Page 1 of 1
10560 - Minimum Weight
Posted: Mon Oct 06, 2003 11:57 pm
by Pier
I keep getting WA. Can someone give me some test cases?
Thanks!
Posted: Tue Oct 07, 2003 4:56 am
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.
Posted: Tue Oct 07, 2003 8:27 am
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
Posted: Tue Oct 07, 2003 6:33 pm
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.
Posted: Tue Oct 07, 2003 8:28 pm
by Larry
I used long long and was okay... what did you do that made the border cases bad?
Posted: Wed Oct 08, 2003 3:05 pm
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?
some test inputs
Posted: Sat Nov 01, 2003 9:47 am
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.
Posted: Thu Jul 05, 2007 1:57 pm
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?