Canadian Computing Competition: 2011 Stage 1, Junior #5
Mark invited some people to join his social network. Some of them invited new people, who invited new people, and so on. Now there are
How many different sets of people can be removed?
Input Specification
The first line contains a single integer
Output Specification
Output a single integer, the number of possible sets of people that can be removed.
Sample Input 1
3
3
3
Output for Sample Input 1
4
Explanation for Sample 1
The first number of the input indicates there are three people in the network. The next line tells us that Person 1 was invited by Mark, while the last line tells us that Person 2 was also invited by Mark. The sets of people that can be removed are
Sample Input 2
4
3
4
4
Output for Sample Input 2
6
Explanation for Sample 2
There are 4 people in the network. Here is a table of who invited who:
Person inviting | Invited |
---|---|
1 | none |
2 | none |
3 | 1 |
4 | 2,3 |
The possible sets are
Comments
Can person 2 invited by person 3, and person 3 invited by person 2?
Edit: No, it can't. Because person 3 can only be invited by a person who has a higher number than 3.
Mark is always person right?
From the statement, yes: "Person is Mark."