2021 Canadian Computing Competition
Junior Problems
Junior Problems
At sea level, atmospheric pressure is 100 kPa and water begins to boil at 100°C. As you go above sea level, atmospheric pressure decreases, and water boils at lower temperatures. As you go below sea level, atmospheric pressure increases, and water boils at higher temperatures. A formula relating atmospheric pressure to the temperature at which water begins to boil is \[P = 5 \times B - 400\] where \(P\) is atmospheric pressure measured in kPa, and \(B\) is the temperature at which water begins to boil measured in °C.
Given the temperature at which water begins to boil, determine atmospheric pressure. Also determine if you are below sea level, at sea level, or above sea level.
Note that the science of this problem is generally correct but the values of 100°C and 100 kPa are approximate and the formula is a simplification of the exact relationship between water’s boiling point and atmospheric pressure.
The input is one line containing an integer \(B\) where \(B \geq 80\) and \(B \leq 200\). This represents the temperature in °C at which water begins to boil.
-1, 0, or
1. This integer represents whether you are
below sea level, at sea level, or above sea level, respectively.
99
95
1When \(B=99\), we can substitute into the formula and get \(P= 5 \times 99 - 400\) which equals \(95\). Since 95 kPa is less than 100 kPa, you are above sea level.
102
100
-1When \(B=102\), we can substitute into the formula and get \(P=5 \times 102 - 400\) which equals \(110\). Since 110 kPa is greater than 100 kPa, you are below sea level.
A charity is having a silent auction where people place bids on a prize without knowing anyone else’s bid. Each bid includes a person’s name and the amount of their bid. After the silent auction is over, the winner is the person who has placed the highest bid. If there is a tie, the person whose bid was placed first wins. Your job is to determine the winner of the silent auction.
The first line of input contains a positive integer \(N\), where \(1 \leq N \leq 100\), representing the number of bids collected at the silent auction. Each of the next \(N\) pairs of lines contains a person’s name on one line, and the amount of their bid, in dollars, on the next line. Each bid is a positive integer less than \(2000\). The order of the input is the order in which bids were placed.
Output the name of the person who has won the silent auction.
3
Ahmed
300
Suzanne
500
Ivona
450Suzanne
The highest bid placed was 500 and it was placed by Suzanne. Suzanne wins the silent auction.
2
Ijeoma
20
Goor
20Ijeoma
The highest bid placed was 20 and it was placed by both Ijeoma and Goor. Since Ijeoma’s bid was placed first, Ijeoma wins the silent auction.
Each instruction is a sequence of five digits which represents a direction to turn and the number of steps to take.
The first two digits represent the direction to turn:
If their sum is odd, then the direction to turn is left.
If their sum is even and not zero, then the direction to turn is right.
If their sum is zero, then the direction to turn is the same as the previous instruction.
The remaining three digits represent the number of steps to take which will always be at least 100.
Your job is to decode the instructions so the assistant can use them to find the secret formula.
There will be at least two lines of input. Each line except the last
line will contain exactly five digits representing an instruction. The
first line will not begin with 00. The last line will contain 99999 and no other line will contain 99999.
There must be one line of output for each line of input except the last line of input. These output lines correspond to the input lines (in order). Each output line gives the decoding of the corresponding
instruction: either right or
left, followed by a single space, followed by the number of steps to be taken in that direction.
57234
00907
34100
99999right 234
right 907
left 100The first instruction is 57234 which is decoded as right 234 because \(5 + 7 = 12\) which is even and
57 is followed by
234.
The second instruction is 00907 which is
decoded with the same direction as the previous instruction
(right) but with 907
steps.
The third instruction is 34100 which is decoded as left 100 because \(3 + 4 = 7\) which is odd and
34 is followed by
100.
The last line contains 99999 which tells us these are the only three instructions.
Valentina wants books on a shelf to be arranged in a particular way. Every time she sees a shelf of books, she rearranges the books so that all the large books appear on the left, followed by all the medium-sized books, and then all the small books on the right. She does this by repeatedly choosing any two books and exchanging their locations. Exchanging the locations of two books is called a swap.
Help Valentina determine the fewest number of swaps needed to arrange a shelf of books as she wishes.
The input will consist of exactly one line containing at least one character.
The following table shows how the available 15 marks are distributed.
| 7 marks | at most \(1000\) characters | each character will be
L or S |
| 2 marks | at most \(500\,000\) characters | each character will be
L or S |
| 4 marks | at most \(1000\) characters | each character will be
L, M, or
S |
| 2 marks | at most \(500\,000\) characters | each character will be
L, M, or
S |
Output a single integer which is equal to the minimum possible number of
swaps needed to arrange the books so that all occurrences of
L come first, followed by all occurrences of
M, and then all occurrences of
S.
LMMMS
0
The books are already arranged according to Valentina’s wishes.
LLSLM
2
By swapping the S and
M, we end up with
LLMLS. Then the M
can be swapped with the L to its right. This
is one way to use two swaps to arrange the books as Valentina wants them
to be. It is not possible to use fewer swaps because both
S and M need to be
moved but using one swap to exchange them does not leave the books
arranged as Valentina wants them to be.
A new and upcoming artist has a unique way to create checkered patterns. The idea is to use an \(M\)-by-\(N\) canvas which is initially entirely black. Then the artist repeatedly chooses a row or column and runs their magic brush along the row or column. The brush changes the colour of each cell in the row or column from black to gold or gold to black.
Given the artist’s choices, your job is to determine how much gold appears in the pattern determined by these choices.
The first line of input will be a positive integer \(M\). The second line of input will be a
positive integer \(N\). The third line
of input will be a positive integer \(K\). The remaining input will be \(K\) lines giving the choices made by the
artist. Each of these lines will either be R
followed by a single space and then an integer which is a row number, or
C followed by a single space and then an
integer which is a column number. Rows are numbered top down from \(1\) to \(M\). Columns are numbered left to right
from \(1\) to \(N\).
The following table shows how the available 15 marks are distributed.
| 1 mark | \(M = 1\) | \(N=1\) | \(K \leq 100\) | only one cell, and up to 100 choices by the artist |
| 4 marks | \(M = 1\) | \(N \leq 100\) | \(K \leq 100\) | only one row, and up to 100 choices by the artist |
| 5 marks | \(M \leq 100\) | \(N \leq 100\) | \(K \leq 100\) | up to 100 rows, up to 100 columns, and up to 100 choices by the artist |
| 5 marks | \(MN \leq 5\,000\,000\) | \(K \leq 1\,000\,000\) | up to 5000000 cells, and up to 1000000 choices by the artist | |
Output one non-negative integer which is equal to the number of cells that are gold in the pattern determined by the artist’s choices.
3
3
2
R 1
C 14
After running the brush along the first row, the canvas looks like this:
GGG
BBB
BBBThen after running the brush along the first column, four cells are gold in the final pattern determined by the artist’s choices:
BGG
GBB
GBB4
5
7
R 3
C 1
C 2
R 2
R 2
C 1
R 410
Ten cells are gold in the final pattern determined by the artist’s choices:
BGBBB
BGBBB
GBGGG
GBGGG