You are hereProgramming Problems / 2016 AIPO National Finals Problems

# 2016 AIPO National Finals Problems

## Problem 1 - Chessboard

Write a program that prints a chessboard with N rows and M columns with the following rules:

- The top left cell must be an asterisk (*)
- Any cell touching (left, right, up or down) a cell with an asterisk must be a dot (.)
- Any cell touching (left, right, up or down) a cell with a dot must be an asterisk.

A chessboard of 8 rows and 8 columns printed using these rules would be:

*.*.*.*.

.*.*.*.*

*.*.*.*.

.*.*.*.*

*.*.*.*.

.*.*.*.*

*.*.*.*.

.*.*.*.*

Input

A single line with two integers N and M separated by spaces. The number N will represent the number of rows and M the number of columns. N and M will be between 1 and 10.

Output

Print N lines each containing M characters with the chessboard pattern.

Input Example 1
1 1 |
Output Example 1
* |

Input Example 2
8 8 |
Output Example 2
*.*.*.*. .*.*.*.* *.*.*.*. .*.*.*.* *.*.*.*. .*.*.*.* *.*.*.*. .*.*.*.* |

Input Example 3
1 5 |
Output Example 3
*.*.* |

Input Example 4
6 1 |
Output Example 4
* . * . * . |

Input Example 5
2 5 |
Output Example 5
*.*.* .*.*. |

## Problem 2 - LCM

The integer A is multiple of B if we can multiply B by some integer number bigger than 0 we get A.

Examples:

- 10 is multiple of 5 because 5*2 is 10
- 10 is multiple of 10 because 10*1 is 10
- 6 is multiple of 1 because 1*6 is 6
- 20 is multiple of 1, 2, 4, 5, 10 and 20.

We call the lowest common multiple of A and B to the the smallest positive integer C that is a multiple of both A and B.

Some examples:

- The lowest common multiple of 2 and 5 is 10 because 10 is multiple of 2 and 5 and there is no other common multiple that is smaller.
- The lowest common multiple of 10 and 20 is 20.
- The lowest common multiple of 5 and 3 is 15.

Your task is to write a program that computes the lowest common multiple of 2 numbers.

Input

A single line containing 2 integers A and B separated by one space.

In 50% of the test cases, the number A and B will be less than 1000 (103). In the other 50% of the test cases, the numbers A and B may be bigger than 1000 but smaller than 100000000 (108).

Note: For the larger test cases you’ll need to declare your variables as 64 bits integers. Use long long int in C/C++ and long in Java.

Output

Print a single line containing an integer, the lowest common multiple of A and B.

Input Example 1
1 1 |
Output Example 1
1 |

Input Example 2
3 5 |
Output Example 2
15 |

Input Example 3
1 123 |
Output Example 3
123 |

Input Example 4
121 199 |
Output Example 4
24079 |

## Problem 3 - Harps and Tails

Gary likes the Celtic Harp that appears in the 1 euro coins.

He has a grid of n rows and m columns of such coins. Each coin has either the harp or the tail facing up.

Gary also loves order, he wants as many rows as possible with all the coins showing the Celtic Harp. To make things interesting he can only do the following operation: choose any column and turn all the coins in this column. That is, any coin showing the Harp will change to tails and any coin showing tails will turn to the Harp.

Gary can perform this operation as many times as he wants to maximize the number of rows with all Harps. Can you help him?

Example: We have the following grid of coins. Coins with tails are represented with the character T and coins with the Harp are represented by H.

T H T H

H T T T

H H H H

T H T H

In this state, only one row show all Harps. If we change the first column we obtain:

H H T H

T T T T

T H H H

H H T H

Then we change the third row to obtain:

H H H H

T T H T

T H T H

H H H H

In this state the first and fourth rows are all Harps which is the best we can get. Hence our answer will be 2.

Input

The first line of input contains 2 integers n and m (1 ≤ n, m ≤ 1000) representing the number of rows and columns of the grid.

The next n lines will describe the state of the grid. The i-th line will contain a string with n characters denoting the state of the i-th row of the grid. The j-th character on this line is 'T' if the j-th square in the i-th row contains a tail, and 'H' if contains a Harp.

Output

The output should be a single line containing an integer equal to a maximum possible number of rows that are completely converted to Harps (‘H’).

Input Example 1
4 4 THTH HTTT HHHH THTH |
Output Example 1
2 |

Input Example 2
3 5 TTTTT TTTTT TTTTT |
Output Example 2
3 |

Input Example 3
10 11 THHHTHTTHHH THHHTHTTHHH HTHTTHTTTHH THHHTHTTHHH TTTTHHTTTTH THHHTHTTHHH THHHTHTTHHH TTTTHHTTTTH HTHTTHTTTHH THHHTHTTHHH |
Output Example 3
6 |

## Problem 4 - Non-decreasing subsegment

We want to compute the longest non-decreasing subsegment of a list of n integer numbers.

A subsegment is a continuous piece of the list. For example: In the list [1, 2, 3, 4, 5], we have subsegments such as [1, 2, 3, 4], [2, 3] or [3, 4]. [1, 3, 4, 5] is not a subsegment because 1 and 3 are not continuous in the original list.

Given the list [3, 1, 2, 4, 2, 2, 3, 6] the non-decreasing subsegments are:

- [3], [1], [2], [4], [2], [2], [3], [6] (each element is a subsegment by itself)
- [1, 2, 4]
- [2, 2, 3, 6] (notice the sequence never decreases)

Hence the longest subsegment is [2, 2, 3, 6] and has a size of 4 elements.

You’ll need to compute the length of the longest subsegment and the sum of these elements. In a case of more than one non-decreasing subsegment with the maximum length, return the length and the sum of the one who appears first in the input.

Input

The first line will contain an integer n (1 ≤ n ≤ 105), the size of the list. The next line will contain n integers, the elements of the list, separated by spaces (the values will be between 1 and 109).

Output

Two integers separated by a single space: the first one representing the size of the longest non-decreasing subsegment of the list and the second it’s sum. In the case of equally longest non-decreasing subsegment, output the length and the sum of the subsegment that appears first.

Input Example 1
5 1 2 3 4 5 |
Output Example 1
5 15 |

Input Example 2
9 514 630 327 242 504 763 353 699 486 |
Output Example 2
3 1509 |

Input Example 3
7 449 434 996 140 918 205 948 |
Output Example 3
2 1430 |

Input Example 4
5 721 231 521 613 792 |
Output Example 4
4 2157 |

## Problem 5 - Tree

One of the most important data structures in computer science is the tree. You already dealt with binary trees in the qualification round. This problem is about general trees.

Trees are the subset of graphs that have the following 3 properties:

- A graph (a set of N nodes and M edges) is a tree when it is connected: for every node you can reach every other node following edges.
- A graph is not a tree if an edge is removed and the graph is no longer connected. That is, some nodes cannot be reached anymore.
- A graph is not a tree if, when an edge is added between two existing nodes A and B, a cycle is created. There is a cycle if there is more than one way to go from A to B.

A few examples:

The tree graphs in the first row are trees. You can check that they match our tree conditions.

The graphs in the second row are not trees. The one on the left has more than one edge connecting 1 and 2. The middle graph is disconnected. The one on the right has a cycle composed by the nodes 1, 3, 7 and 6.

You task is to decide if a given graph is a tree or not.

Input

The first line will contain an integer T representing the number of graphs to check. There will be at most 10 graphs in each test case.

Each of the graph will be represented as follows:

The first line will contain an integer N with the number of nodes in the graph. The number of nodes will be between 1 and 1000. The identifier of each node will be an integer from 1 to N.

The next line will contain an integer M with the number of edges in the graph. There will be at most 106 edges.

The next M lines will contain 2 integers A and B each. These are the two nodes connected by an edge.

Output

For each graph, a single line with “tree” if the graph represents a tree or “graph“ otherwise.

Input Example 1
2 4 3 2 1 3 4 1 3 3 3 1 2 1 2 3 2 |
Output Example 1
tree graph |

Input Example 2
2 7 5 7 2 2 4 4 3 5 6 6 1 7 6 7 2 2 4 4 3 4 5 6 5 1 6 |
Output Example 2
graph tree |

## Problem 6 - Sum of digits

It is easy to compute the sum of the numbers in the sequence from 0 to n with the formula n*(n+1)/2. That is: 0 + 1 + 2 + .... + n = n*(n+1)/2

This problem is a bit harder: what about the sum of the digits in the sequence [0, 1, ..., n]?

Write a program that computes the sum of the digits that can be found when counting from 0 to n.

Example:

For n = 15 we want to sum the digits that appear in the sequence [0, 1, 2, ..., 14, 15].

The result is: 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 + 1 + 0 +1 + 1 + 1 + 2 + 1 + 3 + 1 + 4 + 1 + 5 = 66

Input

A single line with an integer n (1 ≤ n ≤ 1016)

Output

A single line with the sum of digits in the sequence [0, 1, ..., n-1, n]

Note: For the larger test cases you’ll need to declare your variables as 64 bits integers. Use long long int in C/C++ and long in Java.

Input Example 1
15 |
Output Example 1
66 |

Input Example 2
9935125239801570 |
Output Example 2
714619374344308434 |

Input Example 3
1000 |
Output Example 3
180001 |

Input Example 4
83 |
Output Example 4
678 |