CCC '20 J2 - Epidemiology - Olympiads Online Judge

CCC '20 J2 - Epidemiology

View as PDF

Submit solution

All submissions

Best submissions

Points: 3 (partial)

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$ ~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$ ~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$ ~P~. The second line contains $N$ ~N~, the number of people who have the disease on Day $0$ ~0~. The third line contains the value of $R$ ~R~. Assume that $P \le 10^7$ ~P \le 10^7~ and $N \le P$ ~N \le P~ and $R \le 10$ ~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$ ~P~.

Sample Input 1

750
1
5

Output for Sample Input 1

Explanation of Output for Sample Input 1

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

Sample Input 2

10
2
1

Output for Sample Input 2

Explanation of Output for Sample Input 2

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

Comments

1

EtherealComet commented on Oct. 23, 2025, 12:42 a.m.

the question might be a bit incorrectly phrased, really its the current number of people infected multiplies by R (e.g. 1 x 5, then 5 x 5, then 25 x 5 for the first example) each day after day 1. hope this helps!

9
arstgkneio commented on Feb. 2, 2025, 10:02 p.m. ← edit 3 →
A big source of confusion for me was whether a person infects $R$ ~R~ others every day or just on the next day. This becomes obvious after you study the sample outputs, but the original wording could be clearer by stating that each newly infected person infects $R$ ~R~ people only once—specifically on the day immediately after they become infected—and never again after that. Here's how I would've worded it:

You are given three integers $P$ ~P~, $N$ ~N~, and $R$ ~R~.

On Day $0$ ~0~, exactly $N$ ~N~ people start off infected.

Each person who becomes infected infects exactly $R$ ~R~ new people on the very next day and then does not infect anyone again after that.

Let "total infected so far" be the number of unique people who have been infected up to and including a given day.

Task: Determine the first day $d$ ~d~ (starting with Day $0$ ~0~) for which the total infected so far exceeds $P$ ~P~.

Input Specification:

$P$ ~P~ (on the first line), an integer where $1 \le P \le 10^7$ ~1 \le P \le 10^7~.

$N$ ~N~ (on the second line), the initial number of infected people on Day $0$ ~0~, where $1 \le N \le P$ ~1 \le N \le P~.

$R$ ~R~ (on the third line), the number of new infections caused by each infected person on the following day, where $1 \le R \le 10$ ~1 \le R \le 10~.

Output Specification: Output the integer $d$ ~d~ such that the total infected count first becomes greater than $P$ ~P~ at the end of Day $d$ ~d~.

2

PHo3NIX commented on Jan. 18, 2025, 5:18 p.m.

Whether using Python or C++, this problem is a bit difficult to analyze. If you are using C++ you can try to give the start num(in example 1 is 1) to total before your "while".

-30

christin910 commented on Jan. 15, 2024, 1:39 a.m. ← edited →

I use ChatGPT to walk me through the process for CCC problems while practicing, but ChatGPT seems to really struggle to understand this one.

This comment is hidden due to too much negative feedback. Show it anyway.

-8

daveys commented on Jan. 12, 2024, 10:27 a.m.

Interesting problem and surprisingly more difficult to solve than I expected it to be.

This comment is hidden due to too much negative feedback. Show it anyway.

73

Spitfire720 commented on Feb. 22, 2022, 1:10 a.m.

Only in Canada will you have contest organizers apologize for a pandemic that they didn't know would happen.

27

thomas_li commented on Feb. 22, 2022, 1:38 a.m.

meanwhile USACO made COWVID-19 themed problems

10

QooModa commented on Feb. 21, 2022, 9:42 p.m.

An important lesson I have learned. Don't forget to delete the code you write to check new values.

I lost half an hour trying to find out why my answer was correct, and then I noticed I had some print statements to check the values.

6

Amateur360 commented on Oct. 10, 2020, 1:53 a.m. ← edited →

It's a very interesting challenge though.

28

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

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

-67

Dingledooper commented on April 3, 2020, 9:42 p.m.

Not really.

This comment is hidden due to too much negative feedback. Show it anyway.