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.

I can't understand the mean of the problem.
Could you give me some help?

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.

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

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

Please tell me how stones jump, and what happens if there is another stone. Can I jump over two stones in one grid?

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.

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???

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.

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.

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 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
   =>

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?

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

For this tests is this output ok?
999 999 -> 250000
1000 999 -> 500
500 1000 -> 250