Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|

Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |

Language: Pizza schedule
Description PizzaSocks company makes and delivers pizza. Pizza is delivered on regular schedule. A schedule has a period of 1, 2, 3 or 4 weeks. Quantity of pizzas to be delivered is known for each day of the period. First day of a period is always the first day of the week. So formally pizza delivery schedule can be described by the following numbers: A ≥ 0)._{i}Once an absent-minded PizzaSocks manager lost a schedule for one Very Big and Important Client. Only the history of past deliveries was preserved. Your task is to restore the schedule from the history. The problem is complicated by the fact that occasionally Very Big and Important Client changed his orders, ordering either more or less pizzas than scheduled, even sometimes cancelling the order competely or placing an unscheduled order. So it's often impossible to restore the original schedule exactly. That is why your task is to find an optimal schedule, i. e. to minimize the total number of days when historically ordered quantity is different from the quantity according to that schedule. The days before the first recorded order and after the last recorded one should not be taken into consideration. Input Input file contains the following integer numbers: d _{N}q — description of historical orders: week number, day of the week, and quantity of pizzas delivered. For each day there is no more than one record. It's considered that on those days that are not explicitly mentioned in the input file, but fall between the earliest and the latest mentioned days, zero-quantity orders were fulfilled._{N}
1 ≤ w ≤ 52, 1 ≤ _{i}d ≤ 7_{i}Output Output periodicity of the optimal schedule — integer number L from 1 to 4. Then output numbers i from 1 to L × 7. If several solutions exist, output any of them. However, make sure that the first week of your schedule corresponds to the earliest week mentioned in the input file.Sample Input
Sample Output
Hint Bold texts appearing in the sample sections are informative and do not form part of the actual data. Source Northeastern Europe 2005, Far-Eastern Subregion |

[Submit] [Go Back] [Status] [Discuss]

All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di

Any problem, Please Contact Administrator