## MALD Contest 1 P3 - Scratch Cat and Infestation

View as PDF

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 Scratch Cats in the country with various immune systems. The cat will be naturally infected after 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 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.

#### Input Specification

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

The next line will contain space-separated integers, the values of the 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
1, 0, 0Cat is naturally infected.
1, 1, 0Cat is naturally infected. The two Yubocats manually infect cat .
1, 1, 1Cat becomes a Yubocat as a result of his manual infection yesterday.

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