You are hereProgramming Problems / 2013 AIPO National Finals Problems

2013 AIPO National Finals Problems


By gconway - Posted on 21 May 2013

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.

The letter is determined from the values of the digits and is used to ensure that you don't make a mistake when quoting the number.
 
Write a program called q1 that will have a ten digit number as input, and will calculate a unique check character corresponding to the given number according to the following rules:
 
- add the five pairs of digits contained in the number
- take the remainder on dividing the result by 26
- select the letter in that position of the alphabet assuming the A is in position 0, B in position 1, etc.
 
For example, if the input is 1122334455, your program should calculate
(11 + 22 + 33 + 44 + 55) % 26 giving 9 and so give J is the check character.
 
--------------------------------------------------------------------------
 
>cat q1.in
1122334455
 
>cat q1.out
J
 
>java q1 < q1.in
J
 
--------------------------------------------------------------------------

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.

 
For example if N = 1000000080 the output would be the letters K, L and M as they occurred 4 times in the range 1000000000 to 1000000080.
 
--------------------------------------------------------------------------
 
>cat q2_1.in
1000000080
>cat q2_1.out
K
L
M
4
>java q2 < q2_1.in
K
L
M
4
 
>cat q2_2.in
1000000100
>cat q2_2.out
L
5
>java q2 < q2_2.in
L
5
 
--------------------------------------------------------------------------

Q3_Jnr - ISBN Number

Every book has a unique identifier called its ISBN (there are several versions, the latest being called ISBN-13). Typical ISBNs are:

978-0-470-12870-1

978 0 387 98259 5

An ISBN consists of 13 digits organised as 5 non-empty 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

x0x1x2 ... x12 the checksum (x12) equals

(10-(x0+3x1+x2+3x3+ ...+ 3x11) 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

978-0-306-40615-7

978-1-56619-909-4

978-0-470-12870-1

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

                          a^2 + b^2 = c^2
 
This relationships holds in cases where the sides of the triangle are whole
numbers.
 
For example, if 3 to the power of 2 is written 3^2 = 9 then
             3^2 + 4^2 = 5^2
             and
             5^2 + 12^2 = 13^2
             and
             28^2 + 45^2 = 53^2
 
A triple (a, b, c) of positive integers for which this is true is called a Pythagorean Triple.
 
We can list the Pythagorean triples in ascending order of the value of c:
(3,4,5)       first Pythagorean triples
(4,3,5)
 
(6,8,10)      second Pythagorean triples
(8,6,10)
 
(5,12,13)     third Pythagorean triples
(12,5,13)
 
(9,12,15)     fourth Pythagorean triples
(12,9,15)
 
(8,15,17)     fifth Pythagorean triples
(15,8,17)
 
(12,16,20)    sixth Pythagorean triples
(16,12,20)
 
 (7,24,25)     seventh Pythagorean triples
(15,20,25)
(20,15,25)
(24,7,25)
...
Note that if (a, b, c) is a Pythagorean triple, then (b, a, c) is also a Pythagorean triple. So each value of c appears at least twice in this list.
 
In addition, for some values of c, for example 25, c can appear more than twice. Write a program called q4 that will input an integer n, and output a list of the first n values that appear as c in a Pythagorean triple.
 
For example, if n is 7, the Pythagorean triples would be those shown below and your program should output in ascending order the values of c with no repition in other words only print 5 once, only print the 10 once etc.
 
(3,4,5)
(4,3,5)
(6,8,10)
(8,6,10)
(5,12,13)
(12,5,13)
(9,12,15)
(12,9,15)
(8,15,17)
(15,8,17)
(12,16,20)
(16,12,20)
(7,24,25)
(15,20,25)
(20,15,25)
(24,7,25)
 
--------------------------------------------------------------------------
 
>cat q4_1.in
7
>cat q4_1.out
5
10
13
15
17
20
25
 
--------------------------------------------------------------------------
 

Q1_Snr - ISBN Numbers

As above

 

Q2_Snr - Pythagorean Triples

As above

 

Q3_Snr - Average Element

 

You are given a sequence of integers a1, a2, ..., aN.
 
An element ak is said to be an average element if there are indices i, j (with i not equal j) such that ak = (ai + aj) / 2.
 
Consider the first sequence:
----------------------------
              3   7  10  22  17  15
indices  [1] [2] [3]  [4] [5]  [6]
 
when i=1, j=5 and k=3, we get
    ak = (ai + aj) / 2.
    a3 = (a1 + a5) / 2
    a3 = (3  + 17) / 2
    a3 = (20)      / 2
    a3 =  10
    correct
 
Thus a3 = 10 is an average element in this sequence. You can check that a3 is the only average
element in this sequence.
 
Consider the second sequence:
------------------------------
              3   7  10   3  18
indices  [1] [2] [3]  [4] [5]
 
when i=1, j=4 and k=1 we get
    ak = (ai + aj) / 2.
    a1 = (a1 + a4) / 2
    a1 = (3  + 3)  / 2
    a1 = (6)       / 2
    correct
 
Thus a1=3 is an average element. We could also choose i=1, j=4 and k=4 and get ak=(ai +aj)/2.
You can check that a1 and a4 are the only average elements of this sequence.
 
Consider the third sequence:
------------------------------
              3   8   11  17  30
indices  [1]  [2]  [3]  [4]  [5]
has no average elements.
 
Your task is to count the number of average elements in the given sequence.
 
Input format
The first line contains a single integer N indicating the number of elements in the sequence.
This is followed by N lines containing one integer each (Line i+1 contains ai).
(You may assume that ai + aj would not exceed MAXINT for any i and j).
 
Output format
The output must consist of a single line containing a single integer k indicating the number of
average elements in the given sequence.
 
Test Data:
You may assume that N <= 10000. Further, you may assume that in 30% of the inputs N <= 200 and
that in 60% of the inputs N <= 5000.
 
--------------------------------------------------------------------------
 
 >cat q3_test1.in
6
3
7
10
17
22
15
>cat q3_test1.out
1
>java q3 < q3_test1.in
1
 
--------------------------------------------------------------------------

 

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, p-1 and p+1 if 1<p<N, and the neighbor 2 if p=1, and the neighbor N-1 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 ≤ Ci ≤ 2000 where Ci is the number of chips in the pile i when the game starts (1 ≤ iN).

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 Ci.

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)Bx)/ if B < x < (3/2)B

0                             if x => (3/2)B

--------------------------------------------------------------------------

AttachmentSize
test_data.tgz283.19 KB