Author:  ACM ICPC NEERC 2010 Jury  
Input file:  alignment.in  Time limit:  2 sec  
Output file:  alignment.out  Memory limit:  256 Mb 
You are working in a team that writes Incredibly Customizable Programming Codewriter (ICPC) which is basically a text editor with bells and whistles. You are working on a module that takes a piece of code containing some definitions or other tabular information and aligns each column on a fixed vertical position, while keeping the resulting code as short as possible, making sure that only whitespaces that are absolutely required stay in the code. So, that the first words on each line are printed at position p_{1} = 1; the second words on each line are printed at the minimal possible position p_{2}, such that all first words end at or before position p_{2} − 2; the third words on each line are printed at the minimal possible position p_{3}, such that all second words end at or before position p_{3} − 2, etc.
For the purpose of this problem, the code consists of multiple lines. Each line consists of one or more words separated by spaces. Each word can contain uppercase and lowercase Latin letters, all ASCII punctuation marks, separators, and other nonwhitespace ASCII characters (ASCII codes 33 to 126 inclusive). Whitespace consists of space characters (ASCII code 32).
The input file contains one or more lines of the code up to the end of file. All lines (including the last one) are terminated by a standard endofline sequence in the file. Each line contains at least one word, each word is 1 to 80 characters long (inclusive). Words are separated by one or more spaces. Lines of the code can have both leading and trailing spaces. Each line in the input file is at most 180 characters long. There are at most 1000 lines in the input file.
Write to the output file the reformatted, aligned code that consists of the same number of lines, with the same words in the same order, without trailing and leading spaces, separated by one or more spaces such that ith word on each line starts at the same position p_{i}.
No.  Input file (alignment.in ) 
Output file (alignment.out ) 

1 


Author:  ACM ICPC NEERC 2010 Jury  
Input file:  binary.in  Time limit:  2 sec  
Output file:  binary.out  Memory limit:  256 Mb 
Consider a binary operation op defined on digits 0 to 9, op: digs × digs ↦ digs, such that 0op 0 = 0.
A binary operation opd is a generalization of op to the set of nonnegative integers, opd: nneg × nneg ↦ nneg. The result of aopd b is defined in the following way: if one of the numbers a and b has fewer digits than the other in decimal notation, then append leading zeroes to it, so that the numbers are of the same length; then apply the operation op digitwise to the corresponding digits of a and b.
Let us define opd to be leftassociative, that is, aopd bopd c is to be interpreted as (aopd b)opd c.
Given a binary operation op and two nonnegative integers a and b, calculate the value of res.
The first ten lines of the input file contain the description of the binary operation op. The ith line of the input file contains a spaceseparated list of ten digits — the jth digit in this list is equal to (i−1)op (j−1).
The first digit in the first line is always 0.
The eleventh line of the input file contains two nonnegative integers a and b (0 ≤ a ≤ b ≤ 10^{18}).
Output a single number — the value of res without extra leading zeroes.
No.  Input file (binary.in ) 
Output file (binary.out ) 

1 


Author:  ACM ICPC NEERC 2010 Jury  
Input file:  cactus.in  Time limit:  3 sec  
Output file:  cactus.out  Memory limit:  256 Mb 
Advanced Cave Megapolis (ACM) is a city that survives in the underground caves after the global nuclear war. The caves are connected by passages and the whole city map can be represented by a graph with caves being vertices and passages between them being nodes.
There is a revolution in the cave city. The whole population of the city is evenly split into k parties that cannot agree on the common laws that they should adopt. They had decided to split their city into k districts and have each district's citizens impose the laws of their liking upon themselves.
You are given a city map in the form of the graph and your task is to write a program that partitions this graph into k equally sized districts. Each district must form a connected subgraph that is represented by the subset of the graph's vertices.
Fortunately, the number of vertices in the graph is divisible by k and the graph representing the city happens to be a cactus — a connected undirected graph in which every edge belongs to at most one simple cycle. Intuitively, cactus is a generalization of a tree where some cycles are allowed.
The example of a city map with 15 caves and its partitioning into 3 districts is shown on the picture below.
The first line of the input file contains three integer numbers n, m, and k (1 ≤ n ≤ 50 000, 0 ≤ m ≤ 10 000, 1 ≤ k ≤ n). Here n is the number of vertices in the graph. Vertices are numbered from 1 to n. Edges of the graph are represented by a set of edgedistinct paths, where m is the number of such paths, k is the number of districts that the city must be partitioned into, n is divisible by k.
Each of the following m lines contains a path in the graph. A path starts with an integer number s_{i} (2 ≤ s_{i} ≤ 1000) followed by s_{i} integers from 1 to n. These s_{i} integers represent vertices of a path. Adjacent vertices in a path are distinct. Path can go through the same vertex multiple times, but every edge is traversed exactly once in the whole input file. There are no multiedges in the graph (there is at most one edge between any two vertices).
The graph in the input file is a cactus.
If it is possible to partition the vertices into k districts, write to the output file k lines with n/k integer numbers on each line. Each line represents a district as a list of vertices' numbers that constitute it. Vertex numbers must be listed in the ascending order in the description of each district.
If the answer does not exist, write the single number −1.
No.  Input file (cactus.in ) 
Output file (cactus.out ) 

1 


2 


Author:  ACM ICPC NEERC 2010 Jury  
Input file:  dome.in  Time limit:  2 sec  
Output file:  dome.out  Memory limit:  256 Mb 
A travelling circus faces a tough challenge in designing the dome for its performances. The circus has a number of shows that happen above the stage in the air under the dome. Various rigs, supports, and anchors must be installed over the stage, but under the dome. The dome itself must rise above the center of the stage and has a conical shape. The space under the dome must be airconditioned, so the goal is to design the dome that contains minimal volume.
You are given a set of n points in the space; (x_{i}, y_{i}, z_{i}) for 1 ≤ i ≤ n are the coordinates of the points in the air above the stage that must be covered by the dome. The ground is denoted by the plane z = 0, with positive z coordinates going up. The center of the stage is on the ground at the point (0, 0, 0).
The tip of the dome must be located at some point with coordinates (0, 0, h) with h > 0. The dome must have a conical shape that touches the ground at the circle with the center in the point (0, 0, 0) and with the radius of r. The dome must contain or touch all the n given points. The dome must have the minimal volume, given the above constraints.
The first line of the input file contains a single integer number n (1 ≤ n ≤ 10 000) — the number of points under the dome. The following n lines describe points with three floating point numbers x_{i}, y_{i}, and z_{i} per line — the coordinates of ith point. All coordinates do not exceed 1000 by their absolute value and have at most 2 digits after decimal point. All z_{i} are positive. There is at least one point with nonzero x_{i} or y_{i}.
Write to the output file a single line with two floating point numbers h and r — the height and the base radius of the dome. The numbers must be precise up to 3 digits after decimal point.
No.  Input file (dome.in ) 
Output file (dome.out ) 

1 


2 


3 


Author:  ACM ICPC NEERC 2010 Jury  
Input file:  evacuation.in  Time limit:  3 sec  
Output file:  evacuation.out  Memory limit:  256 Mb 
Flatland government is building a new highway that will be used to transport weapons from its main weapon plant to the frontline in order to support the undergoing military operation against its neighbor country Edgeland. Highway is a straight line and there are n construction teams working at some points on it.
During last days the threat of a nuclear attack from Edgeland has significantly increased. Therefore the construction office has decided to develop an evacuation plan for the construction teams in case of a nuclear attack. There are m shelters located near the constructed highway. This evacuation plan must assign each team to a shelter that it should use in case of an attack.
Each shelter entrance must be securely locked from the inside to prevent any damage to the shelter itself. So, for each shelter there must be some team that goes to this shelter in case of an attack. The office must also supply fuel to each team, so that it can drive to its assigned shelter in case of an attack. The amount of fuel that is needed is proportional to the distance from the team's location to the assigned shelter. To minimize evacuation costs, the office would like to create a plan that minimizes the total fuel needed.
Your task is to help them develop such a plan.
The first line of the input file contains n — the number of construction teams (1 ≤ n ≤ 4000). The second line contains n integer numbers — the locations of the teams. Each team's location is a positive integer not exceeding 10^{9}, all team locations are different.
The third line of the input file contains m — the number of shelters (1 ≤ m ≤ n). The fourth line contains m integer numbers — the locations of the shelters. Each shelter's location is a positive integer not exceeding 10^{9}, all shelter locations are different.
The amount of fuel that needs to be supplied to a team at location x that goes to a shelter at location y is equal to x − y.
The first line of the output file must contain z — the total amount of fuel needed. The second line must contain n integer numbers: for each team output the number of the shelter that it should be assigned to. Shelters are numbered from 1 to m in the order they are listed in the input file.
No.  Input file (evacuation.in ) 
Output file (evacuation.out ) 

1 


Author:  ACM ICPC NEERC 2010 Jury  
Input file:  factorial.in  Time limit:  3 sec  
Output file:  factorial.out  Memory limit:  256 Mb 
Peter is working on a combinatorial problem. He has carried out quite lengthy derivations and got a resulting formula that is a ratio of two products of factorials like this:
p_{1}!p_{2}! ... p_{n}!q_{1}!q_{2}! ... q_{m}!
This does not surprise Peter, since factorials appear quite often in various combinatorial formulae, because n! represents the number of transpositions of n elements — one of the basic combinatorial objects.
However, Peter might have made a mistake in his derivations. He knows that the result should be an integer number and he needs to check this first. For an integer result Peter wants to simplify this formula to get a better feeling of its actual combinatorial significance. He wants to represent the same number as a product of factorials like this.
r_{1}!^{s1} r_{2}!^{s2} ... r_{k}!^{sk} t
where all r_{i} are distinct integer numbers greater than one in the descending order (r_{i} > r_{i+1} > 1), s_{i} and t are positive integers. Among all the possible representations in this form, Peter is interested in one where r_{1} is the largest possible number, among those in the one where s_{1} is the largest possible number; among those in the one where r_{2} is the largest possible number; among those in the one where s_{2} is the largest possible number; etc, until the remaining t cannot be further represented in this form. Peter does not care about the actual value of t. He wants to know what is the factorialproduct part of his result.
The first line of the input file contains two integer numbers n and m (1 ≤ n, m ≤ 1000). The second line of the input file contains n integer numbers p_{i} (1 ≤ p_{i} ≤ 10 000) separated by spaces. The third line of the input file contains m integer numbers q_{i} (1 ≤ q_{i} ≤ 10 000) separated by spaces.
On the first line of the output write a single integer number k. Write k = −1 if the ratio of the given factorial products is not an integer. Write k = 0 if the ratio is an integer but it cannot be represented in the desired form. Write k > 0 followed by k lines if the ratio can be represented by a factorial product as described in the problem statement. On each of the following k lines write two integers r_{i} and s_{i} (for i = 1 ... k) separated by a space.
No.  Input file (factorial.in ) 
Output file (factorial.out ) 

1 


2 


3 


Author:  ACM ICPC NEERC 2010 Jury  
Input file:  standard input  Time limit:  3 sec  
Output file:  standard output  Memory limit:  256 Mb 
The Game of 10 is played by two players on a 4 × 4 field. Initially all 16 cells of the field are empty. Players make alternating moves. On each move a player writes a number from 1 to 4 into an empty cell. The first player that makes any row or column filled with four numbers with a sum of 10 wins. If all cells are filled but no row or column has a sum of 10, then a draw is declared.
You have to write a program that plays for the second player and always wins.
The table below shows the field after the sample game that is shown in the ``Sample input and output'' section. Subscripts denote the number of the move in the game starting from the first one, with 14th being the last and winning move by the second player. The last move in the game had filled the second column with a sum of 10.
\Interaction
The interaction starts with your program reading the first player's move from the standard input. Then your program must write its move to the standard output, wait for the first player's move in the standard input and so on.
Your program must exit after writing the last, winning move to the standard output. Your program must write endofline sequence and flush the standard output after each move, including the last, winning move.
The standard input consists of the first player's moves. Each move is represented by a single line that contains three integer numbers r, c, and k (1 ≤ r, c, k ≤ 4) separated by spaces, where r and c are row and column numbers, and k is the number that the first player writes into the cell (r, c).
The standard output consists of the second player's moves. Each move is represented by a single line of the same format as in the standard input. The last, winning move, shall have an extra word "WIN" (without quotes) on the same line after the three numbers that denote the move, separated from them by a space.
No.  Input file (standard input ) 
Output file (standard output ) 

1 


Author:  ACM ICPC NEERC 2010 Jury  
Input file:  hands.in  Time limit:  3 sec  
Output file:  hands.out  Memory limit:  256 Mb 
The standard 52card deck consists of 52 cards divided into 4 suits: clubs, diamonds, hearts and spades. For each suit there are 13 ranks: 2, 3, 4, 5, 6, 7, 8, 9, 10, jack, queen, king and ace, listed from the lowest to the highest.
A card is denoted by its rank (2… 9 for 2… 9, T for 10, J for jack, Q for queen, K for king, and A for ace) followed by its suit (C for clubs, D for diamonds, H for hearts, and S for spades). Cards are partially ordered by their ranks. The suit does not play a role in the cards ordering.
A Poker hand is a set of five distinct cards. Each hand is said to have a certain ranking. A hand with a higher ranking beats a hand with a lower one. Two hands of the same ranking are compared using a tiebreaking rule specific for their ranking — either one of them beats the other or they are tied.
The list of poker rankings is given below, from the worst ranking to the best ranking. If a hand satisfies several rankings, only the best one is considered.
Consider the set h of all Poker hands. Let us introduce an evaluation function v: h ↦ {1, …, m}, such that for any two Poker hands a and b, a beats b if and only if v(a) > v(b). There exists exactly one such evaluation function v.
Given a Poker hand a, find the value of v(a).
The input file contains spaceseparated list of five distinct card descriptions. Each card is described with two characters denoting its rank and suit, respectively. The ranks are denoted by 2… 9, T, J, Q, K, and A (listed here in the ascending order). The suits are denoted by C, D, H, and S.
Output the value of the evaluation function v(a) for the given hand a.
No.  Input file (hands.in ) 
Output file (hands.out ) 

1 


2 


Author:  ACM ICPC NEERC 2010 Jury  
Input file:  ideal.in  Time limit:  3 sec  
Output file:  ideal.out  Memory limit:  256 Mb 
New labyrinth attraction is open in New Lostland amusement park. The labyrinth consists of n rooms connected by m passages. Each passage is colored into some color c_{i}. Visitors of the labyrinth are dropped from the helicopter to the room number 1 and their goal is to get to the labyrinth exit located in the room number n.
Labyrinth owners are planning to run a contest tomorrow. Several runners will be dropped to the room number 1. They will run to the room number n writing down colors of passages as they run through them. The contestant with the shortest sequence of colors is the winner of the contest. If there are several contestants with the same sequence length, the one with the ideal path is the winner. The path is the ideal path if its color sequence is the lexicographically smallest among shortest paths.
Andrew is preparing for the contest. He took a helicopter tour above New Lostland and made a picture of the labyrinth. Your task is to help him find the ideal path from the room number 1 to the room number n that would allow him to win the contest.
Note
A sequence (a_{1}, a_{2}, …, a_{k}) is lexicographically smaller than a sequence (b_{1}, b_{2}, …, b_{k}) if there exists i such that a_{i} < b_{i}, and a_{j} = b_{j} for all j < i.
The first line of the input file contains integers n and m — the number of rooms and passages, respectively (2 ≤ n ≤ 100 000, 1 ≤ m ≤ 200 000). The following m lines describe passages, each passage is described with three integer numbers: a_{i}, b_{i}, and c_{i} — the numbers of rooms it connects and its color (1 ≤ a_{i}, b_{i} ≤ n, 1 ≤ c_{i} ≤ 10^{9}). Each passage can be passed in either direction. Two rooms can be connected with more than one passage, there can be a passage from a room to itself. It is guaranteed that it is possible to reach the room number n from the room number 1.
The first line of the output file must contain k — the length of the shortest path from the room number 1 to the room number n. The second line must contain k numbers — the colors of passages in the order they must be passed in the ideal path.
No.  Input file (ideal.in ) 
Output file (ideal.out ) 

1 


Author:  ACM ICPC NEERC 2010 Jury  
Input file:  jungle.in  Time limit:  3 sec  
Output file:  jungle.out  Memory limit:  256 Mb 
There is a military base lost deep in the jungle. It is surrounded by n watchtowers with ultrasonic generators. In this problem watchtowers are represented by points on a plane.
Watchtowers generate ultrasonic field and protect all objects that are strictly inside the towers' convex hull. There is no tower strictly inside the convex hull and no three towers are on a straight line.
The enemy can blow up some towers. If this happens, the protected area is reduced to a convex hull of the remaining towers.
The base commander wants to build headquarters inside the protected area. In order to increase its security, he wants to maximize the number of towers that the enemy needs to blow up to make the headquarters unprotected.
The first line of the input file contains a single integer n (3 ≤ n ≤ 50 000) — the number of watchtowers. The next n lines of the input file contain the Cartesian coordinates of watchtowers, one pair of coordinates per line. Coordinates are integer and do not exceed 10^{6} by absolute value. Towers are listed in the order of traversal of their convex hull in clockwise direction.
Write to the output file the number of watchtowers the enemy has to blow up to compromise headquarters protection if the headquarters are placed optimally.
No.  Input file (jungle.in ) 
Output file (jungle.out ) 

1 


2 


3 


Author:  ACM ICPC NEERC 2010 Jury  
Input file:  kgraph.in  Time limit:  3 sec  
Output file:  kgraph.out  Memory limit:  256 Mb 
You are given a connected undirected graph with an odd number of vertices. The degree of the vertex, by definition, is the number of edges incident to it. In the given graph the degree of each vertex does not exceed an odd number k. Your task is to color the vertices of this graph into at most k distinct colors, so that the colors of any two adjacent vertices are distinct.
The pictures below show two graphs. The first one has 3 vertices and the second one has 7 vertices. In both graphs degrees of the vertices do not exceed 3 and the vertices are colored into at most 3 different colors.
The first line of the input file contains two integer numbers n and m, where n is the number of vertices in the graph (3 ≤ n ≤ 9999, n is odd), m is the number of edges in the graph (2 ≤ m ≤ 100 000). The following m lines describe edges of the graph, each edge is described by two integers a_{i}, b_{i} (1 ≤ a_{i}, b_{i} ≤ n, a_{i} ≠ b_{i}) — the vertex numbers connected by this edge. Each edge is listed at most once. The graph in the input file is connected, so there is a path between any pair of vertices.
On the first line of the output file write a single integer number k — the minimal odd integer number, such that the degree of any vertex does not exceed k. Then write n lines with one integer number c_{i} (1 ≤ c_{i} ≤ k) on a line that denotes the color of ith vertex.
The colors of any two adjacent vertices must be different. If the graph has multiple different colorings, print any of them. At least one such coloring always exists.
No.  Input file (kgraph.in ) 
Output file (kgraph.out ) 

1 


2 

