天気のスケジュールをつくる問題。

Problem D
Weather Forecast
---- 2003年 会津大会 ----

You are the God of Wind.
 「貴方は風の神様。」

By moving a big cloud around, you can decide the weather: it invariably rains under the cloud, and the sun shines everywhere else.
 「雨雲を動かすことで、天気を左右できる。雲の下はいつも雨、雲のないところはいつも晴れだから。」

But you are a benign God: your goal is to give enough rain to every field in the countryside, and sun to markets and festivals. Small humans, in their poor vocabulary, only describe this as “weather forecast”.
 「でも、貴方は情け深く、十分な量の雨を降らせたいが、マーケットや祭りのある日に晴れてやりたい。」

You are in charge of a small country, called Paccimc. This country is constituted of 4x4 square areas, denoted by their numbers.
 「4x4正方形の国が任せられた。」

Your cloud is of size 2x2, and may not cross the borders of the country.
 「雲の大きさは2x2。しかも国境から出てはいけない。」

You are given the schedule of markets and festivals in each area for a period of time. On the first day of the period, it is raining in the central areas (6-7-10-11), independently of the schedule.
 「ある期間内の、マーケットや祭りのスケジュール表はもらえる。最初の日には、スケジュールと関係なく、中央地区(6-7-10-11)は雨になっている。」

On each of the following days, you may move your cloud by 1 or 2 squares in one of the four cardinal directions (North, West, South, and East), or leave it in the same position. Diagonal moves are not allowed. All moves occur at the beginning of the day.
 「その後の日には、上下左右4方向に、1地区、または2地区、雨雲を動かすことができる。同じ場所に留めることもできる。対角線方向の移動はできない。一日の始まりの時刻に移動する。」

You should not leave an area without rain for a full week (that is, you are allowed at most 6 consecutive days without rain). You don’t have to care about rain on days outside the period you were given: i.e. you can assume it rains on the whole country the day before the period, and the day after it finishes.
 「1週間雨の降らない地区があってはいけない、つまり、雨の降らない日は個々の地区では最大6日間。期間外の日に雨の心配はしなくていい。つまり、期間前後の日に全国的に雨が降ると仮定してもいい。」

Input

The input is a sequence of data sets, followed by a terminating line containing only a zero.
 「入力は複数のデータセットが入る。入力の終了として、0の行が入る。」

A data set gives the number N of days (no more than 365) in the period on a single line, followed by N lines giving the schedule for markets and festivals. The i-th line gives the schedule for the i-th day. It is composed of 16 numbers, either 0 or 1, 0 standing for a normal day, and 1 a market or festival day. The numbers are separated by one or more spaces.
 「データセットに、期間の日数N(365以下)が与えられ、その後にN行が続き、マーケットと祭りのスケジュールを表す。i行目はi日目のスケジュール。1行に16個の数字があり、0は普通の日、1はマーケットや祭りのある日を示す。」

Output

The answer is a 0 or 1 on a single line for each data set, 1 if you can satisfy everybody, 0 if there is no way to do it.
 「それぞれのデータセットに対し、0か1を1行ずつ出力すること。すべての要望に満足させることができるならば1、ダメなら0にすること。」

Sample Input

1
0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0
7
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 1 0 0 0 0 1 1 0 0 1
0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 1
0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0
0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0
1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1
0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0
7
0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0
0 0 1 0 0 0 0 1 0 0 0 0 0 1 0 0
0 0 0 1 0 0 0 0 0 0 1 0 1 0 0 0
0 1 0 0 0 0 0 1 0 0 0 0 1 0 0 0
0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0
0 0 0 0 0 0 0 1 1 0 1 0 0 0 0 1
0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0
15
0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0
0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0
0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 1 1 0 1 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0
0 0 1 1 0 0 0 0 0 1 0 0 0 0 0 0
1 1 0 0 0 0 0 0 0 0 1 0 0 1 0 0
0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0
0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0
1 0 0 1 1 0 0 0 0 1 0 1 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0
0 0 0 0 0 1 0 1 0 1 0 0 0 0 0 0
0

Output for the Sample Input

0
1
0
1

Comments are closed.

Post Navigation