Splashing's blog

By Splashing, history, 5 months ago, In English,

I think it is easy to provide the answer is ⌊(H+1)*(W+1)/6⌋ but my english is pool.XD

So I can only provide it in Chinese.

I'm so sorry for my pool English.

Hope somebody can translate it to English.

问题等价于在(H+1)*(W+1)的格子中放置2*3的砖块,砖块可以旋转,两个砖块之间不能重合但是可以共用边或顶点,求最多能放多少砖块。

考虑X*Y的格子中能放多少砖块

<1>当1<X,Y<=7时,答案为⌊X*Y/6⌋。这可以通过暴力验证

<2>当X=6且Y>1时,砖块可以填满格子。原因是6*2和6*3的格子都可以被砖块填满,而任何大于1的数都可以表示为2*i+3*j,其中i和j为自然数。

<3>由<2>可以推出,当X为6的倍数且Y>1时,砖块可以填满格子。所以接下来只需考虑X和Y都不是6的倍数的情况。

<4>当1<X<6且Y>6时,分以下两种情况:

如果Y%6==1,那么将Y表示为6*c+7。X*Y就被分为两个部分:X*(6*c)、X*7。根据<3>可知第一部分会被砖块填满,又因为1<X<6可根据<1>得出后一部分答案为⌊X*7/6⌋,所以总体答案为⌊X*Y/6⌋。

如果Y%6!=1,那么将Y表示为6*c+d,其中d=Y%6。X*Y就被分为两个部分:X*(6*c)、X*d。根据<3>可知第一部分会被砖块填满,又因为1<X<6且1<d<6可根据<1>得出后一部分答案为⌊X*d/6⌋,所以总体答案为⌊X*Y/6⌋。

<5>当6<X,Y时,分以下三种情况

如果X%6==1且Y%6==1,那么将X表示为6*a+7,将Y表示为6*c+7。X*Y就被分为四个部分:(6*a)*(6*c)、(6*a)*7、7*(6*c)、7*7。根据<3>可知前三个部分会被填满,根据<1>可知第四个部分答案为⌊7*7/6⌋,所以总体答案为⌊X*Y/6⌋。

如果X%6和Y%6中仅有一个为1,不失一般性地我们可以设X%6==1,那么将X表示为6*a+7,将Y表示为6*c+d,其中d=Y%6。X*Y就被分为四个部分:(6*a)*(6*c)、(6*a)*d、7*(6*c)、7*d。根据<3>可知前三个部分会被填满,根据<1>可知第四个部分答案为⌊7*d/6⌋,所以总体答案为⌊X*Y/6⌋。

如果X%6!=1且Y%6!=1,那么将X表示为6*a+b,将Y表示为6*c+d,其中b=X%6,d=Y%6。X*Y就被分为四个部分:(6*a)*(6*c)、(6*a)*d、b*(6*c)、b*d。根据<3>可知前三个部分会被填满,又因为1<b,d<6,根据<1>可知第四个部分答案为⌊b*d/6⌋,所以总体答案为⌊X*Y/6⌋。

所以X*Y的格子最多并且一定能放⌊X*Y/6⌋个砖块,所以原问题的答案为⌊(H+1)*(W+1)/6⌋。

 
 
 
 
  • Vote: I like it
  • +43
  • Vote: I do not like it

»
5 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by Splashing (previous revision, new revision, compare).

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by Splashing (previous revision, new revision, compare).

»
5 months ago, # |
Rev. 3   Vote: I like it +6 Vote: I do not like it

Splashing read it once...

The problem is equivalent to placing 2*3 bricks in the (H+1)*(W+1) grid. The bricks can be rotated. The two bricks cannot overlap but can share edges or vertices.

How many bricks to put.

<1> When 1<X, Y<=7, the answer is ⌊X*Y/6⌋.

<2> When X=6 and Y>1, the bricks can fill the grid. The reason is that the 6*2 and 6*3 grids can all be filled with bricks, and any number greater than 1 can be expressed as 2*i+3*j, where i and j are natural numbers.

<3> can be derived from <2>. When X is a multiple of 6 and Y>1, the brick can fill the grid. So the next step is to consider the case where X and Y are not multiples of 6.

<4> When 1<X<6 and Y>6, the following two cases are considered:

If Y%6 = =1, then Y is represented as 6*c+7. X*Y is divided into two parts: X*(6*c) and X*7. According to <3>, the first part will be filled with bricks, and because 1<X<6 can be based on <1>, the latter part of the answer is ⌊X*7/6⌋, so the overall answer is ⌊X*Y/6⌋ Hey.

If Y%6!=1, then Y is represented as 6*c+d, where d=Y%6. X*Y is divided into two parts: X*(6*c) and X*d. According to <3>, the first part will be filled with bricks, and because 1<X<6 and 1<d<6, the latter part of the answer is ⌊X*d/6⌋ according to <1>, so the overall answer is ⌊X*Y/6⌋.

<5> When 6<X, Y, the following three cases

If X%6==1 and Y%6==1, then X is represented as 6*a+7, and Y is represented as 6*c+7. X*Y is divided into four parts: (6*a)*(6*c), (6*a)*7, 7*(6*c), 7*7. According to <3>, the first three parts will be filled. According to <1>, the answer to the fourth part is ⌊7*7/6⌋, so the overall answer is ⌊X*Y/6⌋.

If only one of X%6 and Y%6 is 1, we can set X%6==1 without loss of generality, then denote X as 6*a+7 and Y as 6*c+d. , where d=Y%6. X*Y is divided into four parts: (6*a)*(6*c), (6*a)*d, 7*(6*c), 7*d. According to <3>, the first three parts will be filled. According to <1>, the answer to the fourth part is ⌊7*d/6⌋, so the overall answer is ⌊X*Y/6⌋.

If X%6!=1 and Y%6!=1, then X is represented as 6*a+b, and Y is represented as 6*c+d, where b=X%6, d=Y%6. X*Y is divided into four parts: (6*a)*(6*c), (6*a)*d, b*(6*c), b*d. According to <3>, the first three parts will be filled, and because 1<b, d<6, according to <1>, the answer to the fourth part is ⌊b*d/6⌋, so the overall answer is ⌊X* Y/6⌋.

So the X*Y grid is the most and must be able to put ⌊X*Y/6⌋ bricks, so the answer to the original question is ⌊(w+1)* (h+1)/6⌋.