You are hereProgramming Problems / 2016 AIPO Preliminary Round Problems
2016 AIPO Preliminary Round Problems
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 'true AND true'  p1 $ true $ p1 < input.txt $ true $ cat input.txt $ true AND true
Table of contents
Problem 1  George Boole
George Boole was an English mathematician, educator, philosopher who was born in 1815, 200 years ago. He was the first professor of mathematics at Queen's College, Cork (now University College Cork (UCC)) and is known as the inventor of boolean arithmetic: The field that is the basis of today’s computers.
In boolean arithmetic, instead of infinite numbers we only have 2 values: 0/1, true/false, yes/no, etc. We will use the values true and false in this problem. The two most common operations in boolean arithmetic are AND and OR.
The result of an AND operation is true only if both elements are true. Examples:
true AND true = true
true AND false = false
false AND false = false
The result of an OR operation is true if any of the elements are true. Examples:
true OR true = true
false OR false = false
false OR true = true
In this problem you’ll read one of such operations and write the correct result.
Input
Read a single line from the standard input. The line will contain three words with the format:
value1 operation value2. The fields value1 and value2 will be either true or false. The field operation will be either AND or OR.
Output
Print either true or false.
Test your program with the following examples. We you execute your solution with the input example, the result should be exactly equal to the output example.
Input example 1
true AND true

Output example 1
true

Input example 2
true OR true

Output example 2
true

Input example 3
true AND false

Output example 3
false

Input example 4
false OR true

Output example 4
true

Input example 5
false AND false

Output example 5
false

Input example 6
false OR false

Output example 6
false

Problem 2  Palindromes
Write a program that reads a word and print “true” if the word is a palindrome or “false” otherwise.
A word is palindrome if it reads the same backward and forward. Examples:
ada is a palindrome
aabbaa is a palindrome
pizza is not a palindrome
Your task is to write program that checks if a word is a palindrome or not.
Input
Your program must read a single word. The word’s length will be at most 20 and will only have lowercase latin letters.
Output
Print “true” if the word is a palindrome or “false” otherwise.
Input example 1
a

Output example 1
true

Input example 2
uu

Output example 2
true

Input example 3
owo

Output example 3
true

Input example 4
bbbbbbbbbbb

Output example 4
true

Input example 5
zzzzzzzzo

Output example 5
false

Input example 6
slakdjfims

Output example 6
false

Problem 3  Collatz Conjecture
The Collatz conjecture is a conjecture in mathematics named after Lothar Collatz, who first proposed it in 1937 and is still an open problem in mathematics. The sequence of numbers involved is referred to as the hailstone sequence or hailstone numbers (because the values are usually subject to multiple descents and ascents like hailstones in a cloud. The conjecture is that no matter what number you start with, you will always eventually reach 1. The property has also been called oneness.
The computation (also known as 3n + 1) is stated as follows:
 We have an integer number n.
 If n == 1: stop
 If n is even: divide the number by 2. Then go to step 1
 If n is odd: multiply by 3 and add 1. Then go to step 1
As the conjecture states, you repeat this steps for any positive integer you will eventually end up with n = 1. The values we find define a sequence from n to 1.
For example, if we start with n = 14.
 14 is even so the new value will be 7 (14/2)
 7 is odd so the new value will be 22 (3*7 + 1)
 22 is even so the new value will be 11 (22/2)
 11 is odd so the new value will be 34 (3*11 + 1)
 34 is even so the new value will be 17
If we continue until we have a value of 1, the final sequence will be:
14, 7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1
Your task is to write a program that, given the starting point n, prints the whole Collatz sequence for this value.
Input
A integer value n. The value of n will be between 1 and 100000.
Output
Print the Collatz sequence with the elements separated by a single space. Do not add any space at the beginning or the end of the line.
Input example 1
14

Output example 1
14 7 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1

Input example 2
1

Output example 2
1

Input example 3
64

Output example 3
64 32 16 8 4 2 1

Problem 4  Binary tree
A binary tree is a mathematical structure made of nodes where each node can have up to two children nodes. One child node will be called left child and the other right child. ch If node B is a child node of A, then we say that A is the parent node of B. In a binary tree, there is only one node that has no parent and we call this node the root of the tree. We call the height of a node N to the distance in nodes between the node N and the root node. The root node’s height is 0.
In this problem, you’ll have to compute the heights of every node of the tree. Each node will be identified by an integer from 1 to the number of nodes n.
Check the following tree:
The root of the tree is 1. The left child of 1 is 2, the right child of 1 is 3.
The nodes 4, 5, 6 and 7 do not have any child.
The heights of the nodes are:
 Node 1: 0
 Nodes 2 and 3: 1
 Nodes 4, 5, 6 and 7: 2
The following tree is a bit different:
Node 1 is still the root and has 2 and 3 as left and right children but 3 only have right child. On the contrary, node 4 only has left child (5).
The heights:
 Node 1: 0
 Nodes 2 and 3: 1
 Node 4: 2
 Node 5: 3
Input
The first line of the input will contain the number of nodes n.
The following n lines will contain one integer each representing the parent of a node. That is, the second line of the input will contain the parent of node 1, the third line the parent of node 2, etc.
The root node will be identified by 1. Remember that node 1 won’t always be the root node.
Output
Print n lines. The first line should be the height of node 1, the second should be the height of node 2, and so on.
Limits
1 ≤ n ≤ 20
Input example 1
7
1
1
1
2
2
3
3

Output example 1
0
1
1
2
2
2
2
This is the first tree of the problem statement.

Input example 2
5
1
1
1
3
4

Output example 2
0
1
1
2
3
The second tree of the problem statement.

Input example 3
3
2
1
2

Output example 3
1
0
1

Problem 5  Bitcoin investment
Bitcoin is a digital asset and a payment system invented by Satoshi Nakamoto. It is not known whether the name "Satoshi Nakamoto" is real or a pseudonym, or whether the name represents one person or a group of people. It was once rumoured by New Yorker Magazine to be a pseudonym for one of our exAIPO finalists, Michael Clear, but he has always strongly denied it.
The value of a bitcoin in euros keeps changes fast. One day a bitcoin may cost 800 euros and two days later go down to 20 euros.
Let’s suppose we know all the future exchange rates of bitcoin to euros and we want to maximize our investment. We don’t have any bitcoin at the beginning. We want to buy one bitcoin and then sell it later. The difference between the buying cost and the selling price will be our benefit (or loss).
Example: these are the cost in euros of a single bitcoin for the next 10 days.
Day  1  2  3  4  5  6  7  8  9  10 
Price  5  11  4  2  8  10  7  4  3  6 
We could buy a bitcoin on day 1 for 5 euros and sell in on day 2 for 11 and we would have a benefit of 6 euros. But, if we instead buy a bitcoin on day 4 (for 2 euros) and sell it on day 6 (for 10 euros) our benefit would be 8 euros. 8 euros is the maximum benefit we can get with these rates.
Your task: given a list of exchange rates. Compute the maximum benefit we can obtain. We can only buy once and sell once. Of course, we must buy before selling. It is possible to buy and sell the same day to get a benefit of 0.
Input
The first line will contain an integer n representing the number of exchange rates.
The second line will contain n integers from 1 to 10000 representing the exchange rate for the following n days. The number of rates will be at most 100000 (105).
Output
Write the maximum benefit you could obtain.
Input example 1
10
5 11 4 2 8 10 7 4 3 6

Output example 1
8
Buy for 2 and then sell for 10.

Input example 2
1
5

Output example 2
0
Buy and sell for 5.

Problem 6  Combinations
When we have a set of n elements from which we take k elements, we have a combination.
For example, if we have a set with the numbers from 1 to 5, we have the following different combinations:
 1combinations (1 element from the set each time): (1), (2), (3), (4), (5)
 2combinations (2 elements from the set each time): (1, 2), (1, 3), (1, 4), (1, 5), (2, 3), (2, 4), (2, 5), (3, 4), (3, 5), (4, 5).
 3combinations (3 elements from the set each time): (1, 2, 3), (1, 2, 4), (1, 2, 5), (1, 3, 4), (1, 3, 5), (1, 4, 5), (2, 3, 4), (2, 3, 5), (2, 4, 5), (3, 4, 5),
 4combinations (4 elements from the set each time): (1, 2, 3, 4), (1, 3, 4, 5), (1, 2, 4, 5), (1, 2, 3, 5), (2, 3, 4, 5)
 5combination (all the elements at once): (1, 2, 3, 4, 5)
 0combination (no element): ()
The following formula will give us the number of kcombinations of n elements:
As we saw in the list before
 (5 over 0) = 1
 (5 over 1) = 5
 (5 over 2) = 10
 (5 over 3) = 10
 (5 over 4) = 5
 (5 over 5) = 1
Your task is to compute several (n over k) operations.
Input
A line with an integer t. The following t lines will contain 2 integers each separated by spaces. The first value will be n and second k.
Output
For each (n k) pair. Compute the number of kcombinations of a set of size n. Compute the results modulo 1000000007 (10^9 + 7).
Limits
 1 ≤ t ≤ 1000
 1 ≤ n ≤ 1000
 0 ≤ k ≤ n
Input example 1
6
5 0
5 1
5 2
5 3
5 4
5 5

Output example 1
1
5
10
10
5
1

Input example 2
3
123 54
7 4
20 10

Output example 2
757228090
35
184756
