## DMPG '16 S2 - Pandemic

View as PDF

Points: 7 (partial)
Time limit: 0.6s
Memory limit: 64M

Author:
Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

cheesecake is playing a mobile game where the goal is to spread a disease across the world. At any point in time, he may infect a healthy person with the pathogen, creating a patient zero. This pathogen spreads very quickly. Specifically, the number of infected people increases by a factor of each day, with the game starting on day .

cheesecake is trying to complete a very delicate mission in which he has to infect exactly people over a course of days. In other words, there must be exactly infected people on day . Help him find the minimum number of patient zeros he would have to create to complete his mission.

#### Input Specification

The only line of input will have , , and , separated by spaces.

#### Output Specification

Output the required answer, the minimum number of patient zeros cheesecake would have to create.

#### Sample Input 1

8 2 1

#### Sample Output 1

4

#### Sample Input 2

9 3 2

#### Sample Output 2

1

#### Sample Input 3

10 7 10

#### Sample Output 3

4

#### Explanation for Sample Outputs

In the first case, the optimal solution is to infect people on day .

In the second case, cheesecake should infect just one person on day . On day there will be people infected. And on day there will be , as required.

In the third case, cheesecake should wait until day , infect one person, then infect more on day .