You are hereProgramming Problems / 2015 AIPO National Finals Problems

2015 AIPO National Finals Problems


By gconway - Posted on 03 March 2015

Please note: Test data and PDF at the bottom of this page

J1 - TicTacToe

TicTacToeWe want to create a program to check the result of a tic tac toe game. A tic tac toe board is a 3x3 grid. Each position can contain either X or O. The game finishes with a winner when a player creates a straight line of 3 equal symbols. The next 3 boards show finished games with a winner. The empty positions are represented using dots. 
 
X . X     O X .    . X .
OOO     . O .    . X .
.  .  .      X . O    . X O
 
In contrast, these 3 boards have not finished with a winner.
 
O X O    X . .    . . .
X X O    O.O    . X .
O O X    . X X   . . O
 
Input
 
The test case consists of 3 lines. Each one with 3 characters (dot, O or X).
Note that we are using the letter “o” not the digit zero.
 
Output
 
For each test case, write YES if the board finished with a winner or NO if there is no winner.
 
Input Example 1
 
X X X
. O O
O O .
 
Output Example 1 
 
YES
 
Input Example 2
 
X O X
O X O
O X O
 
Output Example 2
 
NO
 
 

J2 - The Real Manhattan Distance

RealManhattanDistance
If you remember the preliminary round, we already measured distances in Manhattan. Besides being a grid, Manhattan also has very tall buildings scattered all over the island.
Suppose I want to go to from my apartment that is at position x=3, y=4, floor=3 to my friends apartment, which is x=3, y=5, floor=2. To compute the distance between two points we have to take into account the distance from the my apartment down to the street, the distance to my friend’s building and finally the distance from the street up to my friend’s apartment.
 
Given two points, please compute the distance in meters we need to walk. We will assume the distance between floors is 1. You should know already that in Manhattan, the street distance between two points is equal to the distance between the x coordinates plus the distance between the y coordinates.
 
Example:
Distance from (3,4,3) to (3,5,2) is 3 (going down the first building) + 0 (moving among x) + 1 (moving among y) + 2 (going up the second building).
Result = 3 + 0 + 1 + 2 = 6. We spent more time inside buildings that actually walking on the streets!
 
Input
 
The first line will contain the number of test cases T. Each of the next T lines will contain 2 points. You have to compute the distance between these two points.
Each test cases is a line with 6 integer numbers x1, y1, floor1, x2, y2, floor2. See the examples below.
 
Output
 
For each test case a single line with the distance between the two points.
 
Limits
  • Easy tests
    • 1 ≤ T ≤ 10
    • 0 ≤ x, y, floor ≤ 100
  • Hard tests
    • 1 ≤ T ≤ 100
    • 0 ≤ x, y, floor ≤ 10000
 
Input Example 1
 
3
3 4 3 3 5 2
0 0 0 1 1 1
1 2 3 3 2 1
 
Output Example 1
 
6
3
6
 
Input Example 2
 
3
100 345 12 382 48 19
5 5 5 5 5 5
0 0 10000 10000 10000 10000
 
Output Example 2
 
610
10
40000
 
 

J3 - Selection Sum

SelectionSumSuppose we have an array of integers such as 1, 2, 3, 4, 5, 6, 7, 8, 9, 10. It is easy to compute the sum of all its elements. We only need a loop!
 
For example:
 
int size = 10;
int total = 0;
for (int i = 0; i < size; i += 1) {
    total = total + v[i];
}
If we want to count a different range of elements (for example, from position 5 to 7) we only need to change a few parts of the loop. In this problem you'll have to do this operation several times!
 
Input
 
The first line of the input will contain an integer n (the array size). The next line will contain n integers separated by spaces.
After the array, the next line will contain an integer m (the number of tests). The next m lines will contain a test each. A test is a pair of integers start, end. You'll have to compute the sum of the elements from the position start to end.
 
Output
 
For each test, print the sum of the elements of the array from the position start to the position end inclusive. 
That is: array[start] + array[start+1] + ... + array[end-1] + array[end].
 
Limits
  • n will be a number from 1 to 100000
  • start and end will be valid positions of the array
  • start <= end
  • the values of the array will be integers from 0 to 9
  • m will be at most 10000
 
Input Example
 
10
1 5 6 3 5 9 0 3 9 1
5
1 1
0 9
5 7
9 9
1 8
 
Output Example
 
5
42
12
1
40
 
 

J4S1 - Bits equalizer

You are given two non-empty strings S and T of equal lengths. S contains the characters ‘0’, ‘1’ and ‘?’, whereas T contains ‘0’ and ‘1’ only. Your task is to convert S into T in minimum number of moves. In each move, you can do one of these changes:
  • change a ‘0’ in S to ‘1’
  • change a ‘?’ in S to ‘0’ or ‘1’ 
  • swap any two characters in S
As an example, suppose S = “01??00” and T = “001010”. We can transform S into T in 3 moves: 
  • Initially S = “01??00” 
  • Move 1 – change S[2] to ‘1’. S becomes “011?00” 
  • Move 2 – change S[3] to ‘0’. S becomes “011000” 
  • Move 3 – swap S[1] with S[4]. S becomes “001010”
  • S is now equal to T.
 
Input
 
The first line of input is an integer C (C ≤ 200) that indicates the number of test cases. Each case consists of two lines. The first line is the string S consisting of ‘0’, ‘1’ and ‘?’. The second line is the string T consisting of ‘0’ and ‘1’. The lengths of the strings won’t be larger than 100.
 
Output
 
For each case, output the case number first followed by the minimum number of moves required to convert S into T. If the transition is impossible, output −1 instead. Check the output example for the exact format.
 
 
Input Example
 
3
01??00
001010
01
10
110001
000000
 
Output Example
 
Case 1: 3
Case 2: 1
Case 3: -1
 
 

S2 - Lucky Tickets

LuckyTicketAll bus and train tickets in Soviet Union had an identifier with an even number of digits (2*N). In many places in Russia and Kazakhstan there are tickets still like this. A ticket is called lucky if the sum of the first half of the digits of its identifier is equal to the sum of its last half of the digits.
 
Many children believe that if you eat such ticket, something good will happen to you.
Let’s find out how many lucky tickets exist!
 
Input
 
The first line is the number of test cases T (1 <= T <= 100).
Each of the following T lines contains one integer number N (where 2N is the number of digits in the ticket’s identifier and 1 <= N <= 500);
 
Output
 
For ith test case print a line containing: "Case #i: " followed by the number of lucky tickets with 2N-digit identifiers. The numbers get quite large soon so print the numbers modulo 1000000007 (10^9 + 7).
 
 
Input Example
 
3
1
2
7
 
Output Example
 
Case #1: 10
Case #2: 670
Case #3: 331247783
 
 

S3 - Domain Clusters

We are analyzing how the domains on the Internet connect to each other. A domain is the part of a URL that comes before the / character. Examples of domains are: twitter.com, aipo.computing.dcu.ie or google.com. A domain d1 is connected to a domain d2 if there is a link from d1 to d2 or if d1 is connected to a domain d3 and d3 is connected to d2. We consider that a domain is connected to itself.
In the following structure of domains:
DomainClusters
  • D1 is connected to D2, D3 (through D2), D4 and D5 (through D3).
  • D2 is connected to D3, D4 (through D3) and D5 (through D3).
  • D3 is connected to D2, D4 and D5.
  • D4 is not connected to any other domain.
  • D5 is connected to D2, D3 (through D2) and D4 (through D3).
We want to obtain the biggest subset of domains S where each domain in S is connected to all the other domains in S. In the example above we have the following subsets that meet this criteria:
 
D1 Connected to itself.
D2, D3, D5 We can arrive from D2 to D3 and D5, from D3 to D2 and D5 and from D5 to D2 and D3.
D4 Connected to itself.
 
Please, given the links of the Internet, compute the size of the biggest subset.
 
Input:
 
The first line will contain an integer D representing the number of domains. The names of the domains will be integers from 1 to D.
The second line will contain an integer L representing the number of links between domains.
The following L lines will contain two integers each. The first integer is the source of the link and the second is the destination. Remember that a link from A to B does not imply a link from B to A and that every domain is connected to itself without the need of an explicit link. No link will appear more than once.
 
Output:
 
The size of the biggest subset of domains that meet the criteria above. If two or more subsets are tied for the biggest size, print the size of any of them.
 
Limits
  • Easy tests
    • 1 ≤ D ≤ 30
    • 0 ≤ L ≤ D2
  • Hard tests
    • 1 ≤ D ≤ 5000
    • 0 ≤ L ≤ D2
Input Example 1:
 
5
7
1 2
1 4
2 3
3 4
3 2
3 5
5 2
 
Output Example 1:
 
3
 
Input Example 2:
 
4
4
1 2
4 1
3 4
2 3
 
Output Example 1:
 
4
 
 

S4 - Celtic Symmetry

 
Dolmen
After taking an Ancient Irish History class, Diarmuid has become interested in finding geometric patterns in neolithic tomb locations around Ireland.  He carefully plots the locations of N tombs (2 <= N <= 1000), each one occupying a distinct point in the 2D plane, and he wonders how many different lines of symmetry exist for this set of points.  A line of symmetry, of course, is a line across which the points on both sides are mirror images of each other.  
 
Help Diarmuid answer this most pressing geometric question.
 
Input
 
First line: The number of tombs N.
 
The following N lines: Two integers x, y separated by a space indicating the position x and y of each tomb (-10,000 <= x,y <= 10,000).
 
Output
 
The number of different lines of symmetry of the point set.
 
 
Input Example 1:
 
3
0 0
0 1
0 3
 
Output Example 1:
 
1
 
Input Example 2:
 
4
0 0
0 1
1 0
1 1
 
Output Example 2:
 
4
 
There are 4 lines of symmetry -- one vertical, one horizontal, and two
diagonal.

 

 

AttachmentSize
AIPO2015-Finals-problems.pdf3.77 MB
AIPO2015-Finals-testcases.zip2.09 MB