2017 Canadian Computing Competition
Junior Problems

Problem J1: Quadrant Selection

Time limit: 1 second

Problem Description

A common problem in mathematics is to determine which quadrant a given point lies in. There are four quadrants, numbered from 1 to 4, as shown in the diagram below:

For example, the point A, which is at coordinates (12, 5) lies in quadrant 1 since both its $x$ and $y$ values are positive, and point $B$ lies in quadrant 2 since its $x$ value is negative and its $y$ value is positive.

Your job is to take a point and determine the quadrant it is in. You can assume that neither of the two coordinates will be $0$.

Input Specification

The first line of input contains the integer $x$ $(-1000\le x\le 1000;x\ne 0)$. The second line of input contains the integer $y$ $(-1000\le y\le 1000;y\ne 0)$.

Output Specification

Output the quadrant number ($1$, $2$, $3$ or $4$) for the point $(x,y)$.

Sample Input 1

12
5

Output for Sample Input 1

1

Sample Input 2

9
-13

Output for Sample Input 2

4

Problem J2: Shifty Sum

Time limit: 1 second

Problem Description

Suppose we have a number like 12. Let’s define shifting a number to mean adding a zero at the end. For example, if we shift that number once, we get the number 120. If we shift the number again we get the number 1200. We can shift the number as many times as we want.

In this problem you will be calculating a shifty sum, which is the sum of a number and the numbers we get by shifting. Specifically, you will be given the starting number $N$ and a non-negative integer $k$. You must add together $N$ and all the numbers you get by shifting a total of $k$ times.

For example, the shifty sum when $N$ is 12 and $k$ is 1 is: $12+120=132$. As another example, the shifty sum when $N$ is 12 and $k$ is 3 is $12+120+1200+12000=13332$.

Input Specification

The first line of input contains the number $N$ $(1\le N\le 10000$). The second line of input contains $k$, the number of times to shift $N$ $(0\le k\le 5)$.

Output Specification

Output the integer which is the shifty sum of $N$ by $k$.

Sample Input

12
3

Output for Sample Input

13332

Problem J3: Exactly Electrical

Time limit: 1 second

Problem Description

You live in Grid City, which is composed of integer-numbered streets which run east-west (parallel to the $x$-axis) and integer-numbered avenues which run north-south (parallel to the $y$-axis). The streets and avenues have infinite length, and there is a street for every integer $y$-coordinate and an avenue for every $x$-coordinate. All intersections are labelled by their integer coordinates: for example, avenue 7 and street -3 intersect at (7,-3).

You drive a special electric car which uses up one unit of electrical charge moving between adjacent intersections: that is, moving either north or south to the next street, or moving east or west to the next avenue). Until your battery runs out, at each intersection, your car can turn left, turn right, go straight through, or make a U-turn. You may visit the same intersection multiple times on the same trip.

Suppose you know your starting intersection, your destination intersection and the number of units of electrical charge in your battery. Determine whether you can travel from the starting intersection to the destination intersection using the charge available to you in such a way that your battery is empty when you reach your destination.

Input Specification

The input consists of three lines. The first line contains $a$ followed by $b$, indicating the starting coordinate $(a,b)$ $(-1000\le a\le 1000;-1000\le b\le 1000)$.

The second line contains $c$ followed by $d$, indicating the destination coordinate $(c,d)$ $(-1000\le c\le 1000;-1000\le d\le 1000)$.

The third line contains an integer $t$ $(0\le t\le 10000)$ indicating the initial number of units of electrical charge of your battery.

For 3 of the 15 available marks, $0\le a,b,c,d\le 2$.

For an additional 3 of the 15 marks available, $t\le 8$.

Output Specification

Output Y if it is possible to move from the starting coordinate to the destination coordinate using exactly $t$ units of electrical charge. Otherwise output N.

Sample Input 1

3 4
3 3
3

Output for Sample Input 1

Y

Explanation for Output for Sample Input 1

One possibility is to travel from $(3,4)$ to $(4,4)$ to $(4,3)$ to $(3,3)$.

Sample Input 2

10 2
10 4
5

Output for Sample Input 2

N

Explanation for Output for Sample Input 2

It is possible to get from $(10,2)$ to $(10,4)$ using exactly 2 units of electricity, by going north 2 units.

It is also possible to travel using 4 units of electricity as in the following sequence: $$(10,2)\to (10,3)\to (11,3)\to (11,4)\to (10,4).$$ It is also possible to travel using 5 units of electricity from $(10,2)$ to $(11,4)$ by the following sequence: $$(10,2)\to (10,3)\to (11,3)\to (12,3)\to (12,4)\to (11,4).$$ It is not possible to move via any path of length 5 from $(10,2)$ to $(10,4)$, however.

Problem J4: Favourite Times

Time limit: 1 second

Problem Description

Wendy has an LED clock radio, which is a 12-hour clock, displaying times from 12:00 to 11:59. The hours do not have leading zeros but minutes may have leading zeros, such as 2:07 or 11:03.

When looking at her LED clock radio, Wendy likes to spot arithmetic sequences in the digits. For example, the times 12:34 and 2:46 are some of her favourite times, since the digits form an arithmetic sequence.

A sequence of digits is an arithmetic sequence if each digit after the first digit is obtained by adding a constant common difference. For example, 1,2,3,4 is an arithmetic sequence with a common difference of 1, and 2,4,6 is an arithmetic sequence with a common difference of 2.

Suppose that we start looking at the clock at noon (that is, when it reads 12:00) and watch the clock for some number of minutes. How many instances are there such that the time displayed on the clock has the property that the digits form an arithmetic sequence?

Input Specification

The input contains one integer $D$ $(0\le D\le 1000000000)$, which represents the duration that the clock is observed.

For 4 of the 15 available marks, $D\le 10000$.

Output Specification

Output the number of times that the clock displays a time where the digits form an arithmetic sequence starting from noon (12:00) and ending after $D$ minutes have passed, possibly including the ending time.

Sample Input 1

34

Output for Sample Input 1

1

Explanation of Output for Sample Input 1

Between 12:00 and 12:34, there is only the time 12:34 for which the digits form an arithmetic sequence.

Sample Input 2

180

Output for Sample Input 2

11

Explanation of Output for Sample Input 2

Between 12:00 and 3:00, the following times form arithmetic sequences in their digits (with the difference shown:

• 12:34 (difference 1),

• 1:11 (difference 0),

• 1:23 (difference 1),

• 1:35 (difference 2),

• 1:47 (difference 3),

• 1:59 (difference 4),

• 2:10 (difference -1),

• 2:22 (difference 0),

• 2:34 (difference 1),

• 2:46 (difference 2),

• 2:58 (difference 3).

Problem J5: Nailed It!

Time limit: 2 seconds

Problem Description

Tudor is a contestant in the Canadian Carpentry Challenge (CCC). To win the CCC, Tudor must demonstrate his skill at nailing wood together to make the longest fence possible using boards. To accomplish this goal, he has $N$ pieces of wood. The $i^{th}$ piece of wood has integer length $L_i$.

A board is made up of exactly two pieces of wood. The length of a board made of wood with lengths $L_i$ and $L_j$ is $L_i+L_j$. A fence consists of boards that are the same length. The length of the fence is the number of boards used to make it, and the height of the fence is the length of each board in the fence. In the example fence below, the length of the fence is 4; the height of the fence is 50; and, the length of each piece of wood is shown:

Input Specification

The first line will contain the integer $N$ $(2\le N\le 1000000)$.
The second line will contain $N$ space-separated integers $L_1,L_2,\dots ,L_N$ $(1\le L_i\le 2000)$.

For 7 of the 15 available marks, $N\le 100$.
For an additional 6 of the 15 available marks, $N\le 1000$.
For an additional 1 of the 15 available marks, $N\le 100000$.

Output Specification

Output two integers on a single line separated by a single space: the length of the longest fence and the number of different heights a longest fence could have.

Sample Input 1

4
1 2 3 4

Output for Sample Input 1

2 1

Explanation for Output for Sample Input 1

Tudor first combines the pieces of wood with lengths $1$ and $4$ to form a board of length $5$. Then he combines the pieces of wood with lengths $2$ and $3$ to form another board of length $5$. Finally, he combines the boards to make a fence with length $2$ and height $5$.

Sample Input 2

5
1 10 100 1000 2000

Output for Sample Input 2

Explanation for Output for Sample Input 2

Tudor can’t make a fence longer than length $1$, and there are $10$ ways to make a fence with length $1$ by choosing any two pieces of wood to nail together. Specifically, he may have a fence of height 11, 101, 1001, 2001, 110, 1010, 2010, 1100, 2100 and 3000.