2019 Canadian Computing Competition
Senior Problems

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:

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:

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

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 S2: Pretty Average Primes

Problem Description

For various given positive integers $N>3$, find two primes, $A$ and $B$ such that $N$ is the average (mean) of $A$ and $B$. That is, $N$ should be equal to $(A+B)/2$.

Recall that a prime number is an integer $P>1$ which is only divisible by 1 and $P$. For example, $2,3,5,7,11$ are the first few primes, and $4,6,8,9$ are not prime numbers.

Input Specification

The first line of input is the number $T$ $(1\le T\le 1000)$, which is the number of test cases. Each of the next $T$ lines contain one integer $N_i$ $(4\le N_i\le 1000000,1\le i\le T)$.

For 6 of the available 15 marks, all $N_i<1000$.

Output Specification

The output will consist of $T$ lines. The $i$th line of output will contain two integers, $A_i$ and $B_i$, separated by one space. It should be the case that $N_i=(A_i+B_i)/2$ and that $A_i$ and $B_i$ are prime numbers.

If there are more than one possible $A_i$ and $B_i$ for a particular $N_i$, output any such pair. The order of the pair $A_i$ and $B_i$ does not matter.

It will be the case that there will always be at least one set of values $A_i$ and $B_i$ for any given $N_i$.

Sample Input

4
8
4
7
21

Possible Output for Sample Input

3 13
5 3
7 7
13 29

Explanation of Possible Output for Sample Input

Notice that: $$\begin{array}{rl}8& =(3+13)/2,\\ 4& =(5+3)/2,\\ 7& =(7+7)/2,\\ 21& =(13+29)/2.\end{array}$$ It is interesting to note, that we can also write $$\begin{array}{rl}8& =(5+11)/2\\ 21& =(5+37)/2=(11+31)/2=(19+23)/2\\ 7& =(3+11)/2\end{array}$$ and so any of these pairs could have also been used in output. There is no pairs of primes other than $3$ and $5$ which average to the value of $4$.

Footnote

You may have heard about Goldbach’s conjecture, which states that every even integer greater than 2 can be expressed as the sum of two prime numbers. There is no known proof, yet, so if you want to be famous, prove that conjecture (after you finish the CCC).

This problem can be used to help verify that conjecture, since every even integer can be written as $2N$, and your task is to find two primes $A$ and $B$ such that $2N=A+B$.

Problem S3: Arithmetic Square

Problem Description

You are given a $3\times 3$ grid which contains integers.

Some of the 9 elements in the grid will have a value already, and the remaining elements will be unspecified.

Your task is to determine values for the unspecified elements such that each row, when read from left-to-right is an arithmetic sequence, and that each column, when read from the top-down, is an arithmetic sequence.

Recall that an arithmetic sequence of length three is a sequence of integers of the form $$a,a+d,a+2d$$ for integer values of $a$ and $d$. Note that $d$ may be any integer, including zero or a negative integer.

Input Specification

The input will be 3 lines long. Each line will have three space-separated values. Each value will either be an integer in the range from $-1000000$ to $1000000$, inclusive, or the symbol X.

For 4 of the 15 marks available, there will be at most 3 X symbols in the input.

For an additional 3 of the 15 marks available, all integer values in the input will be between -10 and 10, inclusive.

For an additional 4 of the 15 marks available, there will be at least 7 X symbols in the input.

For an additional 2 of the 15 marks available, all integer values in the input will be even numbers.

Output Specification

The output will be 3 lines long. Each line will have three space-separated integers. All integers that were given in the input must be in their same position (i.e., same row and same column as in the input). All rows and columns must form arithmetic sequences. All integers in the output must be between -1 000 000 000 and 1 000 000 000, inclusive.

If there is more than one solution, output any solution. There is guaranteed to be at least one solution.

Sample Input 1

8 9 10
16 X 20
24 X 30

Output for Sample Input 1

8 9 10
16 18 20
24 27 30

Explanation of Output for Sample Input 1

Notice that the second element of the second row must be $16+t$ and since $20=16+2t$, then $t=2$, and thus, this unspecified element must be 18. A similar argument applies to the second element of the third row.

Sample Input 2

14 X X
X X 18
X 16 X

Possible Output for Sample Input 2

14 20 26
18 18 18
22 16 10

Explanation of Output for Sample Input 2

This is one of many possible solutions. For example, another solution is:

14 16 18
14 16 18
14 16 18

Problem S4: Tourism

Problem Description

You are planning a trip to visit $N$ tourist attractions. The attractions are numbered from $1$ to $N$ and must be visited in this order. You can visit at most $K$ attractions per day, and want to plan the trip to take the fewest number of days as possible.

Under these constraints, you want to find a schedule that has a nice balance between the attractions visited each day. To be precise, we assign a score $a_i$ to attraction $i$. Given a schedule, each day is given a score equal to the maximum score of all attractions visited that day. Finally, the scores of each day are summed to give the total score of the schedule. What is the maximum possible total score of the schedule, using the fewest days possible?

Input Specification

The first line contains two space-separated integers $N$ and $K$ $(1\le K\le N\le {10}^6)$.

The next line contains $N$ space separated integers $a_i$ $(1\le a_i\le {10}^9)$.

For 3 of the 15 available marks, $2K\ge N$.

For an additional 3 of the 15 available marks, $K\le 100$ and $N\le {10}^5$.

Output Specification

Output a single integer, the maximum possible total score.

Sample Input

5 3
2 5 7 1 4

Output for Sample Input

12

Explanation of Output for Sample Input

We need to have at least two days to visit all the attractions, since we cannot visit all attractions in one day.

Visiting the first two attractions on day 1 will give a score of 5, and visiting the last three attractions on day 2 will give a score of 7, for a total score of 12.

Visiting three attractions on day 1, and two attractions on day 2, which is the only possibility to visit in the fewest number of days possible, would yield a total score of $7+4=11$.

Problem S5: Triangle: The Data Structure

Problem Description

In a parallel universe, the most important data structure in computer science is the triangle. A triangle of size $M$ consists of $M$ rows, with the $i$-th row containing $i$ elements. Furthermore, these rows must be arranged to form the shape of an equilateral triangular. That is, each row is centered around a vertical line of symmetry through the middle of the triangle. For example, the diagram below shows a triangle of size 4:

A triangle contains sub-triangles. For example, the triangle above contains ten sub-triangles of size 1, six sub-triangles of size 2 (two of which are the triangle containing $(3,1,2)$ and the triangle containing $(4,6,1)$), three sub-triangles of size 3 (one of which contains $(2,2,1,1,4,2)$). Note that every triangle is a sub-triangle of itself.

You are given a triangle of size $N$ and must find the sum of the maximum elements of every sub-triangle of size $K$.

Input Specification

The first line contains two space-separated integers $N$ and $K$ $(1\le K\le N\le 3000)$.

Following this are $N$ lines describing the triangle. The $i$-th of these lines contains $i$ space-separated integers $a_{i,j}$ $(0\le a_{i,j}\le {10}^9)$, representing the $i$-th row of the triangle.

For 4 of the 15 available marks, $N\le 1000$.

Output Specification

Output the integer sum of the maximum elements of every sub-triangle of size $K$.

Sample Input

4 2
3
1 2
4 2 1
6 1 4 2

Output for Sample Input

23