2020-2021 ICPC East Central North America Regional Contest (ECNA 2020)
A. All in the Family
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

The scientists working at the Family Genetics Institute are tracing the spread of a hereditary disease through family trees. They have started by listing the family members that have the disease, and the parent who passed the disease on to each child (we will assume that each child gets the disease from only one parent). However, the scientists are confused about the names of different family relationships. Parents, grandparents, and siblings they have a handle on. But a relationship like "third cousin, twice removed" has been hard for them to wrap their heads around. After much discussion they came up with some definitions that cleared things up.

Suppose we have two people conveniently named $$$A$$$ and $$$B$$$ and their closest common ancestor is named $$$C$$$ (what are the odds!). We say that $$$A$$$ is $$$m$$$ generations removed from $$$C$$$ if there are $$$m$$$ direct descendants from $$$C$$$ ending with $$$A$$$. Thus if $$$A$$$ is the daughter of $$$C$$$ she is $$$1$$$ generation removed; if she is the granddaughter of $$$C$$$ she is $$$2$$$ generations removed, and so on. Any person is $$$0$$$ generations removed from themselves.

Now let $$$A$$$ be $$$m$$$ generations removed from $$$C$$$ and $$$B$$$ be $$$n$$$ generations removed from $$$C$$$ where $$$m \leq n$$$. We can determine the relationship between $$$A$$$ and $$$B$$$ using the following rules:

  1. if $$$m = 0$$$ then $$$B$$$ is the child of $$$A$$$ if $$$n=1$$$ or the $$$\mbox{great}^{n-2}$$$ grandchild of $$$A$$$ if $$$n \gt 1$$$.
  2. if $$$0 \lt m = n$$$ then $$$A$$$ and $$$B$$$ are siblings if $$$n=1$$$ or $$$(n-1)$$$-th cousins if $$$n \gt 1$$$.
  3. if $$$0 \lt m \lt n$$$ then $$$A$$$ and $$$B$$$ are $$$(m-1)$$$-th cousins $$$(n-m)$$$ times removed.
Notice that if $$$m = 1$$$ and $$$n = 2$$$ we get the interestingly named "$$$0$$$th cousins, $$$1$$$ time removed" for the relationships we typically describe as "aunt/uncle" or "niece/nephew".

Figure 1 below shows some examples for two new people named (what else) $$$D$$$ and $$$E$$$.

# of generations removed
from common ancestor
$$$D$$$$$$E$$$Relationship
$$$0$$$$$$1$$$$$$E$$$ is the child of $$$D$$$
$$$4$$$$$$0$$$$$$D$$$ is the great great grandchild of $$$E$$$
$$$3$$$$$$3$$$$$$D$$$ and $$$E$$$ are $$$2$$$nd cousins
$$$9$$$$$$8$$$$$$D$$$ and $$$E$$$ are $$$7$$$th cousins, $$$1$$$ time removed
$$$1$$$$$$4$$$$$$D$$$ and $$$E$$$ are $$$0$$$th cousins, $$$3$$$ times removed
Some example relationships

The scientists have given you the description of a family tree and pairs of people in the tree and have asked you to determine the relationships between members of each pair.

Input

Input begins with a line containing two positive integers $$$t$$$ $$$p$$$ ($$$t \leq 100, p \leq 1\,000$$$) specifying the number of tree descriptions (described below) and the number of query pairs. Following these are $$$t$$$ lines, each with one tree description. Each tree description will be of the form $$$s_0$$$ $$$d$$$ $$$s_1$$$ $$$s_2 \ldots s_d$$$ indicating that person $$$s_0$$$ has $$$d$$$ children named $$$s_1$$$ through $$$s_d$$$. All names are unique and contain only alphabetic characters. Tree descriptions may be given in any order (i.e., the root of the entire tree may not necessarily be in the very first tree description). No name will appear more than once as $$$s_0$$$ in the tree descriptions. All the tree descriptions will combine to form exactly one tree, and the tree will have at least $$$2$$$ nodes and at most $$$100$$$ nodes.

Following this are $$$p$$$ lines of the form $$$s_i$$$ $$$s_j$$$ where $$$s_i \neq s_j$$$ and both names are guaranteed to be in the tree.

Output

Output the relationship for each pair of people, one per line, using the formats shown in Figure 1. Always output $$$s_i$$$'s name first for each pair except when $$$s_j$$$ is the direct descendant of $$$s_i$$$ (as in the first example in Figure 1). For the $$$n$$$-th ordinal number output $$$n$$$th except for $$$n=1,2,3,21,22,23,31,32,33,\ldots$$$ in which case you should output 1st, 2nd, 3rd, 21st, 22nd, 23rd, 31st, 32nd, 33rd, etc. Also be sure to use times for all times removed except one, where you should use the word time.

Examples
Input
4 5
Horatio 1 Irene
Chris 2 Gina Horatio
Alice 3 Dan Emily Frank
Bob 2 Alice Chris
Irene Bob
Dan Frank
Chris Emily
Alice Chris
Dan Irene
Output
Irene is the great grandchild of Bob
Dan and Frank are siblings
Chris and Emily are 0th cousins, 1 time removed
Alice and Chris are siblings
Dan and Irene are 1st cousins, 1 time removed
Input
4 6
A 4 B C D E
H 3 I J K
C 2 F G
D 1 H
G C
H A
F G
F H
F K
B K
Output
G is the child of C
H is the grandchild of A
F and G are siblings
F and H are 1st cousins
F and K are 1st cousins, 1 time removed
B and K are 0th cousins, 2 times removed

B. Kinky Word Searches
time limit per test
6 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

You're probably familiar with regular word searches, where you're presented with a grid of letters and a word to find. The word can be in a straight line horizontally, vertically, or diagonally (and perhaps backwards in any of those directions). For example, here is a grid of letters:

A word search grid

The word "JAVA" can be found going from the bottom right corner diagonally upwards.

In a kinky word search the path that spells out the word can have one or more "kinks" – places where the path changes direction. For example, in the given grid you can spell the word "PYTHON" with $$$3$$$ kinks (one each at the T, H and O):

A kinky spelling of "PYTHON"

Adding kinks allows letters to be reused – the word "CPLUSPLUS" can be found in the upper right corner of the grid (with $$$5$$$ kinks). However you cannot stay on a letter twice in a row, so you cannot spell the word "HASKELL" in this grid (though you can find at least $$$11$$$ more common programming languages). Your task is to see if the spelling of a word with a certain number of kinks is possible or not.

Input

Input begins with a line containing two positive integers $$$r$$$ and $$$c$$$ ($$$r, c \leq 10)$$$, the number of rows and columns in the grid. After this are $$$r$$$ rows of $$$c$$$ uppercase characters. Letters are separated by a space. After the grid are two lines: The first line is an integer $$$k$$$, the number of kinks. The second line contains an uppercase word to look for, with maximum length $$$100$$$.

Output

Output either the word Yes if it is possible to spell the given word with exactly $$$k$$$ kinks on the grid provided, or No if it is not.

Examples
Input
5 5
L M E L C
C A K U P
D O V S Y
R N L A T
P G O H J
0
JAVA
Output
YES
Input
5 5
L M E L C
C A K U P
D O V S Y
R N L A T
P G O H J
3
PYTHON
Output
YES
Input
5 5
L M E L C
C A K U P
D O V S Y
R N L A T
P G O H J
4
PYTHON
Output
NO

C. Math Trade
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

Suppose a group of people have objects they want to trade, and objects they want to get in return:

NameHasWants
SallyClockDoll
SteveDollPainting
CarlosPaintingClock
MariaCandlestickVase

Notice how none of the people listed can pair off and trade with each other. However, if Sally, Steve, and Carlos all got together, Sally could trade her clock to Steve for the doll she wants, and Steve can then trade that clock to Carlos for the painting Steve wants.

This creation of a chain of individual trades that gets a large number of people the objects they want is called a math trade. Ideally everyone is involved in the math trade but that is not always possible (sorry Maria). The object therefore is to create a single chain of the longest length. Determining the longest math trade gets complicated if the participants have multiple items that they want to trade or obtain. Luckily for you, we are only worried about the situation where each person has and wants exactly one item, and no item is owned by or desired by more than one person.

Input

Input begins with a line containing a positive integer $$$n\,(n \leq 100)$$$, the number of people interested in trading. After this are $$$n$$$ lines, each with three strings separated by spaces. The first string will be the name of the trader. The second string will be the object the trader has. The third string will be the object the trader wants. All trader names will be unique, and no object will be wanted by more than one person and owned by more than one person.

Output

Output the length of the longest math trade. If no trading is possible, output the phrase "No trades possible"

Examples
Input
4
Sally Clock Doll
Steve Doll Painting
Carlos Painting Clock
Maria Candlestick Vase
Output
3
Input
4
Abby Bottlecap Card
Bob Card Spoon
Chris Spoon Chair
Dan Pencil Pen
Output
No trades possible

D. Oreperations Research
time limit per test
7 s
memory limit per test
1024 megabytes
input
standard input
output
standard output

You run a massive mining facility that extracts ore from a mine and loads it onto long trains for shipment to factories around the nation. A train consists of $$$n$$$ cars, where car $$$i$$$ has capacity $$$c_i$$$, indicating how many tons of ore it can carry. Ore is dropped into the train cars at an overhead loading station from two separate queues of mine carts that run on either side the train. As with the train cars, mine carts hold varying loads of ore. Queue $$$A$$$ has $$$r$$$ carts, and cart $$$A_i$$$ carries a load of $$$a_i$$$. Similarly, queue $$$B$$$ has $$$s$$$ carts, and cart $$$B_i$$$ carries a load of $$$b_i$$$. Initially train car $$$1$$$ is at the loading station, and carts $$$A_1$$$ and $$$B_1$$$ are available to dump ore into it. The train car currently in the station can be given the load from the front cart in the $$$A$$$ queue, the front cart in the $$$B$$$ queue, or from both. If a cart doesn't dump its ore, it remains at the loading station; if it does dump its ore, it cycles back into the mine, loads up on ore, and rejoins the end of its queue. Meanwhile, the next cart in the queue moves into place and is available to dump ore. Carts may not drop partial loads of ore and may not leave the loading station until they've emptied. Similarly train cars may not be over-filled and may not leave the loading station until they are filled to capacity. As soon as a train car is filled to capacity it leaves the loading station and the next train car pulls in. Your task is to determine whether given sequences of mine carts can be used to fill a given sequence of train cars to their capacity.

Figure 1 shows an example of the process. Here queue $$$A$$$ has three mine carts carrying loads $$$4$$$, $$$3$$$ and $$$2$$$, queue $$$B$$$ has four mine carts carrying loads $$$1$$$, $$$5$$$, $$$2$$$ and $$$2$$$, and the train has three cars with capacities $$$8$$$, $$$5$$$ and $$$4$$$. The starting setup is shown in the leftmost image. After (say) the first car in queue $$$A$$$ dumps its load into the first train car it goes back to the mine and (eventually) returns to the end of the line in queue $$$A$$$. This situation is shown in the second image, where the first train car still has capacity $$$4$$$ to be filled. This can be accomplished by dumping ore from the front car of both queues $$$A$$$ and $$$B$$$. Once filled, the first train car moves out of the loading station leaving an alignment of cars and carts shown in the third image. Here, the only way to fill the train car is for the front car of queue $$$B$$$ to dump its load. This leads to the final image. Here the last train car can be filled either by the front cars of both queues or the first two cars of queue $$$B$$$. Note that if the third train car had capacity $$$3$$$ it could not be filled to full capacity.

Sample Input $$$1$$$
Input

Input begins with a line containing three positive integers $$$r$$$ $$$s$$$ $$$n$$$ ($$$r,s \leq 50, n \leq 100)$$$ indicating the number of carts in queues $$$A$$$ and $$$B$$$ and the number of train cars, respectively. This is followed by three lines containing the values $$$a_1, a_2, \ldots, a_r$$$, $$$b_1, b_2, \ldots, b_s$$$, and $$$c_1, c_2, \ldots, c_n$$$, the capacities of the $$$A$$$ carts, the $$$B$$$ carts and the train cars, respectively. The maximum capacity of any cart is $$$200$$$ and the maximum capacity of any train car is $$$2\,000\,000$$$.

Output

Output Yes or No indicating whether all of the train cars can be filled to capacity.

Examples
Input
3 4 3
4 3 2
1 5 2 2
8 5 4
Output
yes
Input
3 4 3
4 3 2
1 5 2 2
8 5 3
Output
no

E. Over the Hill, Part 1
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

Hill encryption (devised by mathematician Lester S. Hill in 1929) is a technique that makes use of matrices and modular arithmetic. It is ideally used with an alphabet that has a prime number of characters, so we'll use the $$$37$$$ character alphabet A, B, $$$\ldots$$$, Z, 0, 1, $$$\ldots$$$, 9, and the space character. The steps involved are the following:

  1. Replace each character in the initial text (the plaintext) with the substitution A$$$\rightarrow 0$$$, B$$$\rightarrow 1$$$, $$$\ldots$$$, (space)$$$ \rightarrow 36$$$. If the plaintext is ATTACK AT DAWN this becomes
    $$$0\ 19\ 19\ 0\ 2\ 10\ 36\ 0\ 19\ 36\ 3\ 0\ 22\ 13$$$
  2. Group these number into three-component vectors, padding with spaces at the end if necessary. After this step we have
  3. Multiply each of these vectors by a predetermined $$$3 \times 3$$$ encryption matrix using modulo $$$37$$$ arithmetic. If the encryption matrix is

    then the first vector is transformed as follows:

  4. After multiplying all the vectors by the encryption matrix, convert the resulting values back to the $$$37$$$-character alphabet and concatenate the results to obtain the encrypted ciphertext. In our example the ciphertext is FPLSFA4SUK2W9K3.

This method can be generalized to work with any $$$n \times n$$$ encryption matrix in which case the initial plaintext is broken up into vectors of length $$$n$$$. For this problem you will be given an encryption matrix and a plaintext and must compute the corresponding ciphertext.

Input

Input begins with a line containing a positive integer $$$n \leq 10$$$ indicating the size of the matrix and the vectors to use in the encryption. After this are $$$n$$$ lines each containing $$$n$$$ non-negative integers specifying the encryption matrix. After this is a single line containing the plaintext consisting only of characters in the $$$37$$$-character alphabet specified above.

Output

Output the corresponding ciphertext on a single line.

Examples
Input
3
30 1 9
4 23 7
5 9 13
ATTACK AT DAWN
Output
FPLSFA4SUK2W9K3
Input
6
26 11 23 14 13 16
6 7 32 4 29 29
26 19 30 10 30 11
6 28 23 5 24 23
6 24 1 27 24 20
13 9 32 18 20 18
MY HOVERCRAFT IS FULL OF EELS
Output
W4QVBO0NJG5 Y76H5A6XHR11BV670Z

F. Over the Hill, Part 2
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

Bob Roberts is part of a crack espionage team working for the CIA (Chocolate Institute of Alabama) and he is working on decrypting the encoded messages of their arch rivals at the NSA (Nougat Society of Arkansas). Fortunately, the NSA's espionage staff is not nearly as crack as Bob's as they are using the Hill encryption scheme (described in the previous problem) which is susceptible to a known-plaintext attack. Bob has intercepted a plaintext/ciphertext pair and has knowledge of the size of the encryption matrix used by his not-so-sweet enemies. Given these Bob knows that there is a way to determine the encryption matrix, but no one on his staff is exactly sure how (hmmm $$$\ldots$$$ not quite as crack as they thought). Bob's come to you to solve this problem for them. One complication is that there might not be enough data to uniquely determine the NSA's encryption matrix, and the data they intercepted might have been corrupted leading to no solution to the problem.

Input

Input begins with a line containing a positive integer $$$n \leq 10$$$ indicating the size of the matrix and the vectors to use in the encryption. After this are two lines: the first of these contains the plaintext and the second the ciphertext. Both of these lines will consist only of characters in the set A, $$$\ldots$$$, Z,0, $$$\ldots$$$, 9 and the space character. The lengths of both strings are identical and are multiples of $$$n$$$. Both of these strings may include trailing blanks.

Output

Output one of three possible answers. If the input does not admit any possible encryption matrix output No solution. Otherwise if the input does not uniquely determine the encryption matrix output Too many solutions. Otherwise output the encryption matrix, one row per line with a single space between values on a line.

Examples
Input
3
ATTACK AT DAWN
FPLSFA4SUK2W9K3
Output
30 1 9 
4 23 7 
5 9 13 
Input
3
ATTACK
FPLSFA
Output
Too many solutions
Input
3
ATTACK AT DAWN
EPLSFA4SUK2W9K3
Output
No solution

G. A Rank Problem
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

Coach is fed up with sports rankings – he thinks those who make up these bogus orderings are just nuts. In Coach's opinion changes in rankings should be evidence-based only. For example, suppose the $$$4$$$th place team plays the $$$1$$$st place team and loses. Why should the rankings be altered? The "worse" team lost to the "better" team, so nothing should change in the rankings. Put another way, there's no evidence that the ordering should change so why change it? The only time you change something is if, say, the $$$4$$$th place team beats the $$$1$$$st place team. NOW you have evidence that the rankings should change! Specifically, the $$$1$$$st place team should be put directly below the $$$4$$$th place team (we now have evidence that backs this up) and the teams in $$$2$$$nd through $$$4$$$th place should each move up one. The result is that the former $$$1$$$st place team is now in $$$4$$$th, one position below the team that beat it, the former $$$4$$$th place team now in $$$3$$$rd. Note that the relative positions of the teams now in $$$1$$$st to $$$3$$$rd place do not change – there was no evidence that they should.

To generalize this process, assume the team in position $$$n$$$ beats the team in position $$$m$$$. If $$$n \lt m$$$ then there should be no change in the rankings; if $$$n \gt m$$$ then all teams in positions $$$m+1, m+2, \ldots, n$$$ should move up one position and the former team in position $$$m$$$ should be moved to position $$$n$$$.

For example, assume there are $$$5$$$ teams initially ranked in the order T$$$1$$$ (best), T$$$2$$$, T$$$3$$$, T$$$4$$$, T$$$5$$$ (worst). Suppose T$$$4$$$ beats T$$$1$$$. Then as described above the new rankings should become T$$$2$$$, T$$$3$$$, T$$$4$$$, T$$$1$$$, T$$$5$$$. Now in the next game played let's say T$$$3$$$ beats T$$$1$$$. After this the rankings should not change – the better ranked team beat the worse ranked team. If in the next game T$$$5$$$ beats T$$$3$$$ the new rankings would be T$$$2$$$, T$$$4$$$, T$$$1$$$, T$$$5$$$, T$$$3$$$, and so on.

Coach was all set to write a program to implement this scheme but then he heard about ties in the English Premier League. The last we saw him he was standing motionless, staring out of his window. We guess it's up to you to write the program.

Input

Input begins with a line containing two positive integers $$$n$$$ $$$m$$$ ($$$n, m \leq 100$$$) indicating the number of teams and the number of games played. Team names are $$$\mbox{T}1, \mbox{T}2, \ldots, \mbox{T}n$$$ and initially each team $$$\mbox{T}i$$$ is in position $$$i$$$ in the rankings (i.e., team $$$\mbox{T}1$$$ is in $$$1$$$st place and team $$$\mbox{T}n$$$ is in last place). Following the first line are $$$m$$$ lines detailing a set of games in chronological order. Each of these lines has the form $$$\mbox{T}i$$$ $$$\mbox{T}j$$$ ($$$1 \leq i,j \leq n, i \neq j$$$) indicating that team $$$\mbox{T}i$$$ beat team $$$\mbox{T}j$$$.

Output

Output a single line listing the final ranking of the teams. Separate team names with single spaces.

Examples
Input
5 3
T4 T1
T3 T1
T5 T3
Output
T2 T4 T1 T5 T3
Input
8 4
T4 T1
T1 T2
T2 T3
T3 T4
Output
T1 T2 T3 T4 T5 T6 T7 T8

H. Restroom Monitor
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

Irma P. Freely (yes, we've hit a new low) is in charge of the bank of restrooms at the Rest Pit truck stop. Every so often a tour bus stops by and a load of passengers gets off to use the restroom. Irma has a set of $$$n$$$ single-stall restrooms she can allocate to people. Everyone takes the same amount of time to use the facilities but may have different "deadlines" for when they must be finished. Being good at her job, Irma can look at the people in line and estimate with complete accuracy what their deadlines are.

Unfortunately, owing to shortages caused by the COVID pandemic, there is only one roll of toilet paper. Not everyone needs toilet paper, but only one person can be in a stall with it at a time. Irma needs to figure out whether she can schedule everyone so that they can all make use of her facilities before their deadlines. Sounds like a lot of paperwork $$$\ldots$$$ can you help her?

Input

Input begins with a line containing two integers $$$s$$$ and $$$n$$$, where $$$1 \leq s \leq 50\,000$$$ is the number of stalls and $$$1 \leq n \leq 100\,000$$$ is the number of people who need to use a restroom. Following this are $$$n$$$ lines, one for each person. Each line contains an integer $$$d$$$, $$$1 \leq d \leq 10^9$$$ (the deadline) and a character $$$t$$$. If $$$t$$$ is y, then this person needs the toilet paper; if $$$t$$$ is n, they don't. Assume each user requires one unit of time and that deadlines are specified in terms of the same unit.

Output

If it is possible to allocate everyone to stalls to meet their deadlines, display Yes. Otherwise, display No.

Examples
Input
3 7
2 y
2 n
5 y
1 n
5 n
2 y
1 n
Output
yes
Input
2 7
2 y
2 n
5 y
1 n
5 n
2 y
1 n
Output
no

I. Scholar's Lawn
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

Famously at Cambridge, and often copied at other schools, is the tradition of the "Scholar's Lawn" – an area of grass where Fellows of the school, or other distinguished entities, can walk, but regular students cannot.

So, if a student spies a Fellow walking across campus, and wishes to ambush ..., er, meet up with them, the student is restricted to walking along a set of narrow paved walkways laid out in various places within the grassy areas, hoping to reach the Fellow's path at the same time or before the Fellow arrives. At the end of the Fellow's path is the Sacred Grove of Academe, off-limits to students, so if the Fellow reaches it before the student, the student is out of luck.

For instance, Figure 1 shows an area of lawn together with the fixed set of paved walkways (solid lines) and the path taken by a Fellow of the university (dotted line); $$$F$$$ and $$$S$$$ denote the initial positions of the Fellow and student, respectively. If both travel at the same speed (say, one meter per second), then after $$$17.67767$$$ seconds the Fellow will find the student waiting to have a chat at location $$$(22.5,12.5)$$$ (marked by the small open circle "$$$\circ$$$").

Sample Input 1
Input

Input begins with an integer $$$n$$$, $$$1 \le n \le 500$$$, the number of straight-line walkways. There will then follow $$$n$$$ lines, each with $$$4$$$ integers, denoting the $$$(x,y)$$$ coordinates of the endpoints of each walkway. After that is a line containing three real values $$$x_s$$$, $$$y_s$$$, $$$v_s$$$, where $$$(x_s,y_s)$$$ is the position of the student and $$$v_s$$$, $$$0 \lt v_s \leq 1\,000$$$, is the student's walking speed. The point $$$(x_s,y_s)$$$ is guaranteed to lie on one of the $$$n$$$ paved walkways. The final line contains $$$5$$$ numbers. The first $$$4$$$ numbers are real numbers $$$x_{1f}$$$, $$$y_{1f}$$$, $$$x_{2f}$$$, $$$y_{2f}$$$, $$$-10\,000 \le x_{1f}, y_{1f},x_{2f},y_{2f} \le 10\,000$$$, giving the starting position $$$(x_{1f}, y_{1f})$$$ of the Fellow and the ending position $$$(x_{2f}, y_{2f})$$$ of the Fellow (the last point where the student can reach the Fellow). The final number is a real value $$$v_f$$$, $$$0 \lt v_f \leq 1\,000$$$, giving the Fellow's walking speed. All real-valued inputs will have at most four digits after the decimal point.

The Fellow always walks in a straight line. The student can walk only along walkways, which are assumed to have zero width. If a walkway intersects with another walkway or the Fellow's path, it will do so at a single point. Collinear walkways never intersect one another; similarly, if the Fellow's path and a walkway are collinear, they will not intersect.

Output

Output the earliest time $$$t$$$ when the student's position and the Fellow's position can coincide at an intersection of a walkway and the Fellow's path. If this is impossible, output -1. Numeric answers should be accurate to within an absolute or relative error of $$$10^{-6}$$$.

Side note: in the original problem, you were supposed to output Impossible instead of -1; but the latter format makes it easier to upload this problem to Codeforces.

Examples
Input
7
5 5 35 5
35 0 15 20
30 0 30 10
30 10 35 10
35 10 35 15
35 15 30 15
30 15 30 30
30.0 0.0 1.0
10 0 40 30 1.0
Output
17.67766953
Input
7
5 5 35 5
35 0 15 20
30 0 30 10
30 10 35 10
35 10 35 15
35 15 30 15
30 15 30 30
30.0 0.0 1.0
10 0 40 30 1.2
Output
-1

J. Simply Sudoku
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

Sudoku puzzles come in all different shapes and difficulty levels. Traditionally a Sudoku puzzle is a $$$9\times9$$$ grid. Initially, some of the cells are filled in with numbers and some are empty. The goal is to fill in each cell with a number in the range $$$1$$$ – $$$9$$$ subject to the following restrictions:

  • Each digit $$$1$$$ – $$$9$$$ must appear once in each row
  • Each digit $$$1$$$ – $$$9$$$ must appear once in each column
  • Each digit $$$1$$$ – $$$9$$$ must appear once in each $$$3\times3$$$ sub-grid

The difficulty of a Sudoku puzzle can vary widely. The easiest puzzles can be solved with the following two simple techniques:

  • Single Value Rule: search for squares which only have one possible value that can be put there.
  • Unique Location Rule: within any row, column or sub-grid search for a value that can only be placed in one of the nine locations.
Consider the partially solved Sudoku puzzle shown in Figure 1. The Single Value Rule applies to grid square A$$$7$$$ where $$$8$$$ is the only value that can be placed there. The Unique Location Rule can be used to put a $$$5$$$ in square B$$$3$$$ as it is the only location in row $$$3$$$ where a $$$5$$$ can be placed.
Sample Input $$$1$$$

The easiest Sudoku puzzles can be solved with only these two rules; harder puzzles use techniques like swordfish, x-wings and BUGs.

For this problem you will be given a Sudoku puzzle and must determine if it is an easy puzzle, i.e., whether it can be solved by just using the Single Value and Unique Location rules.

Input

Input consists of a single Sudoku puzzle given over nine lines. Each line contains $$$9$$$ values in the range $$$0$$$ to $$$9$$$, where a $$$0$$$ indicates a blank in the puzzle.

Output

Output the word Easy followed by the solved Sudoku puzzle if it is an easy puzzle. The puzzle should be printed on nine lines with a single space separating values on a line. If the puzzle is not easy output Not easy followed by as much of the Sudoku puzzle as can be solved using the two rules described above. Use the same format for the partial solution as for the complete solution using a '.' instead of a digit for a unfilled square.

Examples
Input
2 6 0 5 1 0 3 0 0
3 0 0 0 6 0 0 0 2
0 1 5 0 7 3 9 0 4
0 0 9 0 0 0 5 0 0
0 0 2 6 0 1 4 0 0
0 0 6 0 0 0 7 0 0
6 0 1 9 4 0 2 3 0
9 0 0 0 2 0 0 0 5
0 0 8 0 3 5 0 4 9
Output
Easy
2 6 4 5 1 9 3 7 8 
3 9 7 8 6 4 1 5 2 
8 1 5 2 7 3 9 6 4 
1 3 9 4 8 7 5 2 6 
5 7 2 6 9 1 4 8 3 
4 8 6 3 5 2 7 9 1 
6 5 1 9 4 8 2 3 7 
9 4 3 7 2 6 8 1 5 
7 2 8 1 3 5 6 4 9 
Input
0 0 0 0 0 0 7 0 1
0 0 0 0 0 1 2 3 5
0 0 1 8 0 0 0 0 6
0 0 0 0 2 5 0 9 3
9 0 0 0 0 0 0 0 2
3 1 0 6 7 0 0 0 0
2 0 0 0 0 3 8 0 0
1 3 8 9 0 0 0 0 0
4 0 6 0 0 0 0 0 0
Output
Not easy
. . 3 . . . 7 8 1 
. . . . . 1 2 3 5 
. . 1 8 3 . 9 4 6 
. . . . 2 5 . 9 3 
9 . . 3 . . . 7 2 
3 1 2 6 7 9 4 5 8 
2 . . . . 3 8 . . 
1 3 8 9 . . 5 . . 
4 . 6 . . . 3 . . 

K. Weighty Tomes
time limit per test
5 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

The Computer Science Library on campus needs to be temporarily closed for renovations and you have been put in charge of the storage of all the library's books. After getting over the shock of being selected as well as the shock that the campus actually had a CS library, you get down to work. The books have already been packed in identical boxes which all have the same weight. You want to stack these boxes on wooden pallets in case the storage room gets flooded, but you have a small problem: you don't know how many boxes you can stack before the pallets collapse under the weight. We'll call the maximum number of boxes that can rest on a pallet the box limit.

You could methodically place one box on a pallet, then a second, a third, etc., until the pallet breaks but that seems very time consuming (and leads to a very boring contest problem). But if you have one or more pallets to experiment with you might be able to determine the box limit quicker. For example, suppose because of the size of the boxes and the height of the storage room ceiling the maximum number of boxes in any stack is $$$3$$$. With just one pallet you could first try one box. If the pallet collapses, well, you need to go out and get some stronger pallets. If the pallet holds then you could try a second box. If the pallet collapses now you know the box limit is $$$1$$$; otherwise, you try a third box and that will let you know whether the box limit is $$$2$$$ (if the pallet collapses) or $$$3$$$ (if the pallet doesn't collapse). This approach requires at most three different experiments. However, if you had two pallets you could determine the box limit with at most only two experiments: first you try two boxes on the first pallet; if it holds, you try a third which will let you know whether the box limit is $$$2$$$ or $$$3$$$. If the first pallet collapses in the first experiment, you haul out the second pallet and place a single box on it. The result of that experiment tells you if the box limit is $$$1$$$ or $$$0$$$.

You are not exactly sure about the height of the storage room (which dictates the maximum possible boxes that could be stacked) or how many pallets you have at your disposal to experiment with. What you would like to know is when given this information, what is the minimum worst-case number of experiments you need to run given an optimal strategy. Too bad you didn't know about the CS Library earlier – maybe there was something in one of the books that would help you now.

Input

Input consists of a single line containing two positive integers $$$n$$$ and $$$m$$$ ($$$n \leq 5\,000, m \leq 20$$$), where $$$n$$$ indicates the maximum number of boxes that can be stacked (regardless of whether a pallet would be collapsed by them or not) and $$$m$$$ is the number of available pallets to experiment with.

Output

Output the minimum worst-case number of experiments that the optimal strategy would require followed by the number of boxes to use in the first experiment. If there is a range of boxes that can be used in the first experiment display the minimum and maximum values of this range separated by a hyphen; if there is only one such number simply output that number.

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

L. Workers of the World Unite! Just Not Too Close.
time limit per test
10 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

You are in charge of a set of workers working on a project so top secret we can't even think of a name for it. They are each housed separately in a set of apartments shown on the left in figure 1 and every morning they each leave at the same time and proceed to one of the workstations shown on the right. In order to get from their homes to the workstations they must pass through a security gate shown in the middle. Each gate has two different corridors that can be used, labeled A and B. As can be seen from the figure the A corridors in each gate are always to the north of the B corridors.

Figure 1: Layout of apartments, gates and workstations.

Getting the workers to the workstations sounds simple, but with the onset of COVID-$$$19$$$ a problem has arisen. First, because of social distancing no two workers can use the same gate. Second, because of the layout of the gates, if one worker uses an A corridor, the person using the gate to the north of them cannot use the B corridor – it's too close. The analogous thing occurs if a worker uses a B corridor – the worker using the gate to the south of them can't use the A corridor.

You are in charge of assigning workers to the stations, one worker at each station. It doesn't matter which worker is assigned to which workstation but you would like to minimize the total distance all the workers travel while adhering to the social distancing requirements described above. Due to the strange layout of the entrances and exits to the gates there can sometimes be large differences in distances when using the A corridor versus the B corridor for a gate, which complicates the problem. Given all the relative distances, determine an assignment of workers to workstations that minimizes the total distance everyone travels.

Input

Input begins with a line containing one positive integer $$$n \leq 50$$$, specifying the number of workers, gates and workstations, each numbered $$$1$$$ to $$$n$$$. Following this are $$$n$$$ lines each containing $$$2n$$$ positive integers. The $$$i$$$-th of these lines gives the distance from worker $$$i$$$ to the entrances of the $$$n$$$ gates; the first two values are the distances to corridors A and B for gate $$$1$$$, the second two values are the distances to corridors A and B for gate $$$2$$$, and so on. After this are $$$n$$$ more lines each containing $$$2n$$$ positive integers. The $$$j$$$-th of these lines gives the distance from the workstation $$$j$$$ to the exits of the $$$n$$$ gates in an analogous fashion. All distances are positive and $$$ \leq 1\; 000$$$.

Output

On the first line of output print the minimum total distance traveled by the workers that can be achieved. Follow this with $$$n$$$ lines showing the assignment for each worker. The $$$i$$$-th of these lines will have the form $$$i$$$ $$$g_i$$$ $$$w_i$$$ indicating that worker $$$i$$$ uses gate $$$g_i$$$ to get to workstation $$$w_i$$$. Use the format shown in the sample output. If there are several optimal assignments, any will be accepted

Example
Input
3
75 64 25 9 32 1
72 51 49 46 64 53
13 37 75 35 62 50
90 62 72 6 30 35
39 89 17 62 47 65
94 79 27 93 21 58
Output
163
1 3B 3
2 2B 1
3 1A 2