You are hereProgramming Problems / 2015 AIPO Preliminary Round Problems

2015 AIPO Preliminary Round Problems


By gconway - Posted on 04 January 2015

You are strongly encouraged to complete these problems on your own without help or using the Internet. Problems in the Final Round of the competition will be more difficult than these.

Your program should not prompt for input from the user. It should read from the standard input and output to the standard output, e.g.:

$ echo 'AB' | q4
$ 3
$ q4 < input.txt
$ 3
$ cat input.txt
$ AB

 

 

Q1 - Manhattan

ManhattanDistanceImageThe island of Manhattan in New York has a grid-like network of streets, where taxis have to travel in a rectilinear fashion along the north, south, east and west cardinal directions. The distance from one intersection to another is often called the taxicab distance or manhattan distance. This form of geometry was first considered by Hermann Minkowski in 19th century Germany.

Suppose Manhattan is a 100km x 100km grid of streets with street blocks measuring 1km x 1km. If someone was waiting for a taxi at the (x,y) intersection of (0,0) and the only taxi in Manhattan is at an (x,y) intersection of (100,100), the manhattan distance between them is 200km. Vice versa, if the person is waiting at the (x,y) intersection of (100,100) and the taxi was at (0,0), the manhattan distance would still be 200km.

Of course there are hundreds of taxis in Manhattan. Output the closest taxi to the intersection you are waiting at in Manhattan.

Input

The first line of the input will be the (x,y) intersection that you are waiting at for a taxi. The second line has a single integer N (1<=N<=100) of the number of available taxis in Manhattan. The next N lines will be the (x,y) positions of taxis around Manhattan. Taxis will always be at the intersections of streets and there will only be one taxi per intersection. All taxis will be at different manhattan distances from you.

Output

The position of the closest taxi to you.

Sample input
 
1 1
3
0 5
2 2
4 3
 
Sample output
 
2 2
 
Sample input
 
41 77
3
19 81
51 92
30 65
 
Sample output
 
30 65

 

Q2 - Matches

Young Sean threw matches all over the floor of his room.

His mum did not like that and ordered him to put all the matches in a box. Sean soon noticed that not all of the matches on the floor fit in the box, so he decided to take the matches that don't fit and throw them in the neighbour's garbage, where his mum (hopefully) won't find them.

Help Sean determine which of the matches fit in the box his mom gave him. A match fits in the box if its entire length can lie on the bottom of the box. Sean examines the matches one by one.

Input

The first line of input contains an integer N (1 ≤ N ≤ 50), the number of matches on the floor, and two integers W and H, the dimensions of the box (1 ≤ W ≤ 100, 1 ≤ H ≤ 100).

Each of the following N lines contains a single integer between 1 and 1000 (inclusive), the length of one match.

Output

For each match, in the order they were given in the input, output on a separate line "YES" if the match fits in the box or "NO" if it does not.

Sample input
 
5 3 4
3
4
5
6
7 
 
Sample output
 
YES
YES
YES
NO
NO
 
Sample input
 
2 12 17
21
20
 
Sample output
 
NO
YES

 

Q3 - Sodium

After failing his chemistry exam, Aodhan (foolishly) decided to get his own back on his teacher and show him just how good he is at science.

He hides a contraption that he made at home into a cupboard behind his chemistry teacher's desk. It consists of a raspberry pi controlling a mechanical arm which will drop a piece of sodium into a cup of water at the precise time his teacher starts one of his lessons. He will enter the time of the 'explosion' into his raspberry pi program which will tell the mechanical arm to drop the sodium into the water after the time is up.

Aodhan know the current time and when he wants the explosion, but maths is (also) not one of his strong points. Write a program for Aodhan that calculates the time to the explosion (this is the time that Aodhan will enter into his raspberry pi program). The time Aodhan wants is at least one second and at most 24 hours.

Input

The first line of the input contains the current time in hh:mm:ss format (hours, minutes, seconds). The hours will be between 0 and 23 (inclusive) and the minutes and seconds between 0 and 59.

The second line contains the time of the explosion in the same format.

Output

Output the desired time on a single line, in the same format as the times in the input.

Sample input
 
20:00:00
04:00:00
 
Sample output
 
08:00:00
 
Sample input
 
12:34:56
14:36:22
 
Sample output
 
02:01:26

 

Q4 - Chop Cup

Oisín is amateur magician and is big fan of Chop Cup routine which involves three cups face down and one ball underneath one of the cups. He's only started to practice the trick and wants to test out if you can follow where the ball is without any tricks or slight of hand. 

The ball starts under the leftmost cup and Oisín then swaps two cups in one of three possible ways a number of times.

ChopCupMoves

What Oisin doesn't realise is that you are recording the moves with your phone using the letters A, B or C and  are going to use a simple program to determine where the ball is. Write that program.

Input

The first and only line contains a string of at most 50 characters, Oisín's moves.

Each of the characters is 'A', 'B' or 'C' (without quote marks).

Output

Output the index of the cup under which the ball is: 1 if it is under the left cup, 2 if it is under the middle cup or 3 if it is under the right cup.

Sample input
 
AB
 
Sample output
 
3
 
Sample input
 
CBABCACCC
 
Sample output
 
1

 

Q5 - Divisors

Given an integer n, compute the number of divisors of n.

A divisor is an integer, d (1 <= d <= n) that evenly divides n.

Example: If n=10, divisors are: 1, 2, 5 and 10. So the result would be 4.

Example: If n=104717, divisors are 1 and 104717. This is a prime number so the number of divisors is 2.

Input

The first line contains an integer C (1 <= C <= 10) with the amount of numbers you need to process. The next C lines will contain an integer n (1 <= n < 10000) each. You have to compute the number of divisors of these values.

Output

For each integer n, print a line with the number n itself, a space and the number of divisors.

Sample input
 
10
1
2
3
4
5
9999
31
10
20
1047
 
Sample output
 
1 1
2 2
3 2
4 3
5 2
9999 12
31 2
10 4
20 6
1047 4

 

Q6 - Divisors Again

Count the divisors of every value in the range [L, U] (both L and U included) and return the biggest divisor count you can find.

Input

The first line will contain an integer C with the number of ranges to process. The next C lines will contain a pair of integers L, U.

You have to count the divisors for each number in the range and output the biggest count.

Constraints

1 <= C <= 10
L <= U
1 <= L, U <= 10000000
0 <= U - L <= 1000

Output

For each range a line containing the biggest divisor count found.

Sample input
 
5
1 10
1000 1000
9999900 10000000
35 999
25 25
 
Sample output
 
4
16
256
32
3

 

 
AttachmentSize
AIPO2015-Prelim-testcases.zip25.6 KB