You are hereProgramming Problems / 2014 AIPO National Finals Problems

# 2014 AIPO National Finals Problems

By - Posted on 25 August 2014

## Q1_JNR - Years

The year 2013 was the first year with all its digits being different. The previous year with this property was 1987, so for all of you 2013 was your first of such year and 2014 your second.

Given a list of birth years, we want to know how many of such special years have happened until 2014.

Input

First line: an integer N (1 <= N <= 10000) with the number of birth years. The following N lines contain one integer Y each that represents the year (1000 <= Y <= 2014).

Output

For each year in the input, a line containing the number of years with this property until 2014 (included).

Input Example

6
2014
2013
1987
1988
2000
1986

Output Example

1
2
3
2
2
4

The last years with 4 different digits are: 2014, 2013, 1987, 1986, 1985, etc.

## Q2_JNR - Poison

Imagine that you are a complex AI called GLaDOS. Your job is to perform scientific tests with humans. You spend your days filling testing chambers with dangerous things and observe how humans manage to escape from them. For your next batch of experiments you need to fill some chambers with liquid poison.

Each chamber is a hexahedron with dimensions X x Y x Z. That is, the floor is a rectangle with sides X and Y meters and the ceil is Z meters above.

The floor contains X x Y tiles of size 1 x 1 meters. Each tile can be raised to a certain height (max height is obviously Z). If a tile is raised the complete volume above it is occupied.

Given a height map of a chamber, calculate what's the minimum amount of liquid poison you will need to fill the room until height L.

In the image you can see a chamber of size 6 x 8 x 6 filled up to height 4.

The height map for this chamber is:

0 0 0 2 2 0
0 2 0 2 1 0
0 0 0 0 0 0
0 3 0 0 0 5
0 1 0 0 0 0
0 0 0 1 2 0
0 1 0 1 0 5
0 0 0 0 0 0

And the amount of poison needed is 166 cubic meters.

Input

The first line contains 4 integers: X, Y, Z, and L. All these numbers will be between 1 and 1000. L won't be bigger that Z. The next Y lines contain X integers each representing the height of a tile. This height won't be bigger than Z.

Output

A single integer number indicating the volume of poison we need.

Input Example 1

2 3 10 5
0 0
0 0
0 0

Output Example 1

30

Input Example 2

2 3 10 5
0 6
1 0
0 2

Output Example 2

22

Input Example 3

6 8 6 4
0 0 0 2 2 0
0 2 0 2 1 0
0 0 0 0 0 0
0 3 0 0 0 5
0 1 0 0 0 0
0 0 0 1 2 0
0 1 0 1 0 5
0 0 0 0 0 0

Output Example 3

166

## Q3_JNR - Fib3

You probably know the Fibonacci numbers. They are defined as:

fib(0) = 0
fib(1) = 1
fib(n) = fib(n-1) + fib(n-2)  (for n > 1)

The Fibonacci numbers grow exponentially, we can only store up to fib(47) using int or fib(92) using long long in C++ or long in Java.

Trying to reduce this exponential grow, we decided to introduce this *new* definition of Fibonacci numbers that we call fib3(n):

fib3(0) = 0
fib3(1) = 1
fib3(2) = 1
fib3(n) = fib3(n-1) + fib3(n-2) - fib3(n-3)   (for n > 2)

Your task is, given a list of values, compute the value of fib3(n) for each of them.

Input

The first line contains an integer C with the number of test cases that follow. The next C lines contain an integer N each.

Limits

1 <= C <= 50
0 <= N <= 1000000000000000000 (1018)

Output

For each N, compute fib3(N).

Input Example

7
0
1
2
3
948
93480
56

Output Example

0
1
1
2
474
46740
28

Note that you need to use 64 bits integers to read the input. Use long long in
C/C++ or long in Java.

## Q4_JNR & Q1_SNR - Equation

Write a program that read the coefficients of a quadratic (second degree) equation and prints the number of solutions it has.

In the image you can see the expression of a quadratic equation and the solution.

Remember that the set of solutions is the number of distinct x that make the expression to be 0.

Input

The first line contains an integer C that indicates the number of testcases that follow.
Each testcase is a line on its own containing three integers a, b, c (the coefficients of the equation).

Limits

1 <= C <= 100
-10 <= a, b, c, <= 10

Output

For each testcase, print a line with the number of solutions of this equation.
Use the following format:

0 solutions: "No solution"
1 solution: "1 solution"
2 solutions: "2 solutions"
Infinite number of solutions: "Over 9000 solutions"

See the output example. Check that your solution output the same exact result
including spaces.

Input Example

5
1 2 3
0 2 1
1 0 -1
0 0 1
0 0 0

Output Example

No solution
1 solution
2 solutions
No solution
Over 9000 solutions

## Q2_SNR - Manhattan

I once had an apartment in Manhattan (New York) and I liked to play the a game for the room tiles. The floor of each room was a grid of either white or black tiles. We will represent the black tiles as asterisks (*) and the
white tiles as dots (.). Look at the map of two rooms:

. . . . .          * * * * * * *
. . * . .          * . . . . . *
. * * * .         * . . . . . *
. . * . .          * * * * * * *
. . . . .

For some reason, all the black tiles are connected with each other. That is, I can move from any black panel to any other just moving up, down, left or right. So the next room is not valid because it has two separated clusters of black tiles.

. . . . .
* * . . .
* * . * *
. * . . *
. . . . .

I spend the weeks moving from each black tile to each other without leaving the black tiles. But I found that some rooms where special: I could move from any two points using *at most* 2 different types of directions.

In the example rooms above I con move from A to B using 2 types of directions (right and down). I can go from C to D moving only up and right or down and right.

. . . . .          * * * * * * *
. . * . .          * . . . . . *
. A * * .        C . . . . . D
. . B . .         * * * * * * *
. . . . .

Notive that I can move in the same direction several times in any order but I can't use more than two different *types* of directions.

In the following example, the first two meet the requirement but the last one has a pair of points (X and Y) that can't be connected using only two types of directions

* * *          * * * *           * * * X
. . * .             . . * .
. . * .             . . * Y

Your task is to discover if a room is _special_ or not.

Input

Each testcase has several rooms. The first line contains an integer C with the number of rooms to process.

For each test case, the first line contains the size Y X of the room (rows and columns). The next Y lines will contain X characters each representing the room.  All the * will be pair-wise contected.

The largest test will have grids of size at most 100. There are simple cases with at most 10 and 20 respectively.

Output

For each room, write a line with the format:

Room X: R

Where X is the room number (from 1 to C) and R is "YES" is the room is any * can be reached from any other * using at most 2 types of directions or "NO" if is not possible.

Input Example

6
4 5
. . . . .
. . * . .
. * * * .
. . * . .
4 4
* * * *
* . . *
* . . *
* * * *
3 5
. . . . .
. * * * .
. . . . .
3 4
* * * *
. . * .
. . * .
3 4
* * * *
. . * .
. . * *
10 10
. * . . . . . . . .
. * . . . . . . . .
. * . . . . . . . .
. * * * * * * * . .
. * * * * * * * * .
. * * * * * * * * *
. * * * * * * * . .
. * * * * * * * . .
. . * * * * * . . .
. . . * * . . . . .

Output Example

Room 1: YES
Room 2: NO
Room 3: YES
Room 4: YES
Room 5: NO
Room 6: YES

## Q3_SNR - Cargo

A cargo boat's captain wants to load his ship with cargo so that he can maximize his profits when he sells it on the foreign markets. His cargo hold only has 'S' cubic metres in which to load the cargo.

A list of products he can load onto his ship is supplied. Each product has a certain volume (expressed in cubic metres) and a profit value.

Input:

You should read input from standard input
The first line contains 2 integers: S (1 <= S <= 100) and N (1 <= N <= 150)
- S is the cargo hold size
- N is the number of products
The following N lines contains information about products 1 to N;
each line contains 2 integers each (a and b)
'a' is the product's volume
'b' is the product's profit value.

Output:

You should write your solution to standard output
The output should be N+1 lines long.
The first line should be an integer, the maximum amount of profit attainable.
Each subsequent line contains one integer (per product),
the amount of that product to put in the ship.
(i.e. line k refers to product k-1
e.g. line 2 refers to product 1; how much of product 1 to load onto the ship)

if there are a number of different ways to get the best profit, only one solution is required.

Example:

cargo hold size 10, 3 products
product 1: size 5, profit 3
product 2: size 7, profit 5
product 3: size 6, profit 5

The input will look like this:
10 3
5 3
7 5
6 5

Note that there is a max profit of 6 which is achieved by storing two of product 1. Since product 1 is size 5, the ship can take 2 of them and they are worth 3 each.

The output should look like:
6
2
0
0

Example 2:

input:
23 4
10 5
11 6
3 1
6 2

output:
12
0
2
0
0

## Q4_SNR - Polygon

Consider a convex polygon with N vertices, with the additional property that no three diagonals intersect in a single point. Find the number of intersections between pairs of diagonals in such a polygon.

The image below shows one such polygon with 6 vertices.

Note: a polygon is convex if all of its interior angles are less than 180 degrees.

Input

The first and only line of input contains a single integer N, 3 ≤ N ≤ 100.

Output

Output the number of intersections on a single line.

Sample test data

input1
3
output1
0

input2
4
output2
1

input3
6
output3
15

AttachmentSize