COCI '09 Contest 3 #6 Planete

View as PDF

Submit solution


Points: 20
Time limit: 1.0s
Memory limit: 32M

Problem type

European Space Agency has N telescopes observing distant planets. They classified M different types of events. They noticed that every day on each planet there is exactly one type of event. They measure events in days because they discovered each event lasts at least one day, and at most 365 days. Events last only a complete number of days, they never last a fractional part of a day. Each event of the same type lasts exactly the same number of days every time it occurs, regardless of the planet it occurs on.

After many years of observation, they want to analyze data. The telescopes logged all observations, but unfortunately they forgot to write down the year the observations took place! Each telescope entry consists of the start date, end date and number of each type of event observed. Given all observations on all planets, calculate the duration of each type of event. Note that the telescopes are super precise and they start working exactly when the event starts and end when an event ends, not necessarily the same one.

Note: For this task, each year has exactly 365 days.

Input Specification

First line contains integers N and M (1 \le N, M \le 200), the number of telescopes and the number of event types. Next N lines contain M+4 numbers each:

"D_1D_1\ M_1M_1\ D_2D_2\ M_2M_2\ F_1\ F_2\ \dots\ F_M"

Where D_1D_1\ M_1M_1 (01 \le DD \le 31, 01 \le MM \le 12) are start date, D_2D_2\ M_2M_2 end date, and F_i (0 \le F_i \le 200) number of times event type i was observed.

Output Specification

One line containing M numbers, durations of event types. If more than one solution exists, output any one. If no solution exists, output -1.

Sample Input 1

1 1
26 02 03 03 1

Sample Output 1

5

Explanation for Sample Output 1

The telescope observed one type 1 event between 26 February and 3 March. The only possible explanation is that type 1 events last 5 days.

Sample Input 2

1 1
26 02 03 03 2

Sample Output 2

185

Sample Input 3

3 3
22 03 01 10 9 10 10
05 05 16 12 1 7 10
20 06 15 01 4 9 10

Sample Output 3

102
204
125

Comments

There are no comments at the moment.