思考题 for bread

Bread Story

You have a piece of bread which can be seen as a N*M grid. You also have a bottle of jam. You want to put some jam on the bread to make the bread delicious.

You can do the following two operations:

  1. Put 1 unit of jam on one grid of the bread.

  2. Flatten the jam on one grid of the bread. To do so, it will change the adjacent 4 grids and itself's jam size to 1/5 of the grid you are flattening. For example, if you try to flatten a grid of 1/5 unit of jam, you will get 1/25 unit of jam in grid (x-1,y) (x,y) (x+1,y) (x,y-1) (x,y+1).

Note: if you try to do flatten on an edge grid, the parts that not in the bread will be wasted. And the flatten is accumulate safe, that is to say, you can add the jam in one grid. See example for details.

You will consider the bread delicious if all grids have at least unit of jam. Find the minimum number of operation 1 required.

Example

Input
n=3,m=1
a=2,b=1
Output
2
Explain
You can do as follow:
put two jam at grid (1,2) so that the bread becomes (0,2,0)
flatten (1,2) so that the bread becomes (2/5,2/5,2/5)

To understand the problem better, you can see the following solution too:

first put a unit of jam at grid (1,1) so that the bread becomes (1,0,0)
then put a unit of jam at grid (1,3) so that the bread becomes (1,0,1)
Then flatten the first grid, the bread becomes (1/5,1/5,1)
then flatten the third grid, the bread becomes (1/5,2/5,1/5)
then put a unit of jam at grid (1,2) the bread becomes (1/5,7/5,1/5)
then flatten the jam at grid (1,2) the bread becomes (12/25,7/25,12/25)
finally put a unit of jam at grid (1,2) the bread becomes (12/25,32/25,12/25)

Note that this is not the best solution.

Input 2
n=3,m=1
a=1,b=1
Output 2
1
put (1,2)
flatten (1,2)
Explain
This is an example about printing the way to do it

Constriants

Subtask1(10%):n=3,m=3
Subtask2(10%):n,m<=10
Subtask3(10%):n,m<=1000
Subtask4(70%):you need to print the way to do it.

blob