10560 - Minimum Weight

All about problems in Volume 105. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Post Reply
Pier
New poster
Posts: 38
Joined: Thu Mar 27, 2003 9:12 pm
Location: Aguascalientes, Mexico
Contact:
Contact Pier

10560 - Minimum Weight

Post by Pier »

I keep getting WA. Can someone give me some test cases?

Thanks!
There are 10 kind of people on this world: those who understand binary and those who don't!
Top
BiK
Experienced poster
Posts: 104
Joined: Tue Sep 23, 2003 5:49 pm

Post by BiK »

I think that the required weights are the degrees of 3. However I also keep getting WA.

It is not clear to me whether the solution must output the weights need to weigh the 1<= i < N or 1<= i <= N. Besides, the problem statement says that the queris must be answered with the weights in descending order irrespective of sign. The sample output, however, prints the signs. What is my solutions supposed to do. Nevertheless I tried all possible combinations and I still get WA.

Any hints would be greatly appreciated.
Top
Red Scorpion
Experienced poster
Posts: 192
Joined: Sat Nov 30, 2002 5:14 am

Post by Red Scorpion »

Here sample input output:

INput:
28243 10
12483 2147 292 99 120 30 19 1 2 99
100000 5
1999 999 2993 1 77777
2000000000 10
1999999999 88888889 99999 1009299 129999 199992 77182 53514 16627 7761800
0 0

output:
10 1 3 9 27 81 243 729 2187 6561 19683
19683-6561-729+81+9
2187-27-9-3-1
243+81-27-9+3+1
81+27-9
81+27+9+3
27+3
27-9+1
1
3-1
81+27-9
12 1 3 9 27 81 243 729 2187 6561 19683 59049 177147
2187-243+81-27+1
729+243+27
2187+729+81-3-1
1
59049+19683-729-243+27-9-1
21 1 3 9 27 81 243 729 2187 6561 19683 59049 177147 531441 1594323 4782969 14348907
43046721 129140163 387420489 1162261467 3486784401
3486784401-1162261467-387420489+43046721+14348907+4782969+531441+177147+19683-6561-2
187-729+243-81+1
129140163-43046721+4782969-1594323-531441+177147-59049+19683+729-243-27+3-1
177147-59049-19683+2187-729+243-81-27-9
1594323-531441-59049+6561-2187+729+243+81+27+9+3
177147-59049+19683-6561-2187+729+243-9+3
177147+19683+2187+729+243+3
59049+19683-2187+729-81-9-3+1
59049-6561+729+243+81-27
19683-2187-729-243+81+27-9+3+1
14348907-4782969-1594323-177147-59049+19683+6561+243-81-27+3-1

Good Luck :lol:
Top
BiK
Experienced poster
Posts: 104
Joined: Tue Sep 23, 2003 5:49 pm

Post by BiK »

Thanks a lot man. Your input actually didn't help me because my wrong program output correct results. But I greatly appreciate that you answered the post and tried to help. To be honest this is a thing that rare happens to me in that forum which makes me think what after all is this forum all about.

My mistake was that I used long long instead of unsigned long long.
Top
Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:
Contact Larry

Post by Larry »

I used long long and was okay... what did you do that made the border cases bad?
Top
junjieliang
Experienced poster
Posts: 169
Joined: Wed Oct 31, 2001 2:00 am
Location: Singapore

Post by junjieliang »

Hey BiK, don't feel disheartened...
There are many reasons why some requests for help don't get replies:
1) Some people just submit code, and if we help, it's something like spoon-feeding the person. Not very helpful isn't it? It'll be better to simply describe the algorithm.
2) Sometimes we really don't know what's the problem, so how to help?
3) It takes a really really really kind person to provide sample IO if he/she solved the problem at first (or second) try, since he/she will most likely have no idea what the tricks are. It'll be easier to provide the input, and ask for output, as some people have done. For me (personally), I'll try to help if I have solved that problem and still have my code.

This is a good forum board, it helped me move from 0 to 400+ problem solved. So don't lose hope okay? :lol:
Top
zubair
New poster
Posts: 17
Joined: Fri Apr 18, 2003 2:22 pm

some test inputs

Post by zubair »

hi,
INput:
28243 10
12483 2147 292 99 120 30 19 1 2 99
100000 5
1999 999 2993 1 77777
2000000000 10
1999999999 88888889 99999 1009299 129999 199992 77182 53514 16627 7761800
0 0

output:
10 1 3 9 27 81 243 729 2187 6561 19683
19683-6561-729+81+9
2187-27-9-3-1
243+81-27-9+3+1
81+27-9
81+27+9+3
27+3
27-9+1
1
3-1
81+27-9
12 1 3 9 27 81 243 729 2187 6561 19683 59049 177147
2187-243+81-27+1
729+243+27
2187+729+81-3-1
1
59049+19683-729-243+27-9-1
21 1 3 9 27 81 243 729 2187 6561 19683 59049 177147 531441 1594323 4782969 14348907
43046721 129140163 387420489 1162261467 3486784401
3486784401-1162261467-387420489+43046721+14348907+4782969+531441+177147+19683-6561-2
187-729+243-81+1
129140163-43046721+4782969-1594323-531441+177147-59049+19683+729-243-27+3-1
177147-59049-19683+2187-729+243-81-27-9
1594323-531441-59049+6561-2187+729+243+81+27+9+3
177147-59049+19683-6561-2187+729+243-9+3
177147+19683+2187+729+243+3
59049+19683-2187+729-81-9-3+1
59049-6561+729+243+81-27
19683-2187-729-243+81+27-9+3+1
14348907-4782969-1594323-177147-59049+19683+6561+243-81-27+3-1
my code runs well for this input. i don't know why my code is getting w/a.
i think it is probably for big input. but i used double to store the weights.
can any body help me with some test input. pls help me on this.
zubair-CUET old sailor
Top
Pawel Wiejacha
New poster
Posts: 1
Joined: Thu Jul 05, 2007 1:47 pm

Post by Pawel Wiejacha »

"If multiple output is possible, take the combination which contains largest weights."

Why output for "8" is:
3 1 3 9

not
3 2 6 9
?

Have I misunderstood the problem? Maybe weights have to be 3^i and I should report bug?
Top
Post Reply

Return to “Volume 105 (10500-10599)”