After unfolding the mysteries of the palindromic decorations in the Thai ruins, the famous researcher Renzo "the fearless" Morales is searching for a Sioux artifact. Some people believe that such artifact got lost a long time ago during the struggles between the Sioux and the north-american settlers.
Renzo believes that this artifact was hidden from the north-americans, and after a long search, he found clues to its location. The clues are two old maps of the region that today is known as Rapid City. Both maps have rectangular shape and show exactly the same region, but one is on a larger scale than the other. Renzo noticed that the corners of the smaller map are numbered from 1 to 4, and in the interior of the larger map exist four points numbered from 1 to 4 forming a rectangle of the exact same size of the smaller map.
Being a proficient problem solver, the famous researcher came rapidly to the conclusion that the smaller map has to be put on top of the larger map, in such a way that the numbered points coincide. Considering that both maps are in the Cartesian plane with the origin at the lower left corner of the larger map, the place where the artifact is hidden must correspond to a point in the plane that represents the same location in both maps.
To help Renzo find this precious historic artifact, write a program that finds one of these points.
The first line contains two integers H and W (10 ≤ H, W ≤ 1000), that represent the height and the width of the map, respectively. The following lines contain four pairs of values xi, yi (0 < xi < W, 0 < yi < H), one pair per line, indicating the coordinates of the smaller map, starting from its lower left corner (regarding the original orientation), followed by its lower right corner, upper right and finally the upper left corner. The coordinates are given with exactly 8 decimal places. Its guaranteed that the ratio between the scales of the smaller and larger map is between 0.01 and 0.99, inclusive.
Print a single line containing two numbers xp, yp: the coordinates of the point corresponding to the location of the artifact in both maps. Absolute or relative errors up to 10 - 4 will be tolerated. If there are multiple solutions, print any of them. It is guaranteed that at least one exists.
10 20
8.00000000 4.00000000
12.00000000 4.00000000
12.00000000 6.00000000
8.00000000 6.00000000
10.000000 5.000000
10 10
5.00000000 4.50000000
2.50000000 4.50000000
2.50000000 7.00000000
5.00000000 7.00000000
4.000000 6.000000
All teams participating on ICPC World Finals 2017, in Rapid City, were invited to make a visit to Custer State Park and relax a bit before the contest. Custer State Park is home to abundant wildlife, including bighorn sheep, antelope, deer, elk, coyote, and many other animals, including buffaloes.
As you know, buffaloes like to walk in a line. Many families of buffaloes walk in the same line, but they are not always in adjacent positions. However, buffaloes of the same family always stay in the same relative order in the line; an older buffalo always stays in front of a younger buffalo of his family, to protect him in case of any danger. Notice that, since there can be many different families in the line, the line isn't necessarily ordered by age.
Let b = (b1, ..., bN) be a line of buffaloes, where bi is the age of the ith buffalo. You can assume no two buffaloes in a line have the same age. We say a sequence of indexes (i1, ..., iL) is a possible family of size L if 1 ≤ i1 < ... < iL ≤ N and bi1 > bi2 > ... > biL, that is, it is not impossible that the buffaloes with these indices are in the same family. The family size of a line is the size of the largest possible family in that line.
As you and your team is taking a tour through the park, you sight a line of N buffaloes, and the instructor that is escorting you proposes the following puzzle: "In how many ways can you reorder the buffaloes in the line such that the family size of the line is not 3 or 4?".
Stefano "the swimmer" Spinnato, your coach, tells you "I can't distinguish the easy problems from the hard ones" and writes the solution in a piece of paper. You feel challenged and want to solve the puzzle too.
A single integer N, the number of buffaloes in the line.
Limits
- 1 ≤ N ≤ 60
Print one integer, the answer to the problem. Since this number can be very large, print it modulo 109 + 7.
1
1
2
2
3
5
4
14
In the third case, assuming the 3 buffaloes age 1, 2 and 3, the possible lines are (1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2) and (3, 2, 1). Of those, only line (3, 2, 1) has family size 3, so the answer is 5.
Cahokia is the area of an ancient civilization located in the state of Illinois. This place importance comes from the fact that it helps understand the history of North America. Cahokia was composed by 120 mounds, 80 of them still remain nowadays. One of these mounds is called Monks Mound, considered the biggest natural monument in all North America.
Recently, a group of archaeologist of the organization Extraordinary Mystery Investigators (IME, in their language) have discovered secret passages in the underground surroundings of Monks Mound. Because of the importance of this discovery, IME has called one of its famous members, Marcio "the indispensable" Himura, for help. After diving in Thai seas, Marcio is back in action and want to unfold the mysteries of Cahokia. The members of IME want to reach the deepest part of Monk Mound, but to do so, they have to traverse a special room.
This room can be represented by a 2D grid with dimensions H × W meters. The particularity of this room is that the instant somebody enters the room the east and west walls begin to move towards each other until they collide. Marcio suspects that this was made to keep safely treasures from intruders. Each wall is represented by a sequence of H integers a1, a2, ..., aH, where ai is the width (in meters) of the wall at row i. Marcio knows that each wall moves with speed of 1 m / s. The following figure depicts (a) the initial configuration of the room given in the first sample test case, and (b) the collision of the walls after one second.
Marcio is interested in knowing, given an initial configuration of the walls, in how much time the walls collide after someone enter the room. This information is crucial for Marcio to determine an strategy to go through the room. He acknowledges your potential, so he ask for your help to solve this problem.
In the first line we give two space-separated integers, H (2 ≤ H ≤ 105) and W (4 ≤ W ≤ 105). In the second line, there are H space-separated integers representing the east wall. In the third line, there are H space separated-integers representing the west wall. It is ensured that the walls don't overlap at any row.
One number representing in how much time the two walls hit each other. Error of 10 - 9 is tolerated.
4 6
1 1 1 3
1 2 1 1
1
4 100
10 10 20 30
15 35 20 10
27.5
In Rapid City are located the main producers of the Black Hills gold jewelry, a very popular product among tourists. The main characteristics of these jewels are the designs of leaves and grape clusters that are made with gold alloys in yellow, green and pink tones.
Planning a trip to Rapid City in 2017, Nay Suames decides that he wants to buy these famous jewels, but he doesn't have much money to spend. Searching for the lowest prices, he found a jewelry store that will have a sale in May, the same month he will travel to that city. Lucky guy!
The jewelry store intends to sell the jewels that were produced with small defects, in general, only perceivable by experts. The jewels are separated in N categories of defects. Even if the defect is imperceptible, the jewelry store can't sell the jewel at full price, so it gives a discount proportional to the defect.
Knowing the high demand for these jewels, the jewelry store created a system aiming to be fair and, at the same time, to prevent everybody from buying only the cheapest jewels. The clients have to make a queue and will be served one at a time. When their time comes, the client must choose two jewels from different categories. Furthermore, they can't choose the same combination of categories that was previously chosen by another client.
Nay asks for your help to find the minimum amount of money he needs, being the K-th client in the queue, so that it is guaranteed that he can buy two different jewels.
The first line contains two integers, N and K, 
, representing the number of categories and the position of Nay in the queue, respectively. The next line contains N integers a1, a2, ..., aN (0 ≤ ai ≤ 109), corresponding to the prices of each category.
Print a single integer, the minimum amount of money to guarantee that Nay can buy the jewels.
4 3
2 4 5 2
6
6 9
1 2 3 4 5 6
7
Donald Trump is a terrible person. It is said he won't sleep at night until he has unfairly offended someone. Donald knows N horrible words and M kind words. For his next speech, he wants to compress the horrible words together to create the most offensive word of all time, while not saying any kind words.
We say a word s contains a word t if it has the word t as a contiguous substring. Trump wants to find the smallest word that contais all N horrible words he knows, and none of the M kind words. Determine one such word.
On the first two integers N and M. In each of the next N lines, a horrible word. In each of the next M lines, a kind word.
Limits
- 1 ≤ N + M ≤ 15
- N ≥ 1, M ≥ 0
- Each word is a string with at least 1 and at most 300 characters
- All strings consist of lowercase characters from a to j
- The sum of lengths of all strings will not exceed 300
If there is no such word, print only "-" in a single line. Otherwise, print a single string, an answer to the problem. It can only contain lowercase characters from a to j. If there are multiple possible strings, print any of them.
3 0
hejja
gecab
jag
hejjagecab
3 1
ababab
bababb
abbb
babbb
abbbabababb
Since the 2017 world finals will be in Rapid City, South Dakota, the MaratonIME's coach decides to visit the city to know the contest location.
The city is preparing to receive the best computer programmers in the world. To ensure the safety of the event, metal detectors are being installed at the entrance of the convention center where the contest will be held. To avoid long waits in the line, the security officers were instructed to send every person that activates the metal detector to the end of the line.
The coach noticed that one of the metal detectors is defective and it is always activated alternately. This means that the first person does not activate it and the next person does. The third person does not activate it and the next person does, and so on.
Given that there are N people in the line, the coach, that is the i-th in the line, wants to know when he will be able to go through the metal detector without activating it.
The input starts with an integer T, the number of test cases.
Each test case consists of two integers, N and i, corresponding to the number of people in the line and the position of the coach in the line, respectively.
Limits
- 1 ≤ T ≤ 103
- 1 ≤ N ≤ 109
- 1 ≤ i ≤ N
For each test case, print a line with one integer j meaning that the coach will be the j-th person to go through the metal detector without activating it.
2
5 1
6 2
1
4
In 1776, a Committee of Five was chosen to draft the Declaration of Independence of the USA, among them John Adams, Thomas Jefferson and Benjamin Franklin. From June 11 to July 5 they worked tirelessly to write such important document.
It wasn't written correctly in the first attempt, and many many changes had to be made. Since in that time there weren't such great and time-saving utilities like git and version control, they had a very simple but time consuming way to keep old versions of the document.
Suppose Thomas Jefferson wanted to add a line to a version i of the document. Instead of changing the actual document in version i, he would use a letter copying press, a machine just invented by James Watt just around that time, to copy the version i to a new sheet of paper, and then would modify this new sheet of paper. This paper would then be stored so it could be copied later. As each modification creates a new version of the document, the kth modification will create the version k of the document. You can assume the version 0 of the document is an empty piece of paper.
As everything was written in ink and the committee doesn't like to contradict itself, each modification could only add some lines to the end of the document, or erase some lines from the beginning of the document.
Your task is to simulate the making of the Declaration of Independence. Each sentence is represented as an integer number. You need to process the following queries:
- E v x — Copy the document with version v, then add sentence x to the end of the copied document
- D v — Copy the document with version v, then remove the first sentence of the copied document
Queries are numbered from one. The document with version 0 is empty.
In the first line an integer Q, the number of queries. Each of the next Q lines has a query, in the format given in the statement.
Limits
- 1 ≤ Q ≤ 105
- In the ith query it is guaranteed that 0 ≤ v < i
- For each query of type E, x will fit in a 32-bit signed integer
- For each query of type D, it is guaranteed the document will not be empty during the removal of the first sentence
For each query of type D, print the sentence removed.
8
E 0 10
E 0 -10
D 2
D 1
E 2 5
D 5
D 6
D 2
-10
10
-10
5
-10
Glauber "the drinker" Sokolov, after participating in two ICPC World Finals, decided to abandon competitive programming and pursue his dream of working with the pop divas. His first job was as a dancer in one of Britney Spears' concerts, then composing songs for Lana del Rey, and he worked with Rihanna, Shakira, and many others. As time passed he used his unmatched intelligence to rise to the top, and became a producer.
Each song has an attribute named quality, that depends on how catchy it is, how touching the lyrics are and how danceable is the beat. This value can be represented as a number in the range [0, + ∞]. When choosing the tracks for an album, the quality of an album is equal to the glauber mean of the qualities all the songs in that album, that is, if a1, ..., aB are the qualities of the songs chosen for an album, then the quality of the album is 
.
The quality of an album is closely related to how much it will sell and how it will be portrayed on the media. Producers don't usually know the quality of their singers' songs, but Glauber is no simple producer.
Glauber manages both Katy Perry and Taylor Swift music, and both divas are about to release an album. Each singer has a collection of songs, and Glauber will choose one or more songs from that collection to create an album. As both singers are very good, Glauber knows the quality of all of their songs are integers not smaller than one.
To avoid creating any more bad blood between them, Glauber wants to choose albums with the same quality, so that the media won't compare them and rate one as better than the other. He forgot how to do that since he stopped programming, can you help him?
The first line has two integers N and M, the size of the collection of songs from Taylor Swift and Katy Perry, respectively.
The second line has N integers a1, ..., aN, the qualities of the songs from Taylor.
The third line has M integers b1, ..., bM, the qualities of the songs from Katy.
Limits
- 1 ≤ N, M ≤ 16
- 1 ≤ ai, bj ≤ 109
In the first line print "Y" if it is possible to choose such albums, and "N" otherwise.
If it is possible, print the sizes of the albums from Taylor and Katy in one line, and the quality of their songs in the next two lines, in the same format as in the input. The values for each album can be printed in any order. If there are multiple answers, you can print any of them.
2 3
2 15
6 5 7
Y
2 2
2 15
6 5
3 5
2 3 5
7 11 13 17 19
N
One of the most popular tourist attractions in the USA is the Central Park, in New York City. This park appears in several movies. It is also one of the largest in the world: it spans an area twice as large as Monaco. The park has many monuments and buildings such as the Belvedere Castle, the Victorian Gardens, the Marionette Theather, a zoo, among others. These attract visitors and tourists everyday. Central Park is administered by Central Park Conservancy (CPC). The CPC is responsible for security of the park, among other things. Recently, the CPC has noted that attendance to the park has been increasing. Due to concerns with the safety of visitors and tourists, the CPC has chosen a few places, and paths that joins these places, to be kept under constant surveillance.
Due to the humongous size of the park and budget issues, CPC is looking for a way to perform this task as efficiently as possible. The CPC hired an expert to solve this problem, Marcel "the optimizer" Saito. After studying the situation for a while, Marcel concluded that the problem can be solved optimally using his most famous technique: Separation Determined by Pairs (SDP).
SDP considers the places and paths that need protection and attributes pairs of paths to the guards, with the requirement that each path must be in a single pair, and each pair of paths must intersect at a common place. The following figure shows (a) the first sample input, and (b) one way to perform separation determined by pairs (each pair of paths is represented by a different type of line).
You wish to impress Marcel so that he will take you as an apprentice, by writing a program that finds such separation. After a little thought, you believe it is not always possible to find such separation, and you inquire Marcel. But Marcel says: "Everything is connected and we always have an even number of paths, so clearly it is always possible!" Though you still do not understand why this claim is true, you decide not to cross your mentor and start working.
The first line has two integers, N and M, separated by a blank space, the represent the number of critical places and the number of paths joining these places, respectively. The places are numbered 1 to N. Each one of the next M lines describes a path. Each path is represented by two integers, say u and v, separated by a blank space. The numbers u and v represent the places connected by this path. It is guaranteed that u ≠ v, that there are not multiple paths joining the same two places and that you can go from one place to any other place by traversing a sequence of paths.
Limits
- 1 ≤ N ≤ 104
- 2 ≤ M ≤ 5·105, and M is even
In the first line, print the number of paths of the separation, say K. In the next K lines, print the pairs of the separation, one per line. Each pair of paths must be represented by three integers separated by a blank space, and they must be printed in the following format: "u v w", where (u, v) and (v, w) are the paths that make up this pair. Note that it is equivalent to write "u v w" ou "w v u". If there are multiple solutions, any one will be accepted.
5 6
1 2
1 3
2 4
2 3
3 5
4 5
3
1 3 2
3 5 4
4 2 1
King of Tokyo is a board game in which each player is a monster trying to destroy Tokyo, or its enemies. In his or her turn, the player rolls 6 dice, and can reroll some of those dices to get better results. The dice are used to attack, gain energy, cure health or score points. King of Tokyo is very famous in the USA, and one day you were relaxing in the five-star hotel for the ICPC World Finals 2017 when the hotel staff challenged you and many other contestants to a game of King of Tokyo. You know they are very very good in this game, so you decide to use your programming abilities to help you. Your task is to implement a simple King of Tokyo player that tries to score the maximum amount of points, ignoring energy and damage to enemies.
The 6 dice you roll are alike, each with 6 distinct faces: 1, 2, 3, A, V, E. The faces A, V and E are not used for points and their effects should be ignored in this problem. The points awarded for rolling the 6 dice are calculated in the following way: for each 3 dice with the same face up (of the types 1, 2, or 3), you are awarded points equal to the number on the face up; for each additional die with that face up you get 1 extra point.
For example, if we represent a rolling of the dice by the values on their face up, then 22231A scores 2 points, 2222VV scores 3 points, 112233 scores 0 points, 33333E and 222333 scores 5 points.
One turn is done in the following way. Let K be the number of rerolls you have.
- Roll the 6 dice
- Choose a subset of the 6 dice, and reroll the chosen dice. You can repeat this procedure up to K times.
Given an initial configuration of rolled dice obtained by the the first step, and K, determine the expected number of points you can score this turn if you play optimally, and print the first subset of dice (possibly empty) that should be rerolled to get that expected value. To indicate that a certain die belongs to that subset, use the value in the face up.
In the first line, a single integer T, the number of test cases.
The next T lines begin with an integer K and are followed by a string of 6 characters representing the first roll.
Limits
- 1 ≤ T ≤ 500
- 0 ≤ K ≤ 4
- Each character in the string is one in 123AVE
For each test case, print 2 lines.
The first line should have a number, the expected number of points, if you play optimally. The error should not exceed 10 - 4.
The second line should contain up to 6 characters, the first subset of dice you should reroll to get the optimal result, print the values in the face up of those dice in any order. If the optimal play is not rerolling any dice, or if K = 0, print "-". This answer will be considered correct if, by rerolling these dice, the expected number of points you get if playing optimally after this play does not differ from the correct answer by more than 10 - 4.
3
0 112223
1 321321
4 EA2322
2.0000000000
-
1.7523148148
1122
3.5980742688
3EA
After going to the World Finals 2017, your team decided to stay in Rapid City for an extra week and visit some nearby attractions.
When visiting Mount Rushmore, a sculpture with the carved faces of presidents George Washington, Thomas Jefferson, Theodore Roosevelt and Abraham Lincoln, you wondered what was the chance that two of them had birthday in the same day. After a quick search on the internet, you find out that Lincoln was born on February 12 and Washington on February 11. Close enough!
The chance that in a group of 4 people 2 of them have the same birthdays is really quite low, about 1.6%. But your teammate tells you that in a group of 23 random people, the chance that some pair of them will have the same birthday is greater than 50%!
This is interesting, but if the year had a different number of days, how would this number change?
Given N, the number of days in a year, answer what is the minimum number of people needed in a room so that the chance that a pair of them has the same birthday is greater than 50%. You can assume each day has the same chance of being someone's birthday.
The input has a single integer N, the number of days in a year.
Limits
- 1 ≤ N ≤ 1000
Print a single integer, the answer to the problem.
365
23
666
31
To prepare for the ICPC World Finals 2017, your team attended to a training camp. Glauber "the drinker" Sokolov was the teacher, and all teams had to answer a form so he would know what topics were the best to teach. The first day was introductory and Glauber said he would just go over well-known topics. He said "I noticed you all answered that you knew the Knapsack problem very well, so here is a simple exercise about it, follows directly from the definitions. Solve the knapsack problem with repetitions.".
More formally, given N types of items, each one with a weight and a cost, choose some items such that the sum of its weights does not exceed S, and the sum of costs is maximum. You may choose any number of items of each type.
Solve Glauber's exercise.
On the first line two integers N and S, the number of types of items and the maximum allowed weight.
Each of the next N lines has two integers wi and ci, the weight and the cost of the ith type of item.
Limits
- 1 ≤ N, wi ≤ 103
- 0 ≤ S, ci ≤ 109
Print a single integer, the cost of the items you choose.
3 100
14 5
13 2
5 1
35