パネルを覆うカーペットの最小枚数を決定する問題。

プログラムを楽しく書いている。実用性のありそうな問題なので、本当に楽しい。多くのテキストにあるような、意味不明な四則演算で言語学習するよりも、そういう面白い実例があれば、学習の動機付けに効果的だろう。

Square Carpets --- 2003年 会津大会 国内予選 問題E

[ Problem ]
 Mr. Frugal bought a new house. He feels deeply in love with his new house because it has a comfortable living room in which he can put himself completely at ease. He thinks his new house is a really good buy.
 「新しく住宅を買った。使いやすいリビングルームを見て、満足している。」

 But, to his disappointment, the floor of its living room has some scratches on it.
 「ただ、リビングルームは床にキズが何箇所にある。」

 The floor has a rectangle shape, covered with square panels. He wants to replace all the scratched panels with flawless panels, but he cannot afford to do so. Then, he decides to cover all the scratched panels with carpets.
 「床は四角い形だが、正方形のパネルに覆われている。キズのあるパネルを取り替える経済的余裕がないので、カーペットを敷くことにした。」
 
 The features of the carpets he can use are as follows.
 「使えるカーペットに、つぎの条件がついている。」

   1. Carpets are square-shaped.
   2. Carpets may overlap each other.
   3. Carpets cannot be folded.
   4. Different sizes of carpets are available. Lengths of sides of carpets are multiples of that of the panels.
  「1.正方形。
   2.互いにオーバーラップできる。
   3.折り曲げることはできない。
   4.さまざまなサイズのものが使えるが、それぞれのサイズはパネルの整数倍と考えてよい。」
 
 The carpets must cover all the scratched panels, but must not cover any of the flawless ones.
 「キズのあるパネルはカーペットで覆わなければいけないが、キズのないパネルは覆ってはいけない。」

 For example, if the scratched panels are as shown in Figure 1, at least 6 carpets are needed.
 「例えば、図1のキズに対し、最低6枚のカーペットが必要。」


Figure 1: Example Covering

 As carpets cost the same irrespective of their sizes, Mr. Frugal would like to use as few number of carpets as possible.
 「サイズに関係なく、カーペットは皆同じ値段で買える。したがって、できるだけ少ない枚数にすべきだ。」

 Your job is to write a program which tells the minimum number of the carpets to cover all the scratched panels.
 「キズのついたパネルを覆うカーペットの最小枚数を決めてくれ。」

[ Input ]
 The input consists of multiple data sets. As in the following, the end of the input is indicated by a line containing two zeros.
 「入力に複数のデータセットが含まれる。入力の終了として、最終行に0が2つ入る。」

   DataSet1
   DataSet2
   ...
   DataSetn
   0 0

 Each data set (DataSeti) represents the state of a floor. The format of a data set is as follows.
 「それぞれのデータセットは床の状態を示す。データセットのフォーマットはつぎの通り。」

   W H
   P11 P12 P13 ... P1W
   P21 P22 P23 ... P2W
   ...
   PH1 PH2 PH3 ... PHW

 The positive integers W and H are the numbers of panels on the living room in the x- and y- direction, respectively. The values of W and H are no more than 10. The integer Pyx represents the state of the panel. The value of Pyx means,
 「W, H (10以下の正整数)、リビングルームのx, y方向のパネルの数。Pyx (整数)、パネルの状態を示す。」

   0: flawless panel (must not be covered),
   1: scratched panel (must be covered).
   「Pyxの値が0のものは、キズのないパネルを示す。覆ってはいけない。
    値が1のものは、キズのついたパネルを示す。覆うべきだ。」

[ Output ]
 For each data set, your program should output a line containing one integer which represents the minimum number of the carpets to cover all of the scratched panels.
 「それぞれのデータセットに対し、キズのついたパネルを覆うカーペットの最小枚数を整数1行に出力せよ。」

[ Sample Input ]
4 3
0 1 1 1
1 1 1 1
1 1 1 1
8 5
0 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 0 1 1 1 1
0 1 1 1 0 1 1 1
8 8
0 1 1 0 0 1 1 0
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
0 1 1 0 0 1 1 0
0 1 1 0 0 1 1 0
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
0 1 1 0 0 1 1 0
10 10
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 0 1 1 0 1 1 0 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 0 1 1 0 1 1 0 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 0 1 1 0 1 1 0 1
1 1 1 1 1 1 1 1 1 1
0 0

[ Output for the Sample Input ]
2
6
14
29

Comments are closed.

Post Navigation