You are hereProgramming Problems / 2013 AIPO Preliminary Round Problems

# 2013 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 '144 12' | q1 $ 12 $ q1 < input.txt $ 12 $ cat input.txt $ 144 $ 12

## Q1 - GCD

The greatest common divisor (GCD) of two non-zero, natural numbers a and b is the largest number which divides both of them. It is denoted gcd(a, b).

Write a program that will input two integer values a and b, and output the singe integer answer of gcd(a, b). You can assume that:

1 < a,b < 10^{9}

Hint. *Euclid’s Algorithm* can be used to compute the GCD of two numbers.

Your program should be named one of the following depending on the language used:

q1.c, q1.cpp, q1.java, q1.php, q1.py, q1.pl

**Sample input:**

144 12

**Sample output:**

12

## Q2 - Operators

Given the two operators +1 and ×2, which you may use repeatedly; write a program that computes the *minimal* number of operator invocations required to reach a given integer, N from the integer 10. You can assume that:

10 < N < 10^{6}

For example, for reaching 21 from 10, two invocations suffice: ×2 and then +1. For reaching 24, three invocations are required: +1, +1 and then ×2.

Your program should produce a single integer answer and be named one of the following depending on the language used:

q2.c, q2.cpp, q2.java, q2.php, q2.py, q2.pl

**Sample input:**

24

**Sample output:**

3

## Q3 - Prime Factors

Write a program that will read an integer x, and outputs its **unique** prime factors. You can assume that:

1 < x < 10^{6}

Your program should be named one of the following depending on the language used:

q3.c, q3.cpp, q3.java, q3.php, q3.py, q3.pl

**Sample input:**

273

**Sample output:**

3 7 13

## Q4 - Palindromic Prime

Palindromic Primes are prime numbers that read the same left to right (forwards) as from the right to left (backwards).

Here are a few random examples : 3, 131, 71317, 134757431

Write a program that outputs the number of palindromic primes between two integers, a and b. You can assume that:

1 < a,b < 10^{6}

Your program should produce a single integer answer and be named one of the following depending on the language used:

q4.c, q4.cpp, q4.java, q4.php, q4.py, q4.pl

**Sample input:**

2 100

**Sample output:**

5

## Q5 - Module Marks

There are *n* students taking a computing module at a well-known university in Ireland. Each student is identified by an integer *i* such that 1 ≤ i ≤ *n*, and is allocated a unique 6-digit prime number *p _{i}* such that 100000 <

*p*< 1000000. Students are expected to keep their prime number secret.

_{i}In a lab exam, each student receives a mark *m _{i}* such that 0 ≤

*m*≤ 100.

_{i }For each student, the lecturer computes the value *r _{i }* = (

**m**+

_{i }**1**) ×

*p*, and publishes these values in the form of a set of integers:

_{i}[*r _{0}* ,

*r*, . . . ,

_{1}*r*]

_{n−1}A student knows her prime number *p _{i}*, but does not know her identity

*i*, i.e., she does not know where her

*r*value appears in the vector.

_{i}For example, assuming *n* = 3, that a student’s prime number is 212633, and that the lecturer publishes the set:

result = [1005695, 20625401, 6699754]

then the student has a mark of 96.

The students taking the module described are curious to discover just how well they have done in the lab exam. So they decide to ask the lecturer of the module to tell them the marks of all of the students taking the module.

The kind lecturer tells them that he cannot give them a list of marks for each student, but that it is possible to discover all of the marks from the information that he has already released. *This is okay as a student cannot find the mark of another student who has kept their prime number pi secret, as advised on the web site for the module.*

The module results for the class are as follows:

result = [882571, 40630558, 70111157, 3574196, 90589021, 21650088, 51724479, 25453708, 83836530, 936619, 1938886, 78225520, 23671992, 99401300]

Write a program that will output all the marks for the module.

Your program should be named one of the following depending on the language used:

q5.c, q5.cpp, q5.java, q5.php, q5.py, q5.pl

**Sample input:**

20625401 7289806 32018846

**Sample output:**

96 37 61

## Q6 - Average Sequence

Consider a non-decreasing sequence of integers *s _{1},...., s_{n+1 }*where

*s*

_{i}*≤*

*s*for

_{i+1}*1*

*≤*

*i*

*≤*

*n*.

The sequence a* _{1},..., a_{n }*defined by a

*, for*

_{i}= 1/2 (s_{i}+ s_{i+1})*1 ≤ i ≤ n*, is called the average sequence of sequence

*s*.

_{1},...., s_{n+1}### Input

The first line of the standard input contains a single integer *n (2 ≤ n ≤ 5 000 000)*. The remaining *n* lines contain the sequence *a _{1} ,...., a_{n}* . Line

*i+1*contains a single integer

*a*.

_{i}(0 ≤ a_{i}≤ 1 000 000 000)### Output

Your program should write to the standard output exactly one integer - the number of non-decreasing integer sequences, that have the input sequence as it's average sequence.

Your program should be named one of the following depending on the language used:

q6.c, q6.cpp, q6.java, q6.php, q6.py, q6.pl

**Sample input:**

3 2 5 9

**Sample output:**

4

The four non-decreasing integer sequences for which 2, 5, 9 is the average sequence are:

- 2 2 8 10
- 1 3 7 11
- 0 4 6 12
- -1 5 5 13