You are hereProgramming Problems / 2017 AIPO Preliminary Round Problems
2017 AIPO Preliminary Round Problems
You are strongly encouraged to complete these problems on your own without help or using the Internet. Problems at the National Finals 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
For Python(2.7), please use raw_input(), e.g.:
$ echo "Hello World"  python p0.py
Hello Ireland!
$ cat p0.py
line = raw_input()
words = line.split()
print words[0], "Ireland!"
Table of contents
Problem 1  Rectangles
Read two integer numbers R and C from the standard input and then print R lines with C asterisks (*) each.
Example (R=3, C=5):
*****
*****
*****
Example (R=2, C=10):
**********
**********
Input
The first line will contain an interger R. The number of lines to print.
The second line will contain an integer C. The number of asterisks to print in each line.
R, C will be at most 20.
Output
Print a rectangle of R lines and C columns.
Examples
Input Example 1
3
5
Output example 1
*****
*****
Problem 2  Final Score
We have had a problem with one of our hard disks and we lost the final score of some football matches. However, we have been able to recover the names of the players that scored and found the members of each team on Wikipedia.
Input
The first line will contain three integers A, B and G representing the number
of players in team A and team B and the number of goals scored in the match.
The second line will contain A strings separated by spaces. The names of the
players of team A.
The third line will contain B strings separated by spaces. The names of the
players of team B.
The fourth line will contain G strings. The names of the players that scored.
Limits
There will be at most 20 players in each team and at most 100 goals.
The names of the players are lowercase latin letters and they will have at most 20 characters each.
Output
Print "A" if the team A scored more than team B.
Print "B" if the team B scored more than team A.
Print "TIE" if both scored the same number of goals.
Examples
Example Input 1
3 3 5
messi neymar suarez
ronaldo bale james
messi messi messi bale james
Example Output 1
A
Example Input 2
4 1 5
jordan pippen oneal bryant
villa
villa villa villa villa villa
Example Output 2
B
Example Input 3
3 3 4
messi neymar suarez
ronaldo bale james
bale messi ronaldo suarez
Example Output 3
TIE
Problem 3  Number Pairs
Given a sequence of N distinct integer numbers compute the number of pairs that sum to K.
Example:
Given the sequence {1, 2, 3, 4, 5, 6}
There are 1 pair of numbers that sums to 3: (1, 2)
There are 1 pair of numbers that sums to 4: (3, 1)
There are 2 pairs of numbers that sum to 5: (1, 4) and (3, 2)
There are 2 pairs of numbers that sum to 6: (5, 1) and (4, 2)
There are 3 pairs of numbers that sum to 7: (1, 6), (2, 5) and (3, 4).
There are 2 pairs of numbers that sum to 8: (2, 6) and (5, 3)
There are 2 pairs of numbers that sum to 9: (6, 3) and (5, 4)
...
Note that we consider that the pairs (1, 6) and (6, 1) are the same.
Input
The first line will contain two integers N and K.
N represents the number of elements in the sequence and K the goal value.
We want to know how many pairs of numbers sum to K.
The second line will contain N integers separated by spaces.
Limits
N <= 1000
The numbers in the sequence will be between 1 and 10^6.
Output
An integer, the number of pairs that add K.
Examples
Example Input 1
6 7
1 3 2 6 5 4
Example Output 1
3
Problem 4  Olympiad Pizza
During the Olympiad finals we usually serve pizza for the contestants. When the food arrives, the contestants to queue to get some pizza. Each student will be given a single slice of pizza when his/her turn arrives. The problem is that some people need more than one slice of pizza to be well fed so they need to queue again for more pizza after they get the first one.
Given a list of slices needed to fed each of the contestants, compute how long it will take to fed all of them. We can give a slice of pizza every second and when a contestant is well fed he does not return to the queue.
Input
The first line will contain an integer N. The number of contestants.
The second line will contain N integers separated by spaces. The number of slices of pizza needed to feed each contestant.
Limits
N <= 1000
The numbers in the sequence will be between 1 and 1000.
Each contestant will need at least 1 and at most 100 slices of pizza.
Output
A line containing N integers separated by spaces. The time in which each of the
contestant get all the slices he/she needs.
Examples
Example Input 1
4
1 3 1 4
Example Output 1
1 7 3 9
The contestants that get a slice are, in order: 1, 2, 3, 4, 2, 4, 2, 4, 4.
So at t=1s the first contestant get all slices, at t=3s the third contestant gets a slice, at t=7s the second student finishes and finally at t=9s the fourth student gets the last slice.
Problem 5  Dominos
Dominoes are gaming pieces used in numerous tile games. Each domino piece contains two marks. Each mark consists of a number of spots (possibly zero). The number of spots depends on the set size. Each mark in a size N domino set can contain between 0 and N spots, inclusive. Two tiles are considered identical if their marks have the same number of spots, regardless of reading order. For example tile with 2 and 8 spot marks is identical to the tile having 8 and 2 spot marks. A proper domino set contains no duplicate tiles. A complete set of size N contains all possible tiles with N or less spots and no duplicate
tiles. For example, the complete set of size 2 contains 6 tiles:
Write a program that will determine the total number of spots on all tiles of a complete size N set.
Input
The first and only line of input contains a single integer, N (1 ≤ N ≤ 1000), the size of the complete set.
Output
The first and only line of output should contain a single integer, total number of
spots in a complete size N set.
Examples
Input
2
Output
12

Input
3
Output
30

Input
15
Output
2040

Problem 6  Cipher
Sean is a great code breaker (or thinks he is). He knows any cipher in the world can be broken by frequency analysis, but he has the completely the wrong idea what frequency analysis is, however.
He intercepted an enemy message. The message consists of N numbers, smaller than or equal to C.
Sean believes frequency analysis consists of sorting this sequence so that more frequent numbers appear before less frequent ones. Formally, the sequence must be sorted so that given any two numbers X and Y , X appears before Y if the number of times X appears in the original sequence is larger than the number of time Y does. If the number of appearances is equal, the number whose value appears sooner in the input should appear sooner in the sorted sequence.
Help Sean by creating a "frequency sorter".
Input
First line of input contains two integers, N (1 ≤ N ≤ 1 000), length of message, and C (1 ≤ C ≤ 1 000 000 000), the number from task description. Next line contains N integers smaller than or equal to C, message itself.
Output
First and only line of output should contain N numbers, the sorted sequence.
Examples
Input
5 2
2 1 2 1 2
output
2 2 2 1 1

input
9 3
1 3 3 3 2 2 2 1 1
output
1 1 1 3 3 3 2 2 2

input
9 77
11 33 11 77 54 11 25 25 33
output
11 11 11 33 33 25 25 77 54
