Show all threads Hide all threads Show all messages Hide all messages |
Mathematical proof! | Elastoman | 1051. Simple Game on a Grid | 10 Mar 2024 00:38 | 2 |
Listen everyone, who wants to prove the algorithm to this problem! See the solution of the problem 3 from IMO34 (International Mathematical Olympiad, year 1993). The rectangle in that problem is n*n (not m*n), but it isn't important. And the case 1*n is clear, I think. The problem statement in the problem set for IMO34 is somewhat better. Definitely worth reading. |
I need help! | yick | 1051. Simple Game on a Grid | 17 Dec 2015 11:47 | 1 |
I can't understand the mean of the problem. Could you give me some help? |
Correct idea is HERE | Vlad Veselov | 1051. Simple Game on a Grid | 31 Aug 2013 20:06 | 7 |
I will show you only two combinations("x" means stone, that was killed at last lead). 1). Those you can kill three stones oo xo oo ox oo oo ox o oo oo o o 2). Those you can kill six stones o oo ox o oooo ooox oox oo oo ox o oooo ooo oo oo xo oo ox This are all you need to get AC. (But I cannot prove that if (M Mod 3 = 0) or (N Mod 3 = 0) answer is 2, I can only show how make it) P.S. Sorry for bad English. BTW, you also need that if you have only one row or column, you can only take half of the stones Interesting. But I also can't proove it! How to get this idea more formally? Let's talk about this. Thank you if n or m is divided by 3 we can prove that we can leave only 3x3 stones. and than its easy to finish game with 2 stones. assume that m is divided by 3.so we can divide rectangle into m/3 parts and reduce each's "n" to 3. than reduce m to 3 and we'll get cube with dimensions 3x3. Edited by author 16.04.2007 22:24 I still can't get it,especially for your graph,I hope you can explain it more clear. Thanks. Here comes the proof of why you can't remove all stones but one if M or N is divisible by 3. Let us paint all the grid nodes for which the sum of their coordinates is divisible by 3 ((x + y) mod 3 = 0) in red, all ones meeting the (x + y) mod 3 = 1 condition in green, and the rest in blue. Let us also denote the amount of stones placed in red, green and blue nodes as R, G and B respectively. Obviously, each turn two stones lying on nodes of different colors turn into one stone lying on the third color. So, two of the R, G and B values get decreased by 1, and the third one gets increased by 1. This process has an invariant: parities of (R - G), (R - B) and (G - B) don't change! At the start of the game with M or N being divisible by 3 R, G and B are equal. So all the three differences listed above stay even till the very end, and it's impossible to get the (1,0,0), (0,1,0) and (0,0,1) combinations of R,G,B, therefore the game can't be finished with only one stone. Q.E.D. P.S. My English could have some flaws, i know. |
algorithm | kamran_maharov | 1051. Simple Game on a Grid | 15 Feb 2012 19:26 | 2 |
the main idea is that: if we have 2*3 sized grid we can erase top or bottom row. ... we can get either ... ... or ... using this: let's say that n<m. if n%3==0 we can convert n*m to n*3 and the n*3 to 3*3 same approach also works when m%3==0. 3*3 grid is elementary grid which we can get minimum 2 stones from it. if n%3==1 AND m%3==1 example .... .... .... .... cut this into .... .... ...^ ..^^ ^... ^... ^..^ ^.^^ ^... ^... ^..^ ^.^^ ^... ^^^^ ^^^^ ^^^^ (^ means erased stone.) After this we can get 1 stone easily. cut 1*3 pieces in first column vertically,then in bottom rows horizontally,then upper rows vertically until this figure achieved. if n%3==1 AND m%3==2 example ..... ..... ..... ..... cut this into ..... ..... ..... ....^ ...^^ ^.... ^^... ^^... ^^..^ ^^.^^ ^.... ^^... ^^... ^^..^ ^^.^^ ^.... ^^... ^^^^^ ^^^^^ ^^^^^ from this figure we can get 1 also. cut 1*3 pieces from 1nd and 2nd columns vertically,then bottom rows horizontally and upper rows vertically. if n%3==2 AND m%3==2 example ..... (finally) ...^^ ..... (finally) ...^^ ..... (finally) ^^.^^ ..... (finally) ^^^^^ ..... (finally) ^^^^^ cut 1*3 pieces vertically from 1nd and 2nd columns,then horizontally from bottom rows and vertically from upper rows.then we can reduce this grid into 1 stone. AND finally,if n==1 or m==1 the answer is ceil(n/2); Edited by author 13.06.2011 22:04 Edited by author 13.06.2011 22:05 Edited by author 13.06.2011 22:07 Edited by author 13.06.2011 22:07 Why the answer of (3m, n) is same as (3, n). Maybe we can solve (3m, n) for 1, but (3, 3) only for 2. |
poor english as mine | zhongwei1025 | 1051. Simple Game on a Grid | 24 Nov 2011 20:52 | 1 |
the description of the problem is so unclear. the rule of the game is that you take a stone through a stone( just a stone, but not two ) and get to a place which is empty, and the stone which had been passed is taken away. sorry for my poor english. Edited by author 24.11.2011 21:14 |
I cannot understand what is going on! | Иксанов Семён Александрович | 1051. Simple Game on a Grid | 3 Aug 2011 04:05 | 4 |
Please tell me how stones jump, and what happens if there is another stone. Can I jump over two stones in one grid? Stone situated in grid (a;b), then it can move to grid (a+2;b) if it is empty and if there is stone in (a+1;b), stone in (a+1;b) will be taken away;it can move to grid (a;b+2) if it is empty and if there is stone in (a;b+1), stone in (a;b+1) will be taken away; and so on... P.S. My poor, poor English... Your understanding is right... But the discription of the problem is not clear enough. I really can't understand at first. Emm.. is the rectangle solid? That's not clear. |
I uderstand. I got ACC, thanks | npenate | 1051. Simple Game on a Grid | 23 May 2011 03:40 | 1 |
|
I cannot understand | npenate | 1051. Simple Game on a Grid | 23 May 2011 02:35 | 1 |
Actually I can not understand the problem, as I understand it almost always the answer will be 1. Even in the example for me is 1 response: 2 and 3 = 1. x stones intact 0 stones removed
x x x x x x x x x x x x -> _ 0 0 0 x x x x x x x x x -> _ 0 0 0 x _ 0 0 0 x x x x x -> _ 0 0 0 x _ 0 0 0 x _ 0 0 0 x -> _ 0 0 0 _ _ 0 0 0 0 _ 0 0 0 0 x I know I'm wrong, but I do not understand. help me please. sorry for my English. |
I dont know why!!! | visit.er | 1051. Simple Game on a Grid | 7 Sep 2007 19:24 | 1 |
It's easy to understand if (n mod 3=0) or (m mod 3=0) then answer=2 But why are the answers to the rest of datas are all 1???? Can someone tell me??? |
Some changes in the problem. (+) | Sandro (USU) | 1051. Simple Game on a Grid | 22 Jan 2007 23:14 | 1 |
Statement is fixed. Old limitations were 1000x1000 but there were numbers to 10000 in tests. Some new tests were added. Only 90 authors lost their AC. |
whi i get WA end please tell me how i mast do it and i will tell you senc your?here is a my program | I am david. Tabo. | 1051. Simple Game on a Grid | 22 Dec 2006 10:32 | 5 |
var m,n,sol:longint; begin readln (m,n); if m=1 then sol:=(n+1) div 2 else if (m mod 3=0)or(n mod 3=0) then sol:=2 else sol:=1; writeln (sol); end. > var m,n,sol:longint; var tg:longint; > begin > readln (m,n); if m>n then begin tg:=m; m:=n; n:=tg; end; > if m=1 then > sol:=(n+1) div 2 > else > if (m mod 3=0)or(n mod 3=0) then > sol:=2 > else > sol:=1; > writeln (sol); > end. > > > > var m,n,sol:longint; > var tg:longint; > > begin > > readln (m,n); > if m>n then > begin > tg:=m; > m:=n; > n:=tg; > end; > > if m=1 then > > sol:=(n+1) div 2 > > else > > if (m mod 3=0)or(n mod 3=0) then > > sol:=2 > > else > > sol:=1; > > writeln (sol); > > end. > > > > var m,n,sol:longint; var tg:longint; begin readln (m,n); if m>n then begin tg:=m; m:=n; n:=tg; end; if m=1 then sol:=(n+1) div 2 else if (m mod 3=0)or(n mod 3=0) then sol:=2 else sol:=1; writeln (sol); end.
but why?can anyone tell me? |
i don't understand why input 5 2 output = 1 | TestT | 1051. Simple Game on a Grid | 3 Oct 2005 20:31 | 3 |
I think that if m==2 n>2 output must be 2! That's it: The 5:2 is: ABCDE FGHIJ Jumps: J->E; I->D; J->I; G->H; J->C; G->J; A->B; F->G; A->F The stone A remains alone. |
Ask for sample output ? | Tran Nam Trung (trungduck@yahoo.com) | 1051. Simple Game on a Grid | 28 Aug 2005 19:19 | 5 |
I think I don't understand exactly this problem. For the input : 3 4 { 1 2 3 4 5 6 7 8 9 10 11 12 } I jump 5 6 7 8 over 1 2 3 4 --> 1 2 3 4 are taken away. Then I jump 5 6 7 8 over 9 10 11 12 --> 9 10 11 12 are taken away. Then I jump 6 over 5, 7 over 8 --> only 6 and 7 are in the grid. Last I jump 6 over 7 so it's only one stone in the grid . Why the sample output is 2 ? Thanks. 71222119 > I think I don't understand exactly this problem. For the > input : > > 3 4 > { > 1 2 3 4 > 5 6 7 8 > 9 10 11 12 > } > I jump 5 6 7 8 over 1 2 3 4 --> 1 2 3 4 are taken away. the remaining board is 5 6 7 8 z z z z z z z z 9 10 11 12 so you can't get 5, 6, 7, 8 jump over 9, 10, 11 and 12. The correct answer is 1 2 3 4 2 z z 3 4 2 9 z 3 4 2 3 4 5 6 7 8 => 5 6 7 8 => 6 7 8 => 6 7 8 9 A B C 9 A B C A B C A B C Do the same as above, you'll get the board 3 4 7 8 B C and then 4 8 C => get the board of 2 4 z z C Good luck ! QH@ (z means space) > > I think I don't understand exactly this problem. For the > > input : > > > > 3 4 > > { > > 1 2 3 4 > > 5 6 7 8 > > 9 10 11 12 > > } > > I jump 5 6 7 8 over 1 2 3 4 --> 1 2 3 4 are taken away. > > the remaining board is > 5 6 7 8 > z z z z > z z z z > 9 10 11 12 > so you can't get 5, 6, 7, 8 jump over 9, 10, 11 and 12. > > The correct answer is > 1 2 3 4 2 z z 3 4 2 9 z 3 4 2 3 4 > 5 6 7 8 => 5 6 7 8 => 6 7 8 => 6 7 8 > 9 A B C 9 A B C A B C A B C > Do the same as above, you'll get the board > 3 4 > 7 8 > B C > and then > 4 > 8 > C > => get the board of 2 > 4 > z > z > C > > Good luck ! > > QH@ > > (z means space) > > > I think I don't understand exactly this problem. For > the > > > input : > > > > > > 3 4 > > > { > > > 1 2 3 4 > > > 5 6 7 8 > > > 9 10 11 12 > > > } > > > I jump 5 6 7 8 over 1 2 3 4 --> 1 2 3 4 are taken away. > > > > the remaining board is > > 5 6 7 8 > > z z z z > > z z z z > > 9 10 11 12 > > so you can't get 5, 6, 7, 8 jump over 9, 10, 11 and 12. > > > > The correct answer is > > 1 2 3 4 2 z z 3 4 2 9 z 3 4 2 3 4 > > 5 6 7 8 => 5 6 7 8 => 6 7 8 => 6 7 8 > > 9 A B C 9 A B C A B C A B C > > Do the same as above, you'll get the board > > 3 4 > > 7 8 > > B C > > and then > > 4 > > 8 > > C > > => get the board of 2 > > 4 > > z > > z > > C > > > > Good luck ! > > > > QH@ > > > > (z means space) xxxx...| |xxxx...| |.xxx...| |..x....| |..x....| xxxx...|=>|xxxx...|=>|.xxx...|=>|..x....|=>|..x....| xxxx...| |..x.x..| |x.x.x..| |xxxxx..| |x..x.x.| |....... |....... =>|.......=> => |x.xx.x. x...xx. x.....x |
I can't understand this problem! Who can tell me problem in Russian(algorithmus@univ.kiev.ua)? | Algorithmus_UA(algorithmus@univ.kiev.ua) | 1051. Simple Game on a Grid | 14 Jul 2004 23:29 | 6 |
I can only tell you the problem in Chinese > I can only tell you the problem in Chinese tell me sindong@21cn.com Please send me an e-mail. My address is cmc_czfls@163.com Of course I'm a Chinese boy. I need your help. Thanks CMC |
| Xenia | 1051. Simple Game on a Grid | 9 Mar 2002 23:16 | 1 |
I didn't understand: can we jump over a stone, if there is a space knot between 2 stones? I mean can we jump over empty knot? Like this: s _ s => |
Why is the solution... | Stefan Ciobaca | 1051. Simple Game on a Grid | 3 Mar 2002 19:58 | 3 |
Suppose: m<=n if m=1 then sol:=(n+1) div 2 else begin if (m mod 3=0)or(n mod 3=0) then sol:=2 else sol:=1; end; Why is this solution correct? Can someone explain this to me please? o o ooo => oo => o => o o <= this stone hasn't change his position but it delete 3 stones above itself. You can delete 3-line stones in this way, but pay attention that for every deletion, you must leave 3 row or 3 line stones for next deleteion in another direction.( You can delete stones in different direction. After that,the result is either 1 or 2) Good Luck. Wrong................! > o o > ooo => oo => o => > o o <= this stone hasn't change his position > but it delete 3 stones above itself. > > You can delete 3-line stones in this way, but pay attention that > for every deletion, you must leave 3 row or 3 line stones for > next deleteion in another direction.( You can delete stones in > different direction. After that,the result is either 1 or 2) > > Good Luck. |
What's the algorithm to this problem? | Li Yi | 1051. Simple Game on a Grid | 3 Mar 2002 07:55 | 4 |
> This is a my solution: Suppose: m<=n if m=1 then sol:=(n+1) div 2 else begin if (m mod 3=0)or(n mod 3=0) then sol:=2 else sol:=1; end; How did you realise this algorithm? How can you proof that? This solution really impressed me! :-) You may e-mail me: fortuna@acm.org Thank you > > This is a my solution: > Suppose: m<=n > if m=1 then sol:=(n+1) div 2 else > begin > if (m mod 3=0)or(n mod 3=0) then sol:=2 else sol:=1; > end; > > > > > This is a my solution: > > Suppose: m<=n > > if m=1 then sol:=(n+1) div 2 else > > begin > > if (m mod 3=0)or(n mod 3=0) then sol:=2 else sol:=1; > > end; > > |
the rule is: | killer | 1051. Simple Game on a Grid | 13 Feb 2002 23:08 | 1 |
A stone can move must obey: * : the knot is under a stone o : the stone we can move N : the knot is empty N*o o*N o * N N * o |
Wrong answer | Nazar Revutsky | 1051. Simple Game on a Grid | 21 May 2001 02:07 | 4 |
For this tests is this output ok? 999 999 -> 250000 1000 999 -> 500 500 1000 -> 250 > For this tests is this output ok? > 999 999 -> 250000 > 1000 999 -> 500 > 500 1000 -> 250 I can 999 999 ->500 999 999 -> 2 1000 999 -> 2 500 1000 -> 1 Good luck ! Mg9H@Yahoo.Com > > For this tests is this output ok? > > 999 999 -> 250000 > > 1000 999 -> 500 > > 500 1000 -> 250 > I can 999 999 ->500 How you can do this? |