2019 Canadian Computing Competition
Junior Problems

Problem J1: Winning Score

Problem Description

You record all of the scoring activity at a basketball game. Points are scored by a 3-point shot, a 2-point field goal, or a 1-point free throw.

You know the number of each of these types of scoring for the two teams: the Apples and the Bananas. Your job is to determine which team won, or if the game ended in a tie.

Input Specification

The first three lines of input describe the scoring of the Apples, and the next three lines of input describe the scoring of the Bananas. For each team, the first line contains the number of successful 3-point shots, the second line contains the number of successful 2-point field goals, and the third line contains the number of successful 1-point free throws. Each number will be an integer between 0 and 100, inclusive.

Output Specification

The output will be a single character. If the Apples scored more points than the Bananas, output A. If the Bananas scored more points than the Apples, output B. Otherwise, output T, to indicate a tie.

Sample Input 1

Output for Sample Input 1

B

Explanation of Output for Sample Input 1

The Apples scored $10 \cdot 3 + 3 \cdot 2 + 7 \cdot 1 = 43$ points and the Bananas scored $8 \cdot 3 + 9 \cdot 2 + 6 \cdot 1 = 48$ points, and thus the Bananas won.

Input for Sample Input 2

Output for Sample Input 2

T

Explanation of Output for Sample Input 2

The Apples scored $7 \cdot 3 + 3 \cdot 2 + 0 \cdot 1 = 27$ points and the Bananas scored $6 \cdot 3 + 4 \cdot 2 + 1 \cdot 1 = 27$ points, and thus it was a tie game.

Problem J2: Time to Decompress

Problem Description

You and your friend have come up with a way to send messages back and forth.

Your friend can encode a message to you by writing down a positive integer $N$ and a symbol. You can decode that message by writing out that symbol $N$ times in a row on one line.

Given a message that your friend has encoded, decode it.

Input Specification

The first line of input contains $L$ , the number of lines in the message.

The next $L$ lines each contain one positive integer less than 80, followed by one space, followed by a (non-space) character.

Output Specification

The output should be $L$ lines long. Each line should contain the decoding of the corresponding line of the input. Specifically, if line $i + 1$ of the input contained N x, then line $i$ of the output should contain just the character x printed N times.

Sample Input

4
9 +
3 -
12 A
2 X

Output for Sample Input

+++++++++
---
AAAAAAAAAAAA
XX

Problem J3: Cold Compress

Problem Description

Your new cellphone plan charges you for every character you send from your phone. Since you tend to send sequences of symbols in your messages, you have come up with the following compression technique: for each symbol, write down the number of times it appears consecutively, followed by the symbol itself. This compression technique is called run-length encoding.

More formally, a block is a substring of identical symbols that is as long as possible. A block will be represented in compressed form as the length of the block followed by the symbol in that block. The encoding of a string is the representation of each block in the string in the order in which they appear in the string.

Given a sequence of characters, write a program to encode them in this format.

Input Specification

The first line of input contains the number $N$ , which is the number of lines that follow. The next $N$ lines will contain at least one and at most 80 characters, none of which are spaces.

Output Specification

Output will be $N$ lines. Line $i$ of the output will be the encoding of the line $i + 1$ of the input. The encoding of a line will be a sequence of pairs, separated by a space, where each pair is an integer (representing the number of times the character appears consecutively) followed by a space, followed by the character.

Sample Input

4
+++===!!!!
777777......TTTTTTTTTTTT
(AABBC)
3.1415555

Output for Sample Input

3 + 3 = 4 !
6 7 6 . 12 T
1 ( 2 A 2 B 1 C 1 )
1 3 1 . 1 1 1 4 1 1 4 5

Explanation of Output for Sample Input

To see how the first message (on the second line of input) is encoded, notice that there are 3 + symbols, followed by 3 = symbols, followed by 4 ! symbols.

Problem J4/S1: Flipper

Problem Description

You are trying to pass the time while at the optometrist. You notice there is a grid of four numbers:

1	2
3	4

You see lots of mirrors and lenses at the optometrist, and wonder how flipping the grid horizontally or vertically would change the grid.

Specifically, a “horizontal” flip (across the horizontal centre line) would take the original grid of four numbers and result in:

3	4
1	2

A “vertical” flip (across the vertical centre line) would take the original grid of four numbers and result in:

2	1
4	3

Your task is to determine the final orientation of the numbers in the grid after a sequence of horizontal and vertical flips.

Input Specification

The input consists of one line, composed of a sequence of at least one and at most 1 000 000 characters. Each character is either H, representing a horizontal flip, or V, representing a vertical flip.

For 8 of the 15 available marks, there will be at most 1 000 characters in the input.

Output Specification

Output the final orientation of the four numbers. Specifically, each of the two lines of output will contain two integers, separated by one space.

Sample Input 1

HV

Output for Sample Input 1

4 3
2 1

Sample Input 2

VVHH

Output for Sample Input 2

1 2
3 4

Problem J5: Rule of Three

Problem Description

A substitution rule describes how to take a sequence of symbols and convert it into a different sequence of symbols. For example, ABA $\to$ BBB, is a substitution rule which means that ABA can be replaced with BBB. Using this rule, the sequence AABAA would be transformed into the sequence ABBBA (the substituted symbols are in bold).

In this task, you will be given three substitution rules, a starting sequence of symbols and a final sequence of symbols. You are to use the substitution rules to convert the starting sequence into the final sequence, using a specified number of substitutions.

For example, if the three substitution rules were:

AA $\to$ AB
AB $\to$ BB
B $\to$ AA

we could convert the sequence AB into AAAB in 4 steps, by the following substitutions:

\to

\to

AAB

\to

AAAA

\to

AAAB,

where the symbols to be replaced are shown in bold. More specifically, from the initial sequence AB, substitute rule 2 starting at position 1, to get the result BB. From BB, substitute rule 3, starting at position 1, to get the result AAB. From AAB, substitute rule 3, starting at position 3, to get the result AAAA. From AAAA, substitute rule 1, starting at position 3, to get the result AAAB, which is the final sequence.

Input Specification

The first three lines will contain the substitution rules. Each substitution rule will be a sequence of A’s and B’s, followed by a space following by another sequence of A’s and B’s. Both sequences will have between one and five symbols.

The next line contains three space separated values, $S$ , $I$ and $F$ . The value $S$ ( $1 \leq S \leq 15$ ) is an integer specifying the number of steps that must be used, and the values $I$ (the initial sequence) and $F$ (the final sequence) are sequences of A’s and B’s, where there are at least one and at most 5 symbols in $I$ and at least one and at most 50 symbols in $F$ .

For 7 of the 15 marks available, $S \leq 6$ .

For an additional 7 of the 15 available marks, $S \leq 12$ .

Output Specification

The output will be $S$ lines long and describes the substitutions in order.

Line $i$ of the output will contain three space-separated values, $R_{i}$ , $P_{i}$ , and $W_{i}$ :

$R_{i}$ is the substitution rule number (either 1, 2 or 3) that will be used.
$P_{i}$ is the starting position index of where the substitution rule will be applied in the sequence. Notice that the string is 1-indexed (i.e., the first character of the string is at index 1).
$W_{i}$ is the sequence that results from this substitution. Specifically, $W_{i}$ is the sequence of symbols that results by applying substitution rule $R_{i}$ starting at position $P_{i}$ from the previous sequence of symbols, $W_{i - 1}$ , where we define $W_{0}$ to be the initial sequence $I$ . Note that $W_{S} = F$ , the final sequence.

There will always be at least one sequence of $S$ substitutions that will convert $I$ into $F$ . If there is more than one possible sequence of substitutions, any valid sequence will be accepted.

Sample Input

AA AB
AB BB
B AA
4 AB AAAB

Possible Output for Sample Input

2 1 BB
3 1 AAB
3 3 AAAA
1 3 AAAB

Explanation of Output for Sample Input

This is the example outlined in the problem description. Note that the following is another possible valid substitution sequence:

2 1 BB
3 2 BAA
1 2 BAB
3 1 AAAB

Specifically, showing the substitutions in bold, we get

\to

\to

BAA

\to

BAB

\to

AAAB.

2019 Canadian Computing Competition Junior Problems

Problem J1: Winning Score

Problem Description

Input Specification

Output Specification

Sample Input 1

Output for Sample Input 1

Explanation of Output for Sample Input 1

Input for Sample Input 2

Output for Sample Input 2

Explanation of Output for Sample Input 2

Problem J2: Time to Decompress

Problem Description

Input Specification

Output Specification

Sample Input

Output for Sample Input

Problem J3: Cold Compress

Problem Description

Input Specification

Output Specification

Sample Input

Output for Sample Input

Explanation of Output for Sample Input

Problem J4/S1: Flipper

Problem Description

Input Specification

Output Specification

Sample Input 1

Output for Sample Input 1

Sample Input 2

Output for Sample Input 2

Problem J5: Rule of Three

Problem Description

Input Specification

Output Specification

Sample Input

Possible Output for Sample Input

Explanation of Output for Sample Input

2019 Canadian Computing Competition
Junior Problems