fry
A housewife has to fry n pies (which she's numbered from 1 to n), by using a frying pan which fits only k pies at most. Each pie has to be fried on both sides, and frying one side of a pie requires exactly one minute.
Task
Write a program that determines the way in which the housewife will proceed
in order to fry all the pies in the shortest amount of time possible.
Input Data
Line one of input file fry.in contains positive integers n and k separated by a space.
Output Data
Line one of output file fry.out
contains the minimum amount of time, tmin,
required to fry the pies. Next in the file are tmin
lines, one line for each minute. Line i+1
will contain at most k+1 positive
integers separated by a space; the first number on the line represents minute
(i) and the following at most
k numbers represent the pies
fried in the frying pan during minute i.
The order the pies are written is not important.
Constraints
0 < n, k < 1000
Examples
| fry.in | fry.out | Explanations (how the pies are fried) |
| 7 4 |
4 |
The 7 pies can be fried in 4 minutes During minute 1 pies 1, 2, 3 and 4 are fried on side 1 During minute 2 pies 1, 2, 3 and 4 are fried on side 2 During minute 3 pies 5, 6, and 7 are fried on side 1 During minute 4 pies 5, 6, and 7 are fried on side 2 |
| fry.in | fry.out | Explanations (how the pies are fried) |
| 3 2 | 3 1 1 2 2 3 1 3 2 3 |
The 3 pies can be fried in 3 minutes During minute 1 pies 1 and 2 are fried on side 1 During minute 2 pie 3 is fried on side 1 and pie 1 on side 2 During minute 3 pies 2 and 3 are fried on side 2 |
| fry.in | fry.out | Explanations (how the pies are fried) |
| 2 1 | 4 1 1 2 1 3 2 4 2 |
The 2 pies can be fried in 4 minutes During minute 1 pie 1 is fried on side 1 During minute 2 pie 1 is fried on side 2 During minute 3 pie 2 is fried on side 1 During minute 4 pie 2 is fried on side 2 |
Time limit: 0.1 seconds/test
Marinel Serban
"Gr. C. Moisil" Iaşi IT High School
marinel_serban@yahoo.com