2017 Hackatari Codeathon
A. The Fault in Our Cubes
time limit per test
0.5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Rula is the Human Resources Manager at Mixed Dimensions Inc. She has some very delightful puzzles for the employees to enjoy their free time at the office. One of these puzzles is the Worm Puzzle.

The puzzle consists of 27 cubic pieces of several types. The pieces are connected by a rope that runs through holes in the pieces, and allows the pieces to rotate. In order to solve the puzzle, you need to build a 3x3x3 cube.

Each piece has one of the following three types:

  • Type E represents an end cube, it has a hole at one face only. This piece is always connected to only one other piece.
  • Type I represents a cube which has two holes on opposite faces, the rope goes straight into one hole and out through the other.
  • Type L represents a cube which has two holes in two adjacent faces, the rope enters through one face, makes a 90 degree turn, and exits through the other face.

Well, Hasan has cut the rope of the puzzle by mistake, of course he didn’t want to tell Rula about it, so he bought a new rope and linked the pieces together to make a new Worm Puzzle, but he wasn't sure whether he linked them in their original order or not.

Now Rula has been trying to solve the puzzle for two days, but with no success, although she used to solve it in 30 seconds. She started to suspect that something might be wrong with the puzzle.

She asked one of the engineers at Mixed Dimensions to verify whether the puzzle is solvable or not. Unfortunately, that engineer was Hasan, and of course, the question is difficult for him to answer.

Given the type of each piece, and the order in which Hasan linked the pieces together, can you help him by finding whether the given puzzle is solvable or not?

Input

The input consists of a string of 27 letters, each letter will be either an E, I, or L, which represents the type of that piece.

The first and last letters are always E.

Output

Print YES if the given puzzle is solvable, otherwise print NO.

Examples
Input
EILILLLLLLILILLLLLLILILLLLE
Output
YES
Input
EILLLILLILLLILILLLLILILILIE
Output
YES
Input
EILLILLLILLILLLILLLILLLLILE
Output
NO

B. 2Trees
time limit per test
0.75 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given two trees with the same number of leaves L, your task is to merge the two trees' leaves in a way that ensures the following:

  • The number of colors needed to color the resulting graph such that no two adjacent nodes share the same color is minimum.
  • Each leaf in the first tree is merged into exactly one leaf from the second tree.
  • Each leaf in the second tree is merged into exactly one leaf from the first tree.
  • Nodes other than leaves are not merged.

Note that by merging two leaves a and b, the resulting node will have both edges of a and b.

Input

The first line of input contains one integer N (3 ≤ N ≤ 105), the number of nodes in the first tree.

Then follows N - 1 lines, the ith line contains two integers u and v (1 ≤ u, v ≤ N), the indices of the nodes connected by the ith edge in the first tree.

The next line contains an integer M (3 ≤ M ≤ 105), the number of nodes in the second tree.

Then follows M - 1 lines, the ith line contains two integers u and v (1 ≤ u, v ≤ M), the indices of the nodes connected by the ith edge in the second tree.

It is guaranteed that the two trees will have the same number of leaves L.

Output

On a single line print the number of colors needed to color the resulting graph.

Followed by L lines, the ith line of them contains two integers u and v (1 ≤ u ≤ N)(1 ≤ v ≤ M), the indices of the leaves to be merged, where u is a leaf in the first tree, and v is a leaf in the second tree.

If there’s more than one possible solution, print any of them.

Examples
Input
3
1 2
1 3
3
3 1
2 3
Output
2
2 1
3 2
Input
4
1 2
2 3
3 4
3
3 1
1 2
Output
3
4 2
1 3
Note
  • A tree of N nodes is a connected undirected graph with N - 1 edges.
  • A node is a leaf if and only if it is connected to at most one other node.

In the first sample, the two trees can be illustrated as follows:

After merging node 2 from first tree with node 1 from the second tree, and node 3 from the first tree with node 2 from the second tree, the resulting graph is illustrated in the figure below:

The minimum number of colors required to satisfy the problem constraints is 2.

C. Arcade
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Abdullah and Haritha were building a 3D printed arcade machine. Abdullah had worked on the hardware, while Haritha had been working on the game that will be running on the arcade machine.

The game is represented as a 2D grid of R rows and C columns. The goal of the game is to build the maximum possible number of Hackatari logos. Hackatari's logo consists of 5 symbols, they are: {x, o,  > ,  - , | }. When the game starts, the player will have an infinite number of the first two symbols {x,  and o}.

Each cell of the grid contains one of the three-to-last symbols of the logo, specifically, { > ,  - ,  or | }.

The player is placed at the top-left cell, and is only allowed to move to the cell below him, or to the one to his right. The player is not allowed to go outside the grid. To collect a symbol from a cell, the player needs to move to that cell. The goal of the game is to build the maximum number of Hackatari logos using the collected symbols.

Abdullah was testing Haritha’s game, recently, and he got a score of 103%, which means that the maximum score that Haritha expected, was less than the maximum score that the player can actually achieve.

Can you help Haritha fix his game by writing a program that finds the maximum number of logos that can actually be built??

Input

The first line of input contains two integers, R and C (1 ≤ R, C ≤ 100), the number of rows and the number of columns in the grid, respectively.

Each of the following R lines contains C characters, each character belongs to the set: { > ,  - , | }.

Output

On a single line, print the maximum number of Hackatari logos.

Examples
Input
3 4
>|>-
-|->
->-|
Output
2
Input
4 2
>-
>-
>-
||
Output
1

D. !Hasan
time limit per test
0.25 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Mixed Dimensions Onsite Round will host N contestants this year.

Moath and Saif have been preparing the contest hall, Moath needs X minutes to set up a computer for the contest, while Saif needs Y minutes to set up a computer. Each one of them works separately on one computer at a time.

Hasan is concerned they won't finish setting up the PCs in time, can you help Hasan figure out the minimum time required by Moath and Saif to set up all N PCs for the contest?

Input

The input contains 3 integers, N, X, and Y (1 ≤ N, X, Y ≤ 109), the number of PCs to set up, the amount of minutes Moath needs to set up a computer, and the amount of minutes Saif needs to set up a computer, respectively.

Output

On a single line, print one integer, the minimum number of minutes required by Moath and Saif to set up all the PCs for the contest.

Examples
Input
5 3 4
Output
9
Input
100 10 1
Output
91

E. Another Step-by-Step Pupil
time limit per test
0.25 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Hamza is a new intern at Mixed Dimensions, and he's learning the basics about 3D models. Hasan gave him an easy task on his first day, he has to count the number of boundary edges in a 3D mesh.

A boundary edge in a 3D mesh is an edge that is a part of only one triangle. Hamza got so confused, and asked Hasan to simplify the problem. Hasan decided to give him only two triangles. But he still can’t figure it out. Given the names of the vertices that make up the two triangles, can you help Hamza find the number of boundary edges in the two triangles?

Input

The input consists of two lines, each line describes one triangle, and contains 3 distinct integers from 1 to 6 which represent the names of the vertices of each triangle. It is guaranteed that the two triangles are different by at least one vertex.

Output

Print one integer, the number of boundary edges in the two given triangles.

Examples
Input
3 5 2
3 1 2
Output
4
Input
6 1 4
5 2 3
Output
6
Note

The first sample results in the following 2 triangles with 4 boundary edges (in green):

F. Islands II
time limit per test
1.5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

The world of Bitland is an N × M grid with K islands numbered from 1 through K. An island is a group of connected cells. Two cells are connected if you can start in one of them and reach the other one by moving only to adjacent cells. Two cells are adjacent if they share a side.

The picture above shows a world with 9 islands, each island is represented by a unique color.

As you can see, in Bitland, islands may contain other islands, and so to avoid ambiguity, Bitland was built in a way that will never allow the following situation:

If you don't see why it's ambiguous, well, we can't tell whether the blue island is contained inside the green one or not.

More formally, for any 2 × 2 sub-grid of Bitland, if the cells on one of the two diagonals belong to the same island, then there's at least one more cell that belongs to the same island in this sub-grid.

Your task this time is to find the number of sub-islands contained in each island in Bitland.

Input

The first line of input contains two space-separated integers, N and M (1 ≤ N, M ≤ 1000), the number of rows and columns of the grid, respectively.

Each of the following N lines contains M integers, each integer is between 1 and K, where K is the number of islands.

It is guaranteed that the input is valid and matches the description of the problem statement.

Output

On a single line, print K integers, the ith integer represents the number of sub-islands contained in the ith island.

Examples
Input
5 5
1 1 1 1 1
1 2 2 2 1
1 2 3 2 1
1 2 2 2 1
1 1 1 1 1
Output
2 1 0
Input
5 6
1 1 1 1 1 1
1 2 2 4 4 1
1 2 3 3 4 1
1 2 2 4 4 1
1 1 1 1 1 1
Output
3 0 0 0

G. 24
time limit per test
0.5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Round 16,777,216 of Codeforce-is has just finished, and all the contestants were able to pass the pretests in problem A.

Maike, the founder of Codeforce-is wants to measure how weak the tests for problem A were, so he became interested in finding the amount of changes that will occur on the contest’s scoreboard after the system tests.

Given the score for problem A, the score of each contestant before the system tests, and the probability of failing the system tests for each contestant’s solution, can you help Maike find the expected number of pairs of contestants that will swap their relative order after the system tests? That is, the number of pairs of contestants i, j such that the scorei  >  scorej before the system tests, but scorei  <  scorej after the system tests.

Input

The first line of input consists of two integers, N (2 ≤ N ≤ 105), and SA (1 ≤ SA ≤ 105), the number of contestants in the round, and the score the contestants achieved for passing the pretests of problem A.

The second line contains N space-separated integers, the Kth integer is TK (SA ≤ TK ≤ 105) which represents the total score in the contest for the Kth contestant before the system tests, Ti  ≥  Ti + 1 for (1 ≤ i < N).

The third and final line contains N space-separated numbers, the Kth number is PK (0.01 ≤ PK ≤ 1.00) which represents the probability that the Kth contestant's solution will fail the system tests. Numbers are given with exactly two digits after the decimal point.

Output

On a single line, output the expected number of pairs of contestants that will swap their relative order after the system tests are over.

Examples
Input
2 10
25 20
0.50 0.50
Output
0.250000000
Input
4 10
25 20 15 15
1.00 0.50 1.00 0.50
Output
0.750000000

H. Card
time limit per test
0.5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

After Hasan ruined the Worm puzzle, Rula brought a new game to the office, the Card game.

The game has a group of cards, each card has an integer value Vi written on it.

Initially, N cards are placed side by side in a straight line (refer to the picture above). In each turn you will pick two adjacent card sets (a single card is also considered a card set) and merge the cards of the two sets together to form one new set.

After each turn, you will add the maximum card value in each card set to your score. The game is over when no more merges could be performed.

What is the maximum score you can get at the end of the game, given that your initial score is 0?

Input

The first line of input contains a single integer N (2 ≤ N ≤ 105), the number of cards in the game.

The second line contains N space-separated integers, each integer is Vi (1 ≤ Vi ≤ 5000), which represents the number written on the ith card.

Output

On a single line, print the maximum score you can get.

Examples
Input
5
1 2 3 2 1
Output
23
Input
6
7 9 7 5 4 3
Output
108
Note

One of the possible solutions for the first sample is as follows:

  • Initially, each set will contain a single card: {1} {2} {3} {2} {1}.
  • Merge {1} with {2}, the resulting sets are: {1 2} {3} {2} {1}, which will add (2 + 3 + 2 + 1 = 8) to your score.
  • Merge {2} with {1}, the resulting sets are: {1 2} {3} {2 1}, which will add (2 + 3 + 2 = 7) to your score.
  • Merge {1 2} with {3}, the resulting sets are: {1 2 3} {2 1}, which will add (3 + 2 = 5) to your score.
  • Merge {1 2 3} with {2 1}, the resulting sets are: {1 2 3 2 1}, which will add 3 to your score.

Final score is 8 + 7 + 5 + 3 = 23.

I. K, Push.
time limit per test
0.75 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Rawand is designing a new game she called K, Push. for the employees at Mixed Dimension.

In K, Push., a group of N players sit in a circle, and each player has a red button in front of them.

When the game starts, an empty array is displayed on a large screen behind the players, and every few seconds, a random integer v is inserted into the array after some random index i. The first integer is always inserted after index 0 i.e., it is always inserted at index 1.

The players must keep watching the screen, and each player should push his button only if he thinks there is an increasing sub-sequence of length K in the array. The first player to do so is declared the winner, and the game ends. On the other hand, if a player pushes his button and there is no increasing sub-sequence of length K in the array, that player loses and is automatically considered out of the game. The remaining players will continue playing until the game's time ends, in this case all players will lose, or until only one player remains in the game, in this case, that player is declared the winner.

Rawand cannot wait to start the game, but she needs some help implementing the game's system. Given a random list of game events, can you help Rawand by writing a software that selects the winner of K, Push. based on the list events?

Input

The first line of input contains three integers, N (2 ≤ N ≤ 105), K (1 ≤ K ≤ 105) and E (1 ≤ E ≤ 2 × 105), the number of players in a game instance, the size of the required increasing sub-sequence, and the number of events in the event list.

Each of the E lines that follow will contain an event with one of the following formats:

  •  +  i v, where v (1 ≤ v ≤ 105) is an integer that got inserted after the element with index i (0 ≤ i ≤ currentSize).
  • p j, which denotes that player number j (1 ≤ j ≤ N) pushed his button.

It is guaranteed that there are no more than 105 events of the first type.

It is possible that the last event in the log is of type  + , and it is guaranteed that losing players will not appear in the input after losing.

Output

On a single line, print out the index of the first event at which a winner should be declared, also, print the number of that winner on the same line.

If there’s no such winner, output  - 1 on a single line.

Examples
Input
4 4 11
+ 0 14
+ 0 9
p 1
+ 2 19
+ 1 11
p 4
+ 0 1
+ 2 10
p 2
+ 1 3
+ 6 16
Output
6 4
Input
2 6 9
+ 0 14
+ 0 9
+ 2 19
+ 1 11
p 1
+ 0 1
+ 2 10
+ 1 3
+ 6 16
Output
5 2
Note

A sub-sequence is a sequence that can be derived from another sequence by deleting some elements without changing the order of the remaining elements. For example, the sequence {1, 5, 4} is a sub-sequence of {2, 1, 5, 3, 4, 9}.