Problem A
Contact Tracing
A novel infectious disease has started spreading through the population. You are tasked with figuring out who might be infected in order to get them to quarantine. The behavior of the disease among members of the population is as follows:
-
When a person comes into contact with someone who is infectious, they may (but do not always) catch the disease. If they catch the disease, they are not infectious for the rest of that day, so they will not spread it to other people they come into contact with that day.
-
When a person catches the disease, they are infectious starting the day after they caught the disease.
-
Starting two days after they caught the disease, they are symptomatic; as a result, they will quarantine themselves and not come into contact with any other people from then on.
You know that on day
Today is day
Input
The first line of input contains three integers
Each of the next
Output
Output a line with a single integer
Explanation of Sample Input 1
In Sample Input 1, Patient Zero could be person 1 or person 4. Persons 2 and 3 can be eliminated, because they had contact on day 2, when Patient Zero would be symptomatic and quarantined.
Suppose person 1 is Patient Zero. Person 1 may have infected person 4 on day 1. Person 1 is symptomatic on day 2, so they begin quarantining. Therefore, there is no chain of contact from person 1 (Patient Zero) to persons 2 or 3, so person 2 and person 3 are safe and do not need to be quarantined. If person 1 infected person 4 on day 1, then person 4 will be symptomatic tomorrow (day 3), so there is no need to contact them because they will isolate on their own. Therefore if Patient Zero is person 1, no one needs to be notified.
Now suppose person 4 is Patient Zero. Person 4 may have infected person 1 on day 1; using the same logic as above, there is no need to notify person 1 or person 4 to quarantine on day 3. This leaves persons 2 and 3, which requires us to consider multiple infection patterns.
If person 4 infected both persons 2 and 3 on day 1, then both of them will be symptomatic and self-quarantine starting on day 3, so we do not need to notify them.
Suppose instead person 4 infected person 2 but NOT person 3 on day 1. (Remember that transmission is not guaranteed.) In this case, person 2 could go on to infect person 3 on day 2, and person 3 would not yet be symptomatic on day 3, so we would need to notify person 3 to quarantine.
Similarly, if person 4 infected person 3 but NOT person 2 on day 1, we would need to notify person 2 to quarantine.
Therefore to be sure we can halt the outbreak, we need to notify both person 2 and person 3 to quarantine. This is guaranteed to stop the outbreak, whether person 1 or person 4 is Patient Zero.
Sample Input 1 | Sample Output 1 |
---|---|
4 2 4 1 4 1 2 3 2 2 4 1 3 4 1 |
2 2 3 |