You are hereProgramming Problems / 2013 AIPO National Finals Problems
2013 AIPO National Finals Problems
Please Note: Test Data available at bottom of the page.
Q1_Jnr  Social Security Number
A social security number consists of a sequence of digits followed by a letter.
Q2_Jnr  Social Security Range
Using some of the code from q1, you are to write a program called q2 that will print the check letters of the social security numbers that occur the most often up to a number N which will be the input to your program. You can assume 1000000000 <= N.
Q3_Jnr  ISBN Number
Every book has a unique identifier called its ISBN (there are several versions, the latest being called ISBN13). Typical ISBNs are:
9780470128701
978 0 387 98259 5
An ISBN consists of 13 digits organised as 5 nonempty groups separated from one another by a space or a hyphen. The first group is either 978 or 979. The final group is a single digit called the checksum. Denoting the sequence of 13 digits by
x_{0}x_{1}x_{2} ... x_{12} the checksum (x_{12}) equals
(10(x_{0}+3x_{1}+x_{2}+3x_{3}+ ...+ 3x_{11}) mod 10) mod 10
where mod is the arithmetic modulo operator.
Write a program that reads a string from the standard input and display a 1 or 0 as to whether the string is a valid ISBN. 1 being the ISBN number is valid and 0 being that it is not.
The input can be a single ISBN number or a set, s of ISBN numbers.

>cat q1_1.in
9780306406157
9781566199094
9780470128701
>cat q1_1.out
1
1
1

Q4_Jnr  Pythagorean Triples
We know from Pythagoras' Theorem that the sum of the squares of the sides of a right triangle equals the square of the hypotenuse.
Q1_Snr  ISBN Numbers
As above
Q2_Snr  Pythagorean Triples
As above
Q3_Snr  Average Element
Q4_Snr  Flatten (IOI1999)
A solitaire game is played given a row of N piles where each pile contains zero or more chips. See Figure 1. Piles are identified by integers 1 through N. In a move of this game you point to a pile, say p, and specify a number, say m. Then m chips are transferred from the pile p to each of its neighboring piles. See Figure 2 for an example. Pile p has two neighbors, p1 and p+1 if 1<p<N, and the neighbor 2 if p=1, and the neighbor N1 if p=N. Note that to be able to make such a move the pile p must have at least 2m chips if it has two neighbors, and it must have at least m chips if it has only one neighbor.
The object of the game is to “flatten” all piles, that is make them have the same number of chips, by making as small as possible number of moves. In case there is more than one solution you are required to report only one of them.
Piles: 1 2 3 4 5 Piles: 1 2 3 4 5
Figure 1. Five piles with 0, 7, 8, 1 and 4 chips. Figure 2. Same piles after a move: p=2, m=2
ASSUMPTIONS

It is guaranteed that it is possible to flatten the given piles in at most 10,000 moves.

2 ≤ N ≤ 200

0 ≤ C_{i} ≤ 2000 where C_{i }is the number of chips in the pile i when the game starts (1 ≤ i ≤ N).
INPUT
The input is a text file named flat.inp having two lines.

The first line: N The second line: there will be N integers the i th of which is the value of C_{i}.
OUTPUT
The output will be the text file named flat.out.

The first line: number of moves. (Call this value M.)

Each of the following M lines contains two integers representing a move: p, m.
The order of moves on the output must be the same order the moves are performed. So, your first move shall be written to the second line of the output file.

flat.inp:
5
0 7 8 1 4
flat.out:
5
5 2
3 4
2 4
3 1
4 2

EVALUATION
Your program will be allowed to run 3 seconds.
To get full credit, A, for a test case, your number of moves, x, must be less than or equal to the number B, set by the evaluation program. Note that B is not necessarily minimal. In fact, B is chosen for a test case depending on the number of moves made by following a simple strategy with no redundant moves and the average number of chips in the piles. You can obtain partial credit for a test case. The points you get is calculated by rounding to the nearest integer the value obtained by the following formula:
A if x <= B
2A ((3/2)B – x)/B if B < x < (3/2)B
0 if x => (3/2)B

Attachment  Size 

test_data.tgz  283.19 KB 