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.