You are hereProgramming Problems / 2013 AIPO Preliminary Round Problems

2013 AIPO Preliminary Round Problems


By gconway - Posted on 11 December 2012

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

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

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

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

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 pi such that 100000 < pi < 1000000. Students are expected to keep their prime number secret.

In a lab exam, each student receives a mark mi such that 0 ≤ m ≤ 100.

For each student, the lecturer computes the value r = (m+ 1) × pi , and publishes these values in the form of a set of integers:

[r0 , r1 , . . . , rn−1 ]

A student knows her prime number pi, but does not know her identity i, i.e., she does not know where her ri value appears in the vector.

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  s1,...., sn+1 where si  ≤ si+1 for  i ≤ n.

The sequence a1,..., adefined by ai = 1/2 (si + si+1), for 1 ≤ i ≤ n, is called the average sequence of sequence s1,...., sn+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 a1 ,...., an . Line i+1 contains a single integer ai (0 ≤ ai ≤ 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