MALD Contest 1 P3 - Scratch Cat and Infestation

View as PDF

Submit solution


Points: 7
Time limit: 1.0s
Memory limit: 512M

Author:
Problem type
Spot the imposter

An outbreak of a terrible disease, the "Yubonic Plague," had occurred in ScratchLand, infecting all cats within. There are N Scratch Cats in the country with various immune systems. The i^\text{th} cat will be naturally infected after t_i days. Natural infections occur right when the day starts. When a Scratch Cat catches the disease, it will turn into a Yubocat. Unlike their counterparts, Yubocats are rather smart. Each day, a group of K Yubocats can surround and infect one Scratch Cat. A Yubocat can only take part in one infection per day. Manually infected Scratch Cats will become Yubocats at next day's start. The SCHO (Scratch Cat Health Organization) forces kindly asks you for help. What is the minimum number of days it will take to infect the entire population of ScratchLand?

Note that because natural infections occur right when a day starts, naturally infected cats can group with other Yubocats to infect Scratch Cats on the same day they are naturally infected.

Constraints

1 \le K \le N \le 10^6

1 \le t_i \le 10^9

Input Specification

The first line will contain two space-separated integers N and K, the number of Scratch Cats and Yubocats required to transform a Scratch Cat on a given day.

The next line will contain N space-separated integers, the t_i values of the N cats.

Output Specification

Output the minimum days to infect the entire population of ScratchLand.

Sample Input

3 2
1 2 10

Sample Output

3

Explanation

Let 1 denote infected, and 0 denote uninfected.

DayInfected StatesExplanation
11, 0, 0Cat 1 is naturally infected.
21, 1, 0Cat 2 is naturally infected. The two Yubocats manually infect cat 3.
31, 1, 1Cat 3 becomes a Yubocat as a result of his manual infection yesterday.

It can be shown that 3 is the minimum amount of days to infect all cats.


Comments

There are no comments at the moment.