You are hereProgramming Problems / 2017 AIPO National Finals Problems
2017 AIPO National Finals Problems
Problem 1: Pirates
Pirates talk a funny way. They say word where the letters are repeated more than they need to be. We would like know which letter appears the most frequently in a Pirate word.
For example: In the word “arrrrrghh”, the letter “r” appears 5 times while “h” appears twice.
Write a program that reads a pirate word from the terminal and writes the letter that occurs most frequently.
It is guaranteed that only one letter is the most repeated. That is, words like “aipo” won’t appear because no single letter wins.
Input
The input will consist of two lines.
The first line will contain the size of the word and the second the word to process.
The word will only contain lowercase letters from a to z. The size of the word will be at most 1000 characters. No spaces or other symbols will appear.
Output
Print a single line with the character that appears the most and the number of occurrences.
Example 1
Input 10 arrrrrrghh 
Output r 6 
Example 2
Input 9 shhhiiver 
Output h 3 
Example 3
Input 20 oxlbelhfikrzxcgxpfcy 
Output x 3 
Problem 2: Password check
Dublin City University wants to prevent students and staff from using weak passwords. The Security Department has commissioned you to write a program that checks that some passwords meet all the quality requirements defined by the Password Guidelines Council.
These requirements are as follows. A password is considered strong enough if it has the following properties:

At least one lowercase letter.

At least one uppercase letter.

At least one digit

At least one symbol from the set +_)(*&^%$#@!./,;{}

Minimum length is 12.
Examples:

The password “Aa1_” (without the quotes) meets the first 4 requirements but its length is less than 12.

The password “Aa1234567890_” is perfectly fine.
Input
You’ll have to process a batch of password in every test case.
The first line will contain an integer N with the number of passwords to process.
Each password will be presented in two lines. The first line will contain an integer S with the size of the password. The next line will contain a sequence of S characters, the password to check.
The password will only contain the letters from a to z (both lowercase and uppercase) the digits from 0 to 9 and the following symbols: “+_)(*&^%$#@!./,;{}” without the quotes.
The maximum size of a password will be 30 characters. Each test case will contain at most 100 passwords to process.
Output
For each password write a line with the word “valid” if the password meets that quality requirement or “invalid” otherwise.
Example 1
Input 2 4 Aa1_ 13 Aa1234567890_ 
Output invalid valid 
Example 2
Input 5 18 UtQ.iNlLgT;{f,.GR! 29 yr)Z,pHQ+No,ZfP_z12D2l1*MSTfk 23 .p7hV/Es^aahW%B.1JJouO; 9 c7V!*$1lW 26 a^pBAAxCohQlBv7qDpVeOB%Min 
Output invalid valid valid invalid valid 
Problem 3: Paint bucket
One of the most timesaving operations when drawing on a computer (for example using Photoshop) is the “bucket fill” operation.
When you select this tool and click on a (target) pixel of the image it will fill all the pixels that have the same color than the target pixel and are connected to it. Two pixels are connected if they share a side or if they are connected through a path of connected pixels.
Let’s see an example: In the following image, if we select the “fill” operation in an image editor program and click on the center of the image (orange pixel). The whole region will be painted orange. Notice that the pixels are not connected diagonally so two corners of the image remain white.
Your task is: Given a matrix of digits representing the pixels, simulated what would be the result of a “fill” operation on given pixels. Thus, the colors will be represented with a number from 0 to 9.
Let’s see another example, now using digits instead of pixels. We have the following image:
0000000
0111000
0111010
0000000
If we “fill” at position Y = 0, X = 0 with color 3, all the 0s get painted of color 3. Because all of them are recursively connected.
The result will be:
3333333
3111333
3111313
3333333
Input
The first line will contain two integers R and C representing the number of rows and columns of the image.
The next R lines will contain C digits each representing the initial colors of the pixels.
The last line will contain 3 integers Y, X and K representing the row and column where we want to apply the “fill” operation and the color to use.
The images will be smaller than 1000 x 1000 pixels.
The colors are limited to a single digit from 0 to 9.
Output
Print the resulting image after applying the operation in the same format as the input.
Example 1
Input 4 7 0000000 0111000 0111010 0000000 0 0 3 
Output 3333333 3111333 3111313 3333333 
Example 2
Input 9 9 000000000 011101110 011101110 011011110 000111000 011110110 011101110 011101110 000000000 4 4 2 
Output 000000000 011102220 011102220 011022220 000222000 022220110 022201110 022201110 000000000

Problem 4: Counting paths
Every afternoon, Jack runs from his house to John's. Their houses are in an open field of size N x M. Jack is trying to use a different path each day but he is not sure how many different ways to reach John's house exist.
We will represent the field using a grid of N rows and M columns like the following:
....
..X.
....
Jack lives in the topleft position and John in the bottomright. Jack wants to use a different route every day but does not want to waste time he will only walk down and/or right. Also, some parts of the fields have obstacles such as rocks or houses and Jack cannot go through them (they are marked with an X in the grid).
In the previous field, the 4 valid routes are:
****
..X*
...* 
*...
*.X.
**** 
*...
**X.
.*** 
**..
.*X.
.*** 
Notice that all the valid routes will always have the same length (N + M  1).
The number of possible paths can be very large so print the result modulo 1000000007 (10^9 + 7).
Input
The first line will contain two integers N and M. The rows and columns of the map.
Each of the following N lines will contain M characters. If the character is a dot (.), this position is empty. If the character is an X, it means that there is an obstacle and Jack cannot use this cell.
The topleft and bottomright cells will never have an obstacle on them.
Limits
2 <= N <= 200
2 <= M <= 200
Output
Print the number of possible path between the topleft and bottomright positions. Remember to print the result modulo 1000000007.
In most languages the modulus operator is %.
Examples
Input example 1 3 4 ....
..X.
.... 
Output example 1 4 
Input example 2 3 3 .X.
X..
... 
Output example 2 0 
Input example 3 5 5 .....
.....
.....
.....
..... 
Output example 3 70 
Input example 4 30 20 ....................
....................
....................
....................
....................
....................
....................
....................
....X...............
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
............X.......
....................
....................
....................
....................
....................
....................
....................
....................
....................
.................... 
Output example 4 833886024 Note that the actual result is 6768833933400 but we need to print the value modulo 1000000007 and 6768833933400%1000000007 equals 833886024. 
Problem 5: Knight
In Chess, the knight is the weirdest of all the pieces. To begin with, the piece is actually a horse without any human riding it. The second reason is its movement pattern. It can move 2 cells forward and one to the side. Below you can see all the possible destinations of a knight.
With a movement pattern so weird, it is complicated to know what’s the shortest path between two board squares. Can you write a program that computes the minimum number of movements needed to move a knight from one square to another? Remember that a chessboard has 8 rows and 8 columns. Also in the standard notation, the columns are represented by letters from a to h.
Input
The input will contain 2 lines. The first line will be the starting position of the knight and the second line will specify its final position.
Output
Output a single integer specifying the minimum number of moves for the knight to get from it’s starting position to it’s final position on the board.
Examples
Input h1 a8 
Output 6 
Input b1 b1 
Output 0 
Input e2 e4 
Output 2 
Problem 6: Tiling
Domino tiles (or dominoes) are rectangular pieces of size 2x1. Each square contains a number from 1 to 6. These pieces are used to play a game but in this problem we are going to use them for something different.
We can build rectangles of certain width W and height 3 using dominoes. We are wondering how many ways of creating such rectangles are possible.
Below you can see the three possible ways of creating a rectangle of width 2 and height 3.
As you see there are many ways of tiling the rectangle. For example this is a possible solution with width 12:
Your task is to write a program that computes the number of possible ways of tiling a rectangle of width W and height 3.
Input
A single line with an integer W. The width of the rectangle.
The value of W will be between 1 and 1000.
Output
A single line with the number of possible ways. The numbers can be large so print the solution modulo 1000000007 (109 + 7).
Examples
Input 2 
Output 3 
Input 8 
Output 153 
Input 30 
Output 299303201 
Input 3 
Output 0 
Input 56 
Output 485646032 
In the last test case, the actual result is 8155103542731753 by we have to print it modulo 109 + 7.
Problem 7: Debug
Seán is trying to debug a piece of his code. First he creates an array of N integers and fills it with zeros. Then he repeatedly calls the following procedure which he has written in C++:
void something( int jump ) {
int i = 0;
while( i < N ) {
seq[i] = seq[i] + 1;
i = i + jump;
}
}
As you can see, this procedure increases by one all elements in the array whose indices are divisible by jump.
Seán calls the procedure exactly K times, using the sequence X1 X2 X3 ... Xk as arguments.
After this, Seán has a list of Q special parts of the array he needs to check to verify that his code is working as it should be. Each of this parts is defined by two numbers, L and R (L ≤ R) the left and right bound of the special part. To check the code, Seán must compute the sum of all elements of seq between and including L and R. In other words seq[L] + seq[L+1] + seq[L+2] + … + seq[R]. Since he needs to know the answer in advance in order to check it, he asked you to help him.
Input
The first line of input contains two integers, N (1 ≤ N ≤ 106), size of the array, and K (1 ≤ K ≤ 106 ), number of calls to something Seán makes.The second line contains K integers: X1 X2 X3 ... Xk , arguments passed to the procedure. (1 ≤ Xi < N).
Next line contains one integer Q (1 ≤ Q ≤ 106), number of special parts of the array Seán needs to check.
Next Q lines contain two integers each Li and Ri (0 ≤ Li ≤ Ri < N), bounds of each special part.
Output
The output should contain exactly Q lines. The ith line should contain the sum of the elements seq[Li] + seq[Li +1] + seq[Li +2] + … + seq[Ri].
Examples
Input Example 1 10 4 1 1 2 1 3 0 9 2 6 7 7 
Input Example 2 11 3 3 7 10 3 0 10 2 6 7 7 
Input Example 3 1000000 6 12 3 21 436 2 19 2 12 16124 692 29021 
Output Example 1 35 18 3 
Output Example 2 8 2 1 
Output Example 3 16422 28874 
Example 1 description: The procedure is called with arguments 1, 1, 2, 1. After that the array contains values {4, 3, 4, 3, 4, 3, 4, 3, 4, 3}. Sum of indices 2 to 6 (inclusive) is 4+3+4+3+4 = 18.
Example 2 description: After the procedure calls, the array is {3, 0, 0, 1, 0, 0, 1, 1, 0, 1, 1}.
Problem 8: Boom!
Tadhg has found an interesting tape in his school chemistry lab. The tape is divided into N segments of equal length, and can easily be bent between two segments, but only by exactly 180 degrees.
One side of the tape is completely covered with a very volatile chemical. If the chemical comes in contact with itself, it reaches critical mass and explodes.
The other side of the tape is not completely covered yet. Only the first A segments and last B segments are covered, with the exact same chemical.
Write a program that will calculate the number of different ways Tadhg can bend the tape so that it does not explode. He can bend the tape more than once and two ways are different if there is at least one bevel between segments that is not bent in one and is bent in the other.
Since the solution can be huge, print the result modulo 10301.
The following example illustrates all 6 possible ways for N=4, A=1 and B=1. For clarity, the tape is only bent 90 degrees on the illustration. Tadhg would actually bend it 180 degrees.
Note: The unbent stage counts as 1 position
Input
The first and only line of input contains three natural numbers N, A and B (A>0, B>0, A+B ≤ N ≤ 1000), total number of segments, number of covered segments from the left and from the right respectively.
Output
The first and only line of output should contain the number of possible ways to bend the tape modulo 10301.
Examples
Input Example 1 4 1 1 
Input Example 2 5 2 2 
Input Example 3 6 1 2 
Output Example 1 6 
Output Example 2 1 
Output Example 3 7 