DMPG '16 S2 - Pandemic

View as PDF

Submit solution

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

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 K each day, with the game starting on day 0.

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


For all subtasks, 0 \le N \le 10^{18}, 2 \le K \le 1\,000, 0 \le D \le 1\,000

Subtask 1 [20%]

K = 2

Subtask 2 [20%]

D = 1

Subtask 3 [60%]

No additional constraints.

Input Specification

The only line of input will have N, K, and D, 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


Sample Input 2

9 3 2

Sample Output 2


Sample Input 3

10 7 10

Sample Output 3


Explanation for Sample Outputs

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

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

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


There are no comments at the moment.