about ProblemB in Codeforces Round #571 (Div. 2)

Revision en3, by Splashing, 2019-06-29 07:44:45

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⌋。

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en5 English Splashing 2019-06-29 08:00:47 106 Reverted to en3
en4 English Splashing 2019-06-29 08:00:41 106 Reverted to en2
en3 English Splashing 2019-06-29 07:44:45 106 Tiny change: ' pool.XD\nSo I can' -> ' pool.XD\n\n\n\nSo I can' (published)
en2 English Splashing 2019-06-29 07:41:28 1016
en1 English Splashing 2019-06-29 06:33:10 252 Initial revision (saved to drafts)