You are a player of the game Mine Craft. As a lawful good player, instead of droping TNT everywhere you want to build your village on a vast plain. The game map could be recognized as a rectangle grid. In one grid, you can set up a gold miner, or an elixir collector, or a headquarter. You also can leave some grids green and vibrant. However, one restriction for some good reasons is that a headquarter must be next to at least one gold miner and at least one elixir collector. 'Next to' means that their grids share one side -- every grid is next to up, down, left, and right grids. "Effeciecy!
You are a player of the game Mine Craft. As a lawful good player, instead of droping TNT everywhere you want to build your village on a vast plain. The game map could be recognized as a rectangle grid. In one grid, you can set up a gold miner, or an elixir collector, or a headquarter. You also can leave some grids green and vibrant. However, one restriction for some good reasons is that a headquarter must be next to at least one gold miner and at least one elixir collector. 'Next to' means that their grids share one side -- every grid is next to up, down, left, and right grids. "Effeciecy!" A good old man said to you. You, the vast plain holder, want to be the most effecient player in the server. You want to maximize the number of headquarters in your village. Formally, If the village is a grid of size n×mn times mn×m, we define the max number of headquarters can be built as f(n,m) f(n,m) f(n,m) . For example, f(1,1)=0 f(1, 1) = 0 f(1,1)=0 since there should be at least 3 grids for setting up a headquarter; f(1,6)=2 f(1, 6) = 2 f(1,6)=2 and one possible solution is (G, H, E, G, H, E)(G, H, E, G, H, E)(G, H, E, G, H, E). To prove that you really understand the problem very well, print the efficiency on the infinite plain. Formally, you need to calculate limn→∞limm→∞f(n,m)n⋅mlim_{ntoinfty} lim_{mtoinfty} frac{f(n,m)}{ncdot m}limn→∞limm→∞n⋅mf(n,m).
