Canadian Computing Competition

The Canadian Computing Competition(CCC) began in 1996 as a forum for high school students in Canada to learn about and enjoy aspects of programming. Since then, it has grown to over 2500 competitors at over 250 schools across the country.

The contest is broken into 2 main contests:

• Stage 1: Written in schools, typically at the end of February. This is a contest composed of 5 questions (either at the Junior or Senior Level). Teachers need to register at the CEMC website in order for contests to be sent to schools.
• Stage 2: The top 20 (or so) contestants from Stage 1 are invited to Stage 2, held at the University of Waterloo, in the early Spring (either April or May). This week-long event involves seminars, a contest (divided into two half-day components) as well as other extra-curricular activities.

The results of Stage 1 and Stage 2 are used to determine the Canadian Team members who participate in the International Olympiad of Informatics (IOI), held in a different country every year.

2007

Stage 1

Senior

There's nothing here.

Problem S3: Friends

Problem Description In a certain school, it has been decided that students are spending too much time studying and not enough time socializing. To address this situation, it has been decided to give every student a friend. Friendship is one-way. That is, if Janet is assigned to be Sarah’s friend, Janet must be friendly to Sarah, but Sarah is not required to reciprocate. The assignment of friends is done by computer using student numbers. Every student is assigned exactly one friend. Sometimes, a ‘circle of friends’ occurs. For example, if Marc is assigned Fred, Fred is assigned Lori, Lori is assigned Jean, and Jean assigned Marc, we have a circle of 4 friends containing Marc, Fred, Lori, and Jean. In the circle, we can say that Marc has a separation of 0 from Fred, of 1 from Lori, of 2 from Jean, and of 3 from Marc. Your task it to identify, given the computer assignment of friends, whether two students are in the same circle of friends, and if so, determine their separation. Input Specification Input begins with a single integer n (2 � n � 9999), on a line by itself, indicating the number of students in the class. The next n lines contain the computer assignment of friendship. An assignment is of the form x y (where 1 � x � 9999, 1 � y � 9999, x 6= y). For example, 1234 8765 is a possible friendship assignment indicating that student 1234 must be friends with student 8765. Following the friendship assignments, there are a series of lines containing two student numbers, separated by a single whitespace. These lines represent the pairs of students that you will determine if they are in same circle of friends and, if so, their separation. The last line of input can be identified by the use of the 0 0 as the friend assignment. Output Specification For each case, you are to print, on a separate line, either Yes or No depending on whether they are in the same circle of friends. If the answer is Yes, follow the output Yes with a single whitespace and then an integer indicating the friend’s separation. Sample Input 6 1 2 2 3 3 1 10 11 100 10 11 100 1 100 2 3 0 0 Output for Sample Input No Yes 0

Problem S4: Waterpark Problem Description The local waterpark has a great slide complex, with many paths crisscrossing down the hill. There is one start point and one end point, but at various points one can turn and take different paths. Walter and Wanda are wondering exactly how many different ways there are to go down the slide. Can you solve their problem? More precisely, there are n marked points (including the start at 1 and the end at n) where the paths down the hill may split or merge. All paths move down the hill to higher numbered positions; some paths will actually cross over others without meeting but we don’t have to worry about that. We won’t worry about the collisions between sliders that can happen either. Our problem is simply to determine the number of different sequences of marked points we can follow down the hill. For example, at one small waterpark, there are 4 points with direct slides from 1 to points 2 and 4; from 2 to 3 and 4; and from 3 to 4. There are 3 ways down the hill. You can check this by seeing that we can go (1,2,3,4), (1,2,4) or (1,4). (Here is a hint: think about starting at the bottom of the slide.) Input Specification Input begins with a single integer n (1 � n � 9999), on a line by itself, indicating the number of marked points. The next lines contain point pairs of the of the form x y, where 1 � x < y � n. For example, 1234 8765 indicates a direct slide from point 1234 to point 8765. The last line of input will be indicated by point pair 0 0. Output Specification The output is an integer, which is the number of different paths from point 1 to point n. You can assume that the number of paths will be less than 230. It is possible that there is no path from point 1 to point n, in which case the number of paths is 0. Sample Input 4 1 2 1 4 2 3 2 4 3 4 0 0 Output for Sample Input 3