You are hereProgramming Problems / 2014 AIPO Preliminary Round Problems

2014 AIPO Preliminary Round Problems


By gconway - Posted on 03 January 2014

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 '11 15' | q1
$ 19
$ q1 < input.txt
$ 19
$ cat input.txt
$ 11 
$ 15

 

 

Q1 - Christmas Money

The number X is called the average of two numbers M1 and M2 if X is equal to (M1+M2)/2.

Brother's Sean and Michael would always get some money from their Uncle in America for Christmas. Being good brothers they would always average out the money between them. Being the eldest brother Sean would take care of this transaction. He would take Micheal's money, go off and calculate the average and return with Michael's averaged Christmas money. As the year's went on Micheal was curious to know how much older brother Sean was getting from his Uncle. He knew how much cash he received from his uncle and the average that Sean returned to him. Help Michael determine how much Christmas money Sean gets from his uncle.

Input:

The first line of the standard input contains the integer M1 and the second line of the standard input contains the integer X, both between 0 and 1000.

Output:

Output M2 on a single line.

Your program should be named one of the following depending on the language used:

q1.c,  q1.cpp,  q1.java,  q1.php,  q1.py,  q1.pl, q1.hs

Sample input:

11
15

Sample output:

19

 

Q2 - Small Factorials

In the 12th century, Indian scholars determined that the number of distinct ways to arrange n integers in a sequence is actually the product of all the postive integers less than or equal to n. In mathematics, this is called the factorial and is denoted by n!. For example,

5! = 5  *  4  *  3  *  2  *  1 = 120.  

You are asked to calculate factorials of some small positive integers.

Input: 

An integer t, 1<=t<=20, denoting the number of testcases, followed by t lines, each containing a single integer n, 0<=n<=20.

Output: 

For each integer n given at input, display a line with the value of n! ("n factorial").

Your program should be named one of the following depending on the language used:

q2.c,  q2.cpp,  q2.java,  q2.php,  q2.py,  q2.pl, q2.hs

Sample input:

4
1
2
5
3

Sample output:

1
2
120
6

 

Q3 - Data Delete

John is the computer expert at his company and has now been tasked to find some software for deleting data properly. It is very important that the data should not be recoverable afterwards, so it should be overwritten on the hard drive several times. Unable to find any free program up to the task, John decides to write such a program himself.

The user interface is simple, it only asks for the file to be destroyed and N, the number of times it should be overwritten. This number can range from 1 (quick deletion) to 20 (maximum security). John processes the file bit by bit and does not consider writing a zero where there was already a zero as really overwriting. So for each of the n sweeps, he overwrites each zero with a one and each one with a zero.

John knows that independent testing is important, so he has asked you to write the verification routine as he knows you are a budding computer scientist. He will not listen to your objections to the algorithm so eventually you give in.

Input:

The first line of the input contains a single integer 1<=N<=20. The two following lines each contain a string containing only the characters 0 and 1. The first of these lines represent the bits of the file before deletion and the second the bits on the same position on the hard drive after the file has been deleted. The length of these strings are the same and between 1 and 1000 characters.

Output:

Output a single line containing either the words "Deletion succeeded” if each bit is switched N times or “Deletion failed” if this is not the case.

Your program should be named one of the following depending on the language used:

q3.c,  q3.cpp,  q3.java,  q3.php,  q3.py,  q3.pl, q3.hs

Sample input1:

1
10001110101000001111010100001110
01110001010111110000101011110001

Sample output1:

Deletion succeeded

Sample input2:

20
0001100011001010
0001000011000100

Sample output2:

Deletion failed

 

Q4 - Palindrome Sums

Liam was getting really bored during his Math class, and so his teacher asked him to solve some additional problems. Liam was given an assignment sheet with some numbers written on it. Liam’s task is to figure out if the given number is a palindrome, i.e., a number which stays the same when read from left to right or from right to left. If not, Liam should add the value of the number read from left to right and its value read from right to left, and check if the obtained sum is a palindrome. If not, he should continue the process, until he eventually obtains a palindrome.

For instance, given the number 37, Liam will come to the conclusion that it is not a palindrome and so he will perform the addition: 37 + 73 = 110. The number 110 is not a palindrome, either, so he will proceed to perform another sum: 110 + 011 = 110 + 11 = 121. The obtained result is a palindrome, so Liam’s work is done.

Your task is to write a program which, for each of the numbers considered by Liam, will print the palindrome he eventually obtains, as well as the number of addition operations leading to this result.

Input: 

The first line of input contains an integer t (t <= 10), which corresponds to the number of problems Liam was asked to solve. Each of the next t lines contains exactly one integer n (1 <= n <= 100), for which Liam should perform his calculations.

Output

For each of the numbers given at input, print one line containing two integers, separated by a space. The first should be the palindrome obtained by Liam, while the second - the number of addition operations required to obtain it.

Your program should be named one of the following depending on the language used:

q4.c,  q4.cpp,  q4.java,  q4.php,  q4.py,  q4.pl, q4.hs

Sample input:

3
5
11
37

Sample output:

5 0
11 0
121 2

 

Q5 - Trees

Farmer Joe loves trees. He has recently bought n tree seedlings that he wants to plant in his yard. It takes 1 day for Joe to plant a seedling1, and for each tree Joe knows exactly in how many days after planting it grows to full maturity. Joe would also like to throw a party for his farmer friends, but in order to impress them he would like to organise the party only after all the trees have grown. More precisely, the party can be organised at the earliest on the next day after the last tree has grown up.

Help Joe to find out when is the earliest day when the party can take place. Joe can choose the order of planting the trees as he likes, so he wants to plant the trees in such a way that the party will be as soon as possible.

Input:

The input consists of two lines. The first line contains a single integer, N (1 <= N <= 100 000) denoting the number of seedlings. Then a line with N integers ti follows (1 <=  ti <= 1 000 000), where ti denotes the number of days it takes for the ith tree to grow.

Output:

Your program should output exactly one line containing one integer, denoting the earliest day when the party can be organised. The days are numbered 1,2,3,... beginning from the current moment.

Your program should be named one of the following depending on the language used:

q5.c,  q5.cpp,  q5.java,  q5.php,  q5.py,  q5.pl, q5.hs

Sample input1:

4
2 3 4 3

Sample output1:

7

Sample input2:

6
39 38 9 35 39 20

Sample output2:

42

 

1 - Joe likes his tea breaks!

 

Q6 - Ants

Ants are funny creatures.

When moving, they form rows so that each ant except the first is behind another ant. But it is not widely known what happens when two rows of ants moving in opposite directions run into each other in a passage too narrow for both rows to pass through. One theory says that, in that situation, ants will jump over each other.

From the moment the rows meet, each second every ant jumps over (or gets jumped over, as they agree upon) the ant in front of himself so that the two ants swap places, but only if the other ant is moving in the opposite direction. Find the order of the ants after T seconds.

Input:

The first line contains two integers N1 and N2, the numbers of ants in the first and second rows, respectively.

The next two rows contain the orders of ants in the first and second row (first to last). Each ant is uniquely determined by an uppercase letter of the alphabet (this letter is unique between both rows)

The last line of input contains the integer T (0 ≤ T ≤ 50).

Output:

Output the order of the ants after T seconds on a single line. Our viewpoint is such that the first row of ants comes from our left side and the other one from our right side.

Your program should be named one of the following depending on the language used:

q6.c,  q6.cpp,  q6.java,  q6.php,  q6.py,  q6.pl, q6.hs

Sample input1:

3 3
ABC
DEF
0

Sample output1:

CBADEF

Sample input2:

3 3
ABC
DEF
2

Sample output2:

CDBEAF

Sample input3:

3 4
JLA
CRUO
3

Sample output3:

CARLUJO