You are hereProgramming Problems / 2017 AIPO Preliminary Round Problems

# 2017 AIPO Preliminary Round Problems

By - Posted on 12 January 2017

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!"

## 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