i see N%3 solution everywhere but does anyone have any explanation as to why the guy who has mod-3 no of stones should lose. Some logical or mathematical reason would be much appreciated. Let's see that for every number k which is an integer power of 2, k mod 3 = 1, or 2. (To be exact - table of (k mod 3) for {1,2,4,8,16,32,64... is: {1,2,1,2,1,2,1,2,1,2,... So, you can see that it is impossible to get from (mod 3 = 0) position to another (mod 3 = 0) position in one move. Let n (number of remaining stones) = 3. The first player can make x=1 or x=2 move, but now the second player can counter by making 3-x move and win. So n=3 is a losing position. We have proven that it is impossible to get from one number of stones divisible by 3 to another number of stones divisible by 3 in one move. We can now prove, by the rule of mathematical induction, that every position with n divisible by 3 is a losing position. Let's look - if the first player begins from position with 3*x stones, after any move the opponent can counter by '1' or '2' move and create another position with lesser number of stones, also divisible by 3. In the second case, when first player begins from position with number of stones not divisible by 3 (so n%3=1 or n%3=2), _he_ can now make a '1' or '2' move which will create a (mod 3 = 0) position (which was proven to be losing) for his opponent. Thus, due to arbitrarity of n, any (n mod 3 != 0) position can create a losing position for the second player in one move, so it is a winning position for the first player. Consider these. number of leave stones 1 win 2 win ---- because we can choose 1 or 2 3 lose sure ---- because if you choose 1 number of leave stones == 2 or if you choose 2 number of leave stones == 1 each player will be the winner. 4, 5 win, choose 1, 2 sure each player will be take 1 or 2 sure you will be the winner. 6 lose 7, 8 win .... we can assume if N mod 3 == 0 sure that person will be lose, otherwise we can choose the minimum of first number of stones = N mod 3 so each player will be the loser.
Also we can consider a Grandy function for n from 1 to .... g[0] = 0 g[1] = 1 g[2] = mex{0, g[1]} = 2 g[3] = mex{g[1], g[2]} = 0 g[4] = mex{0, g[2], g[3]} = 1 g[5] = mex{g[4], g[3], g[1]} = 2 ...... g[n] = n%3 More strictly can be proved using mathematical induction My first solution printed 2, if first player wins and the number of rocks is even and printed 1 if it's odd. And this solution got WA9. After printing "some variable" mod 3 the solution got AC. But why did my first idea fail? Hi All,
1. 1st player Take 2 stones left over is 8-2=6 2. 2nd player takes 1 stone left over is 6-1=5 3. 1st player takes either 1 (left over is 4)0r 4 stones (left over is 1) 4. Finally 2nd player takes remiang stones. Thus second player wins. Did I understand the problem statements properly? According to the output given in sample 1st player has won but how? Please could you explain. Regards Anupam Now I got it, in 3rd step player picks up 2 stones. Then it guarnatees win of 1st player. can you write hear some examples? for 12 the answer is 2 is it true
ı understood Edited by author 18.10.2012 14:14 Edited by author 18.10.2012 14:14 ok... if the player 2 wins, then stop showing the second line? pls give help yes. input : 3 output: 2 good luck! Sorry for Russian... моё решение задачи... перевожу число в двоичную чистему исчисления.. считаю количество единичек.. если это количество четное, то выиграл второй, если нечетное, то первый... Почему такое решение проходит все тесты??? Оно же неверное.. например при N=5 моя прога выдаст, что выиграл второй, хотя на самом деле выигрывает первый, взяв 2 камня... Really... Probably it's another one problem with easy tests. PS: На acm.timus.ru много таких задач, тесты требуют доработки :( Иногда проходят ну очень странные решения :) все правильно выйграет второй, по 1 камню тоже можно брать Here is my source! #include <stdio.h> int main(){ char ch; int sumall=0; while (!feof(stdin)) {scanf("%c",&ch); if (feof(stdin)) break;sumall+=ch-48;} //printf("s=%d",sumall); printf("%d\n",(sumall%3==0)+1); if (sumall%3) printf("%d",sumall%3); return 0; } Thanks!!! #include <stdio.h> int main(){ char ch; int sumall=0; while (!feof(stdin)) {scanf("%c",&ch); if (feof(stdin)) break; if (ch>='0' && ch<='9')sumall+=(ch-'0');}<---check at this :) sumall%=3; printf("%d",((sumall==0)+1)); if (sumall) printf("\n%d",sumall); return 0; } Als0, we can use sumall+=ch instead of sumall+=(ch-'0'), because '0' == 0x30 == 3*16 :) in each turn you must take x stones which x is a member of S= {1, 2^1, 2^2, ...} sorry for my poor english. i am freshman in learning c. so please help me to solving this pulzz. what is the meaning of " while (!feof(stdin)) "? while(stream stdin hasn't finished) And... if anyone can gimme a hint about 1146 please email me: swin@mail2000.ru 1146 is simple DP. Just precount the sums of rectangles. I agree with U about P1180! 10 lines and AC. 200 bytes ;) I can't understand it... If N1 takes 2 stones at first move, he will lose, won't he? 1:8 - 2 = 6 2:6 - 2 = 4 1:4 - 2 = 2 2:2 - 1 = 1 1:1 - 1 = 0 Please, tell me, where I'm wrong? I understood my mistake. Sorry. var s:string; i,j:byte; begin readln(s);j:=0; for i:=1 to length(s) do if (s[i]>='0')and(s[i]<='9') then j:=(j+ord(s[i])-ord('0'))mod 3; if j=0 then writeln(2) else begin writeln(1);writeln(j) end; end. yes, i think this solution i right Here is my source! #include <stdio.h> #include <io.h> int main(){ char ch; int sumall=0; while (!feof(stdin)) {scanf("%c",&ch); if (feof(stdin)) break;sumall+=ch-48;} //printf("s=%d",sumall); printf("%d\n",(sumall%3==0)+1); if (sumall%3) printf("%d",sumall%3); return 0; } Thanks!!!! > Here is my source! > > #include <stdio.h> > #include <io.h> > int main(){ > char ch; > int sumall=0; > while (!feof(stdin)) {scanf("%c",&ch); if (feof(stdin)) > break;sumall+=ch-48;} > //printf("s=%d",sumall); > printf("%d\n",(sumall%3==0)+1); > if (sumall%3) printf("%d",sumall%3); > return 0; > } > > Thanks!!!! |
|