2018 Canadian Computing Competition
Junior Problems

Problem J1: Telemarketer or not?

Problem Description

Here at the Concerned Citizens of Commerce (CCC), we have noted that telemarketers like to use seven-digit phone numbers where the last four digits have three properties. Looking just at the last four digits, these properties are:

• the first of these four digits is an 8 or 9;

• the last digit is an 8 or 9;

• the second and third digits are the same.

For example, if the last four digits of the telephone number are 8229, 8338, or 9008, these are telemarketer numbers.

Write a program to decide if a telephone number is a telemarketer number or not, based on the last four digits. If the number is not a telemarketer number, we should answer the phone, and otherwise, we should ignore it.

Input Specification

The input will be 4 lines where each line contains exactly one digit in the range from $0$ to $9$.

Output Specification

Output either ignore if the number matches the pattern for a telemarketer number; otherwise, output answer.

Sample Input 1

9
6
6
8

Output for Sample Input 1

ignore

Explanation of Output for Sample Input 1

The first digit is $9$, the last digit is $8$, and the second and third digit are both $6$, so this is a telemarketer number.

Sample Input 2

5
6
6
8

Output for Sample Input 2

answer

Explanation of Output for Sample Input 2

The first digit is $5$, and so this is not a telemarketer number.

Problem J2: Occupy parking

Problem Description

You supervise a small parking lot which has $N$ parking spaces.

Yesterday, you recorded which parking spaces were occupied by cars and which were empty.

Today, you recorded the same information.

How many of the parking spaces were occupied both yesterday and today?

Input Specification

The first line of input contains the integer $N$ $(1\le N\le 100)$. The second and third lines of input contain $N$ characters each. The second line of input records the information about yesterday’s parking spaces, and the third line of input records the information about today’s parking spaces. Each of these $2N$ characters will either be C to indicate an occupied space or . to indicate it was an empty parking space.

Output Specification

Output the number of parking spaces which were occupied yesterday and today.

Sample Input 1

5
CC..C
.CC..

Output for Sample Input 1

1

Explanation of Output for Sample Input 1

Only the second parking space from the left was occupied yesterday and today.

Sample Input 2

7
CCCCCCC
C.C.C.C

Output for Sample Input 2

4

Explanation of Output for Sample Input 2

The first, third, fifth, and seventh parking spaces were occupied yesterday and today.

Problem J3: Are we there yet?

Problem Description

You decide to go for a very long drive on a very straight road. Along this road are five cities. As you travel, you record the distance between each pair of consecutive cities.

You would like to calculate a distance table that indicates the distance between any two of the cities you have encountered.

Input Specification

The first line contains 4 positive integers less than 1000, each representing the distances between consecutive pairs of consecutive cities: specifically, the $i$th integer represents the distance between city $i$ and city $i+1$.

Output Specification

The output should be $5$ lines, with the $i$th line $(1\le i\le 5)$ containing the distance from city $i$ to cities $1$, $2$, ... $5$ in order, separated by one space.

Sample Input

3 10 12 5

Output for Sample Input

0 3 13 25 30
3 0 10 22 27
13 10 0 12 17
25 22 12 0 5
30 27 17 5 0

Explanation of Output for Sample Input

The first line of output contains:

• $0$, since the distance from city 1 to city 1 is $0$;

• $3$, since the distance between city 1 and city 2 is $3$;

• $13$, since the distance between city 1 and city 3 is $3+10=13$;

• $25$, since the distance between city 1 and city 4 is $3+10+12=25$;

• $30$, since the distance between city 1 and city 5 is $3+10+12+5=30$.

Problem J4/S2: Sunflowers

Problem Description

Barbara plants $N$ different sunflowers, each with a unique height, ordered from smallest to largest, and records their heights for $N$ consecutive days. Each day, all of her flowers grow taller than they were the day before.

She records each of these measurements in a table, with one row for each plant, with the first row recording the shortest sunflower’s growth and the last row recording the tallest sunflower’s growth. The leftmost column is the first measurement for each sunflower, and the rightmost column is the last measurement for each sunflower.

If a sunflower was smaller than another when initially planted, it remains smaller for every measurement.

Unfortunately, her children may have altered her measurements by rotating her table by a multiple of 90 degrees.

Your job is to help Barbara determine her original data.

Input Specification

The first line of input contains the number $N$ $(2\le N\le 100)$. The next $N$ lines each contain $N$ positive integers, each of which is at most ${10}^9$. It is guaranteed that the input grid represents a rotated version of Barbara’s grid.

Output Specification

Output Barbara’s original data, consisting of $N$ lines, each of which contain $N$ positive integers.

Sample Input 1

2
1 3
2 9

Output for Sample Input 1

1 3
2 9

Explanation of Output for Sample Input 1

The data has been rotated a multiple of 360 degrees, meaning that the input arrangement is the original arrangement.

Sample Input 2

3
4 3 1
6 5 2
9 7 3

Output for Sample Input 2

1 2 3
3 5 7
4 6 9

Explanation of Output for Sample Input2

The original data was rotated 90 degrees to the right/clockwise.

Sample Input 3

3
3 7 9
2 5 6
1 3 4

Output for Sample Input 3

1 2 3
3 5 7
4 6 9

Explanation of Output for Sample Input 3

The original data was rotated 90 degrees to the left/counter-clockwise.

Problem J5: Choose your own path

Problem Description

There is a genre of fiction called choose your own adventure books. These books allow the reader to make choices for the characters which altersthe outcome of the story.

For example, after reading the first page of a book, the reader may be asked a choice, such as “Do you pick up the rock?” If the reader answers “yes”, they are directed to continue reading on page 47, and if they choose “no”, they are directed to continue reading on page 18. On each of those pages, they have further choices, and so on, throughout the book. Some pages do not have any choices, and thus these are the “ending” pages of that version of the story. There may be many such ending pages in the book, some of which are good (e.g., the hero finds treasure) and others which are not (e.g., the hero finds a leftover sandwich from 2001).

You are the editor of one of these books, and you must examine two features of the choose your own adventure book:

1. ensure that every page can be reached – otherwise, there is no reason to pay to print a page which no one can ever read;

2. find the shortest path, so that readers will know what the shortest amount of time they need to finish one version of the story.

Given a description of the book, examine these two features.

Input Specification

The first line of input contains $N$ $(1\le N\le 10000)$, the number of pages in the book. Each of the next $N$ lines contain an integer $M_i$ $(1\le i\le N;0\le M_i\le N)$, which is the number of different options from page $i$, followed by $M_i$ space-separated integers in the range from $1$ to $N$, corresponding to each of the pages to go to next from page $i$. It will also be the case $M_1+M_2+\cdots +M_N$ is at most 10000.

If $M_i=0$, then page $i$ is an ending page (i.e., there are no choices from that page). There will be at least one ending page in the book.

Note that you always begin the book on page 1.

For 4 of the available 15 marks, $N\le 100$, $M_i\le 10$ for $1\le i\le N$.

For an additional 3 of the available 15 marks, the book is guaranteed to have no cycles.

For an additional 4 of the available 15 marks, $N\le 1000$, $M_i\le 25$ for $1\le i\le N$.

Output Specification

The output will be two lines. The first line will contain Y if all pages are reachable, and N otherwise. The last line will contain a non-negative integer $K$, which is the shortest path a reader can take while reading this book. There will always be a finite shortest path.

Sample Input 1

3
2 2 3
0
0

Output for Sample Input 1

Y
2

Explanation of Output for Sample Input 1

Since we start on page 1, and can reach both page 2 and page 3, all pages are reachable. The only paths in the book are $1\to 2$ and $1\to 3$, each of which is 2 pages in length.

Sample Input 2

3
2 2 3
0
1 1

Output for Sample Input 2

Y
2

Explanation of Output for Sample Input 2

Every page is reachable, since from page 1, we can reach pages 2 and 3. The shortest path is the path 1 $\to$ 2, which contains two pages.