CCC '20 J2 - Epidemiology

View as PDF

Submit solution

Points: 3
Time limit: 1.0s
Python 3 3.0s
Memory limit: 512M

Problem type
Canadian Computing Competition: 2020 Stage 1, Junior #2

People who study epidemiology use models to analyze the spread of disease. In this problem, we use a simple model.

When a person has a disease, they infect exactly R other people but only on the very next day. No person is infected more than once. We want to determine when a total of more than P people have had the disease.

(This problem was designed before the current coronavirus outbreak, and we acknowledge the distress currently being experienced by many people worldwide because of this and other diseases. We hope that including this problem at this time highlights the important roles that computer science and mathematics play in solving real-world problems.)

Input Specification

There are three lines of input. Each line contains one positive integer. The first line contains the value of P. The second line contains N, the number of people who have the disease on Day 0. The third line contains the value of R. Assume that P \le 10^7 and N \le P and R \le 10.

Output Specification

Output the number of the first day on which the total number of people who have had the disease is greater than P.

Sample Input 1

750
1
5

Output for Sample Input 1

4

Explanation of Output for Sample Input 1

The 1 person on Day 0 with the disease infects 5 people on Day 1. On Day 2, exactly 25 people are infected. On Day 3, exactly 125 people are infected. A total of 1 + 5 + 25 + 125 + 625 = 781 people have had the disease by the end of Day 4 are 781 > 750.

Sample Input 2

10
2
1

Output for Sample Input 2

5

Explanation of Output for Sample Input 2

There are 2 people on Day 0 with the disease. On each other day, exactly 2 people are infected. By the end of Day 4, a total of exactly 10 people have had the disease and by the end of Day 5, more than 10 people have had the disease.


Comments


  • -2
    qiao_yun20060930  commented on March 31, 2021, 11:32 a.m.

    always use while tho


  • -4
    jbhero  commented on Jan. 22, 2021, 10:39 p.m.

    What's with all the TLE's? My program is like 15 lines lol


    • 2
      drunkendog  commented on Jan. 26, 2021, 9:31 p.m.

      Switching to PyPy 3 fixed that problem for me, so it might be worth a try in your case


    • 4
      Kirito  commented on Jan. 22, 2021, 11:30 p.m.

      Firstly, the number of lines is a poor indication of runtime. Consider the following program:

      while True:
          pass
      

      it's only 2 lines, but will clearly take longer than the 4-line long program:

      print("That's")
      print("a")
      print("bad")
      print("argument")
      

      Your issue is that Python is quite slow, and might time out if you need to loop for many days. Can you find a way to compute the answer for small values of N and R without looping?


  • -3
    Nathan2190  commented on Oct. 25, 2020, 10:09 a.m.

    While loop is recommended for this question


    • 32
      kevinyang  commented on Oct. 25, 2020, 1:20 p.m.

      Writing an AC solution is recommended for this question


  • 7
    Amateur360  commented on Oct. 9, 2020, 9:53 p.m. edited

    It's a very interesting challenge though.


  • 18
    euphoria  commented on April 3, 2020, 3:59 p.m.

    This question was surprisingly difficult compared to the other questions during this years contest


  • -15
    Jacob_Tian  commented on March 28, 2020, 2:09 p.m.

    This comment is hidden due to too much negative feedback. Click here to view it.


    • 0
      Boyan  commented on Nov. 24, 2020, 12:36 p.m. edited

      Well, it can be seen as a geometric sequence, where the first term is N, common ratio is R, and the sum of geometric sequence is P. So the second case is the situation which the common ratio is 1, then the total number of people who are infected is N times day = 2 times (5 + 1) = 12. My code has passed and I used the formulas of geometric sequence


    • 10
      ross_cleary  commented on March 28, 2020, 8:16 p.m.

      When someone is infected, they infect R other people ONLY on the very next day, not every day after they are infected.


      • 9
        alihu264  commented on March 29, 2020, 12:22 p.m.

        Kinda doesn't make any sense when you think about it intuitively, but I guess it's what it is.

        Like people don't stop infecting others when they've already infected someone, how would they know?