AIOC Banner

Problem: Street Construction

Want to try solving this problem? You can submit your code online if you log in or register.

Street Construction

Input File: streetin.txt
Output File: streetout.txt
Time Limit: 1 second
Memory Limit: 1 GB

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 wonderful parks.

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 block.


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

3 1

Sample Output 1


Explanation 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

3 3

Sample Output 2


Explanation 2

Since all locations on the street must be occupied by a park, the only possible block size is 0.

Sample Input 3

7 2

Sample Output 3


Explanation 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.


Privacy statement
© Australian Mathematics Trust 2001-2023

Page generated:  3 June 2023,  2:52pm AEST