2020 Canadian Computing Competition
Junior Problems

Problem J1: Dog Treats

Problem Description

Barley the dog loves treats. At the end of the day he is either happy or sad depending on the number and size of treats he receives throughout the day. The treats come in three sizes: small, medium, and large. His happiness score can be measured using the following formula:

$$1\times S+2\times M+3\times L$$

where $S$ is the number of small treats, $M$ is the number of medium treats and $L$ is the number of large treats.

If Barley’s happiness score is $10$ or greater then he is happy. Otherwise, he is sad. Determine whether Barley is happy or sad at the end of the day.

Input Specification

There are three lines of input. Each line contains a non-negative integer less than $10$. The first line contains the number of small treats, $S$, the second line contains the number of medium treats, $M$, and the third line contains the number of large treats, $L$, that Barley receives in a day.

Output Specification

If Barley’s happiness score is $10$ or greater, output happy. Otherwise, output sad.

Sample Input 1

3
1
0

Output for Sample Input 1

sad

Explanation of Output for Sample Input 1

Barley’s happiness score is $1\times 3+2\times 1+3\times 0=5$, so he will be sad.

Sample Input 2

3
2
1

Output for Sample Input 2

happy

Explanation of Output for Sample Input 2

Barley’s happiness score is $1\times 3+2\times 2+3\times 1=10$, so he will be happy.

Problem J2: Epidemiology

Problem Description

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

Sample Input 1

750
1
5

Output for Sample Input 1

4

Explanation of Output for Sample Input 1

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

Sample Input 2

10
2
1

Output for Sample Input 2

5

Explanation of Output for Sample Input 2

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

Problem J3: Art

Problem Description

Mahima has been experimenting with a new style of art. She stands in front of a canvas and, using her brush, flicks drops of paint onto the canvas. When she thinks she has created a masterpiece, she uses her 3D printer to print a frame to surround the canvas.

Your job is to help Mahima by determining the coordinates of the smallest possible rectangular frame such that each drop of paint lies inside the frame. Points on the frame are not considered inside the frame.

Input Specification

The first line of input contains the number of drops of paint, $N$, where $2\le N\le 100$ and $N$ is an integer. Each of the next $N$ lines contain exactly two positive integers $X$ and $Y$ separated by one comma (no spaces). Each of these pairs of integers represents the coordinates of a drop of paint on the canvas. Assume that $X<100$ and $Y<100$, and that there will be at least two distinct points. The coordinates $(0,0)$ represent the bottom-left corner of the canvas.

For 12 of the 15 available marks, $X$ and $Y$ will both be two-digit integers.

Output Specification

Output two lines. Each line must contain exactly two non-negative integers separated by a single comma (no spaces). The first line represents the coordinates of the bottom-left corner of the rectangular frame. The second line represents the coordinates of the top-right corner of the rectangular frame.

Sample Input

5
44,62
34,69
24,78
42,44
64,10

Output for Sample Input

23,9
65,79

Explanation of Output for Sample Input

The bottom-left corner of the frame is $(23,9)$. Notice that if the bottom-left corner is moved up, the paint drop at $(64,10)$ will not be inside the frame. (See the diagram below.) If the corner is moved right, the paint drop at $(24,78)$ will not be inside the frame. If the corner is moved down or left, then the frame will be larger and no longer the smallest rectangle containing all the drops of paint. A similar argument can be made regarding the top-right corner of the frame.

Problem J4: Cyclic Shifts

Problem Description

Thuc likes finding cyclic shifts of strings. A cyclic shift of a string is obtained by moving characters from the beginning of the string to the end of the string. We also consider a string to be a cyclic shift of itself. For example, the cyclic shifts of ABCDE are:

Given some text, $T$, and a string, $S$, determine if $T$ contains a cyclic shift of $S$.

Input Specification

The input will consist of exactly two lines containing only uppercase letters. The first line will be the text $T$, and the second line will be the string $S$. Each line will contain at most $1000$ characters.

For 6 of the 15 available marks, $S$ will be exactly $3$ characters in length.

Output Specification

Output yes if the text, $T$, contains a cyclic shift of the string, $S$. Otherwise, output no.

Sample Input 1

ABCCDEABAA
ABCDE

Output for Sample Input 1

yes

Explanation of Output for Sample Input 1

CDEAB is a cyclic shift of ABCDE and it is contained in the text ABCCDEABAA.

Sample Input 2

ABCDDEBCAB
ABA

Output for Sample Input 2

no

Explanation of Output for Sample Input 2

The cyclic shifts of ABA are ABA, BAA, and AAB. None of these shifts are contained in the text ABCDDEBCAB.

Problem J5/S2: Escape Room

Problem Description

You have to determine if it is possible to escape from a room. The room is an $M$-by-$N$ grid with each position (cell) containing a positive integer. The rows are numbered $1,2,\dots ,M$ and the columns are numbered $1,2,\dots ,N$. We use $(r,c)$ to refer to the cell in row $r$ and column $c$.

You start in the top-left corner at $(1,1)$ and exit from the bottom-right corner at $(M,N)$. If you are in a cell containing the value $x$, then you can jump to any cell $(a,b)$ satisfying $a\times b=x$. For example, if you are in a cell containing a $6$, you can jump to cell $(2,3)$.

Note that from a cell containing a $6$, there are up to four cells you can jump to: $(2,3)$, $(3,2)$, $(1,6)$, or $(6,1)$. If the room is a $5$-by-$6$ grid, there isn’t a row $6$ so only the first three jumps would be possible.

Input Specification

The first line of the input will be an integer $M$ ($1\le M\le 1000$). The second line of the input will be an integer $N$ ($1\le N\le 1000$). The remaining input gives the positive integers in the cells of the room with $M$ rows and $N$ columns. It consists of $M$ lines where each line contains $N$ positive integers, each less than or equal to $1000000$, separated by single spaces.

For 1 of the 15 available marks, $M=2$ and $N=2$.

For an additional 2 of the 15 available marks, $M=1$.

For an additional 4 of the 15 available marks, all of the integers in the cells will be unique.

For an additional 4 of the 15 available marks, $M\le 200$ and $N\le 200$.

Output Specification

Output yes if it is possible to escape from the room. Otherwise, output no.

Sample Input

3
4
3 10 8 14
1 11 12 12
6 2 3 9

Output for Sample Input

yes

Explanation of Output for Sample Input

Starting in the cell at $(1,1)$ which contains a $3$, one possibility is to jump to the cell at $(1,3)$. This cell contains an $8$ so from it, you could jump to the cell at $(2,4)$. This brings you to a cell containing $12$ from which you can jump to the exit at $(3,4)$. Note that another way to escape is to jump from the starting cell to the cell at $(3,1)$ to the cell at $(2,3)$ to the exit.

Notes

• The online grader begins by testing submissions using the sample input. All other tests are skipped if the sample test is not passed. If you are only attempting the first three subtasks (the first 7 marks), then you might want to handle the specific values of the sample input as a special case.
• For the final subtask (worth 2 marks), if you are using Java, then Scanner will probably take too long to read in the large amount of data. A much faster alternative is BufferedReader.