10891  Game of Sum
Moderator: Board moderators
10891  Game of Sum
hi, Can anyone(who got Ac) help me abt 10891? Can u tell me how to proceed to solve the problem?
And I am afraid abt 10892 that i wont solve it within given time. So pls show the way to solve it
And I am afraid abt 10892 that i wont solve it within given time. So pls show the way to solve it

 A great helper
 Posts: 281
 Joined: Tue Sep 10, 2002 5:14 am
 Location: Mountain View, CA, USA
 Contact:
10891
What does the phrase "consecutive numbers" mean? Does that mean that the numbers themselves are consecutive (like "1, 2, 3" or "6, 5, 4"), or does it simply mean that they are consecutive inside the array?
Also, could anyone please explain why the answer to the first test case is 7?
Also, could anyone please explain why the answer to the first test case is 7?
If only I had as much free time as I did in college...

 A great helper
 Posts: 281
 Joined: Tue Sep 10, 2002 5:14 am
 Location: Mountain View, CA, USA
 Contact:
Nevermind. I figured it out.
Code: Select all
Player A takes 7.
Player B takes 4 and 10.
Player A takes 20.
If only I had as much free time as I did in college...
shamim is correct. Abednego's method gives an answer of 7, not 7.
oulongbin, both players play to get the maximum difference, so if A takes 7, B will take 4 and 10, leaving A with 20 so that B wins with 6 vs. 13. B wouldn't let A pick between 10 and 20 when B could have taken the 10 leaving A with the 20.
oulongbin, both players play to get the maximum difference, so if A takes 7, B will take 4 and 10, leaving A with 20 so that B wins with 6 vs. 13. B wouldn't let A pick between 10 and 20 when B could have taken the 10 leaving A with the 20.

 Experienced poster
 Posts: 120
 Joined: Sat Nov 01, 2003 6:16 am
 Location: Dhaka (EWU)
Hi
in problem 10892
 I have solved this problem by this way
 first i have stored all factor's of the given number
 then a n square loop to find out the LCM Cardinality.
 if two factor's lcm is N then i have increased my counter variable.
 then just print the counter variable.
and in problem 10891 is a game theory problem
 you can solve this probem by using memoization.
Thanks
MAP
in problem 10892
 I have solved this problem by this way
 first i have stored all factor's of the given number
 then a n square loop to find out the LCM Cardinality.
 if two factor's lcm is N then i have increased my counter variable.
 then just print the counter variable.
and in problem 10891 is a game theory problem
 you can solve this probem by using memoization.
Thanks
MAP
thank you very much!jdmetz wrote:shamim is correct. Abednego's method gives an answer of 7, not 7.
oulongbin, both players play to get the maximum difference, so if A takes 7, B will take 4 and 10, leaving A with 20 so that B wins with 6 vs. 13. B wouldn't let A pick between 10 and 20 when B could have taken the 10 leaving A with the 20.
i know the problem.
try these :
Output :
Code: Select all
2
7 2
3
2 7 3
5
1000 1000 1000 1000 1000
9
823 912 345 100000 867 222 991 3 40000
7
23 35 12 100000 99234 86123 3245
8
23 35 12 100000 99234 86123 3245 1
47
7 7 7 7 7 7 80 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7
48
7 7 7 7 7 7 7 80 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7
22
91 56 23 45 87 65 45 45 78 23 20 41 17 54 51 51 94 62 74 42 76 76
18
92834 95461 15911 56189 6369 80545 31811 51263 30076 68867 36905 32499 59799 334 82991 46636 98741 66601
1
129
20
35463 88121 4362 94457 86235 83680 72686 6003 93069 2015 10436 2139 93162 30380 19067 76335 78941 48620 55887 15679
17
19335 97643 11468 86267 79718 59584 12129 52642 86575 62307 11545 52658 72377 39986 74850 1992 86928
5
91883 97793 54567 64714 98624
43
98473 41866 71129 65936 42626 9194 46718 96921 45613 47677 8763 54634 47259 71448 9918 22666 32711 21692 40207 2017 23040 86083 77809 15472 30718 39085 87911 54827 41686 28354 37203 6548 74184 3043 43961 95189 1238 22002 93507 63546 32527 42778 31614
50
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50
50
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
50
1 2 3 4 5 6 7 8 9 11 11 11 11 11 111 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 112 312 312 123 123 123 123 123 123 123 123 123 123 123 123 123 123 231 31 312
50
1234 1233 12 312 32 23 434 12 312 45 1234 1233 12 312 32 23 434 12 312 45 1234 1233 12 312 32 23 434 12 312 45 1234 1233 12 312 32 23 434 12 312 45 1234 1233 12 312 32 23 434 12 312 45
34
1 2 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3
4
9 100 1 8
50
1 2 3 4 5 6 7 8 9 8 7 66 5 4 3 4 5 6 7 8 9 8 7 6 6 5 4 5 6 3 4 4 5 6 3 4 5 6 3 4 5 6 3 4 5 6 3 4 5 6
50
1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 1 2 3 4 65 67 2 3 4 7 2 3 4 6 6 7 2 3 4 7 78 8 82 2 3 4 7 2 2 34 4 6 7 3 2
3
100 10 10
1
1
50
1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 2 4 3 5 4 6 7 5 6 10 2 5 4 3 4 5 6 7 9 10
6
6 4 3 5 8 8
5
1 5 20 2 1
48
1 2 3 4 5 6 6 7 8 767 765 111 76576 5 64 654 64 7 7657 76575 64 65 6454 64 654 65464 7 5435 65 746 7 546 7 654 7 5435 547 6 6 7 6547 7654 6 754 54353 65 7 8
0
Code: Select all
9
12
1000
139395
116356
116381
108
73
364
93092
129
443781
323860
14747
102465
117
6
408
655
33
116
60
210
100
1
70
18
29
114995
if u can think of it .. u can do it in software.
Simpleibrahim wrote:Anbody can explain the algorithm (DP). I am not getting the right process.
For each segment of the input sequence you want to compute the result of the given game.
Note that after the first move of player A they are playing exactly the same game on the rest of the sequence, player B starts.
Example: If the value of player A's move is 4 and the result of the game on the rest of the sequence is 7, the result of the whole game is 47=3.
overflow?
Do you deal with overflow?Towhid wrote:Can someone provide some I/O for the this problem? My DP solution is getting WA.
Input
Code: Select all
5
2147483648 2147483647 2147483648 2147483647 2147483648
5
2147483647 2147483647 2147483647 2147483647 2147483647
0
Code: Select all
2147483646
10737418235