Problem: Street Construction
Want to try solving this problem? You can submit your code online if you log in or register.
Input File: streetin.txt
Output File: streetout.txt
The great city of Dubvegas is designing one side of a new street. This street
is divided into evenly sized chunks of land, each of which will be used for
either a house or a park. The city takes great pride in both the number of
parks that it has, and that no one has to walk far to reach one of their
In particular, the city calls a group of consecutive houses a `block'. The size
of a block is the number of houses it contains.
You must determine, given the number of chunks of land on the street and the
number of parks that will be built, the minimum possible size of the largest
The only line will contain the number of chunks of land N on the street,
followed by the number of parks that will be built K.
Your program should output the minimum possible size of the largest block on a
street with N chunks of land, where K parks will be built.
Sample Input 1
Sample Output 1
Consider the three possible positions for the one park that must be built.
Either it is on one of the ends of the street or in the middle of the street.
If the park is placed on one of the ends of the street then there will be a
block of size 2. However, if the park is placed in the middle of the street,
then there will be two blocks of size 1. Therefore, the smallest we can make
the largest block is 1.
Sample Input 2
Sample Output 2
Since all locations on the street must be occupied by a park, the only
possible block size is 0.
Sample Input 3
Sample Output 3
By placing the parks in the second and fifth chunks we create blocks of size 1,
2, and 2. Note also that it would be impossible to have a largest block of size
1, since once you create two blocks of size 1 the remaining block must be
size 3. Therefore the smallest the largest block can be is 2.
Subtasks & Constraints
For all cases, 1 ≤ K ≤ N ≤ 1,000,000,000.
- For Subtask 1 (35 marks), N ≤ 3. There will never be more than three chunks of land.
You may wish to write a separate if statement for each possible case in this subtask.
- For Subtask 2 (15 marks), N = 17, K = 4. There is only one case in this subtask, where
there are 17 chunks of land and 4 parks to be built. You may wish to write a separate
if statement for this single case.
- For Subtask 3 (15 marks), 1 ≤ N ≤ 1,000,000,000, K = 1. There is always exactly one
park to build.
- For Subtask 4 (15 marks), 2 ≤ N ≤ 100, K = 2. There are always exactly two
parks to build.
- For Subtask 5 (20 marks), no further constraints apply.