Author:  NEERC 2017  Time limit:  3 sec  
Input file:  Standard input  Memory limit:  512 Mb  
Output file:  Standard output 
You were invited to the annual archery tournament. You are going to compete against the best archers from all of the Northern Eurasia. This year, a new type of competition is introduced, where a shooting range is dynamic and new targets might appear at any second.
As the shooting range is far enough from you, it can be represented as a 2D plane, where y = 0 is the ground level. There are some targets in a shape of a circle, and all the targets are standing on the ground. That means, if a target's center is (x, y) (y > 0), then its radius is equal to y, so that it touches the line y = 0. No two targets simultaneously present at the range at any given time intersect (but they may touch).
Initially, the shooting range is empty. Your participation in this competition can be described as n events: either a new target appears at the range, or you shoot an arrow at some point at the range. To hit a target, you must shoot strictly inside the circle (hitting the border does not count). If you shoot and hit some target, then the target is removed from the range and you are awarded one point.
The first line of the input contains integer n (1 ≤ n ≤ 2 ⋅ 10^{5}). Next n lines describe the events happening at the tournament. The ith line contains three integers t_{i}, x_{i}, and y_{i} (t_{i} = 1, 2; −10^{9} ≤ x_{i}, y_{i} ≤ 10^{9}; y_{i} > 0).
For each of your shots, output a separate line with the single integer. If the shot did not hit any target, print ``texttt−1''. If the shot hit a target, print the number of event when that target was added to the range. Events are numbered starting from 1.
No.  Standard input  Standard output 

1 


Author:  NEERC 2017  Time limit:  3 sec  
Input file:  input.txt  Memory limit:  512 Mb  
Output file:  output.txt 
Fiora is a game designer. Now she is designing the final level for her new game.
A level for this game is a labyrinth on a rectangular grid with lots of enemies. Player starts her game at the square (0, 0) and her purpose is to get to the square (a, b). Fiora has lots of ideas on how to put enemies, but she does not like designing labyrinths. She needs your help here.
Fiora is drawing levels in a special level editor which supports one basic block to design a labyrinth. This block is an Lshaped corner, consisting of two perpendicular rectangles 1 × n squares in size intersecting at 1 × 1 square.
It is possible to rotate this block in four ways. Blocks cannot intersect, but they can touch each other. Player can move through all the squares lying in any block. She can move between two squares if they are sharing a side, even if they are in different blocks.
Fiora wants to design the final level with the minimal possible number of blocks. Of course, it should be possible to move from square (0, 0) to square (a, b).
The first line of the input consists of a single integer m (1 ≤ m ≤ 100) — the number of test cases.
It is followed by m test cases.
Each test case is on a separate line and consists of three integers a, b, and n (−10^{8} ≤ a, b ≤ 10^{8}; 2 ≤ n ≤ 10^{8}) — a is the coordinate of the final point along the horizontal axis, b is the coordinate of the final point along the vertical axis, and n is the size of the block.
The final point is not same as the starting one (either a ≠ 0 or b ≠ 0).
For each test case, in the first line print the minimal number k of blocks you need. In the following k lines print description of these blocks.
Each Lshaped corner block is described by coordinates of two cells. Print coordinates of the end of its vertical rectangle, followed by coordinates of the end of its horizontal rectangle.
Specify the coordinates of the ends that are opposite to the intersection of the rectangles. Note that the order of cells in the block description matters, since a change of the order results in a reflected block. Coordinates of each end should be printed with the coordinate along the horizontal axis first, followed by the coordinate along the vertical axis.
All coordinates in the output should not exceed 10^{9} by absolute value.
It is guaranteed that the total number of blocks in the correct output does not exceed 10^{5} for all test cases combined.
No.  Input file (input.txt ) 
Output file (output.txt ) 

1 


Author:  NEERC 2017  Time limit:  6 sec  
Input file:  input.txt  Memory limit:  512 Mb  
Output file:  output.txt 
While studying combinatorial optimization, Lucas came across the notion of ``laminar set family''. A subset family F of some set Ω is called laminar if and only if it does not contain an empty set and for any two distinct sets A, B ∈ F it is correct that either A ⊂ B or B ⊂ A or A ∩ B = varnothing.
As an experienced problem setter Lucas always tries to apply each new piece of knowledge he gets as an idea for a programming competition problem. An area of his scientific interests covers recognition problems that usually sound like ``Given some weird combinatorial property, check if the given structure satisfies it''.
Lucas believes that the perfect programming competition problem should contain a cactus a tree in it. Trying to put together laminar sets and trees into a recognition problem, he finally came up with the following problem: given an undirected tree on n vertices and a family F = {F_{1}, …, F_{k}} of sets, where F_{i} consists of all vertices belonging to the simple path between some two vertices a_{i} and b_{i} of the tree, check if the family F is a laminar family. Note that in this case Ω = V, and each F_{i} ⊆ V.
As you can see, Lucas had succeeded in suggesting this problem to the programming contest. Now it is up to you to solve it.
The first line of the input contains two integers n and f (1 ≤ n, f ≤ 100 000) — the number of vertices in the tree and the number of elements in a family F.
Next n − 1 lines describe the tree structure. In the ith line there are two integers u_{i} and v_{i} (1 ≤ u_{i}, v_{i} ≤ n, u_{i} ≠ v_{i}) — the indices of the vertices that are connected by the ith edge of the tree.
Next f lines describe the sets forming the family F. In the ith line there are two integers a_{i} and b_{i} (1 ≤ a_{i}, b_{i} ≤ n), such that F_{i} consists of all vertices belonging to the simple path between vertices a_{i} and b_{i} in the tree (including a_{i} and b_{i}).
Output the only word ``tYes'' or ``tNo'' depending on whether or not the given set family is laminar.
No.  Input file (input.txt ) 
Output file (output.txt ) 

1 


2 


Author:  NEERC 2016  Time limit:  2 sec  
Input file:  input.txt  Memory limit:  512 Mb  
Output file:  output.txt 
Mayor Adam East wants to improve the public transport network of Harshel city by introducing the network of stations with unicycles. Any person who owns a special card can come to a station and request a unicycle to ride or drop one.
The procedure of requesting a unicycle is simple. The person enters a queue. If there is a unicycle available, then the first person from the queue takes it immediately. Otherwise, people in the queue wait until someone drops a unicycle at the station.
Let the wait time be the time that person spends between the request (entrance to the queue) and obtaining a unicycle. If the person does not receive a unicycle at all, then the wait time is infinity. The total wait time is the sum of wait times for each person.
Adam already knows the schedule of all the people for every day. He knows at what times people request and drop unicycles at the Central Station that can hold any number of unicycles at the same time. The only thing he does not know is how many unicycles should be placed there at the start of each day. He asks you several questions to calculate the total wait time given the starting number of unicycles.
The first line contains n and q (1 ≤ n, q ≤ 10^{5}), where n is the total number of unicycle requests and unicycle drops at the Central Station, and q is the number of questions Adam asks you.
The next n lines describe operations at the Central Station. Each line contains one description of operation:
For each of the described operations 1 ≤ t ≤ 10^{9} and 1 ≤ k ≤ 10^{4}.
The last line of the input contains q different integers b_{i} (0 ≤ b_{i} ≤ 10^{9}) — the number of unicycles at the start of the day.
The operations are given in the strongly increasing order of time.
The output shall consist of q lines. The ith line shall display the total wait time for the case of b_{i} unicycles at the start of the day. If the total wait time is infinite, then the corresponding line shall display the word ``INFINITY''.
No.  Input file (input.txt ) 
Output file (output.txt ) 

1 


Author:  NEERC 2016  Time limit:  2 sec  
Input file:  input.txt  Memory limit:  512 Mb  
Output file:  output.txt 
Fedor is an avid traveler. As a result of his hobby, he has gathered a big collection of postcards from all over the world. Each postcard has a unique picture on the front side and some fields for address information and text on the back side.
During one of the parties at Fedor's house, he decided to show all his of postcards to the guests. To achieve that, he wants to lay them all out on the table. Initially, all of his postcards are arranged in a single stack that Fedor is holding in his hands. Unfortunately, some of the postcards in that stack can be turned incorrectly — upside down. Ideally, Fedor would like all postcards on the table to lie with the picture on top, but looking at every postcard and turning it over individually can be very timeconsuming. Instead, he came up with the following process:
Of course, after all the postcards are on the table, there might still be some that lie back side up. What is the expected number of such postcards?
The input consists of a single line of ``C'' and ``W'' characters — ith character corresponds to ith postcard in the stack, counting from the top of the stack. ``C'' means that ith postcard is oriented correctly in the initial stack, and ``W'' means that ith postcard is oriented in the wrong way. The number of characters is between 1 and 10^{6} inclusive.
Output one real number — the expected number of incorrectly placed postcards on the table. The absolute or relative error should not exceed 10^{−9}.
No.  Input file (input.txt ) 
Output file (output.txt ) 

1 


2 


Author:  NEERC 2016  Time limit:  2 sec  
Input file:  input.txt  Memory limit:  512 Mb  
Output file:  output.txt 
Jane is a game designer and she designs the next version of Jenga Boom, where the blocks have dimensions of 1 × w × wn instead of the ordinary 1 × 2 × 6.
As usual, the initial tower is created at the game start. It consists of the blocks in levels of n blocks placed next to each other along their long sides and at a right angle to the previous level. Players remove blocks from the tower in turns, until the tower collapses.
Jane wants to build a game simulator that helps her to decide the best n and w.
The simulator shall compute the moment when the tower collapses if blocks are removed in the specified order. Tower collapses if there is a crosssection between levels such that the center of the mass of the levels above it does not belong to or is at the edge of the convex hull of the previous level projection.
The first line contains two integers n and w that define the dimensions of the block as described in the problem statement (1 ≤ n, w ≤ 10 000).
The second line also contains two integers: h — the number of levels in the tower and m — the number of removed blocks (1 ≤ h, m ≤ 5 000).
The next m lines contain coordinates of the removed blocks with two integers each: l_{i} — the level of the block, counting from the bottom and k_{i} — the position of the block, counting from the edge nearest to the players (1 ≤ l_{i} ≤ h; 1 ≤ k_{i} ≤ n).
Blocks are removed one by one and no block is removed twice.
In the first line output ``yes'' if the tower collapses, and ``no'' otherwise. In the former case, output the number of the block (starting from 1), that was removed just before the collapse, in the next line.
No.  Input file (input.txt ) 
Output file (output.txt ) 

1 


2 


3 


Author:  NEERC 2016  Time limit:  2 sec  
Input file:  input.txt  Memory limit:  512 Mb  
Output file:  output.txt 
Lidia likes sets of prime numbers. When she is bored, she starts writing them down into the Extremely Long Notebook for Prime Sets.
Elements of each set are written down in ascending order. Each set of prime numbers appears in her notebook eventually. A set with a smaller sum always appears before a set with a larger sum. Sets with the same sum are sorted in ascending lexicographical order: they are compared by the first element, if the first elements are equal, then by second element, and so on.
Just in case someone decides to parse her notebook, she writes down her sets in a machinereadable JSON format. Of course, she puts a space after each comma. Here's the beginning of her notebook:
[2], [3], [2, 3], [5], [2, 5], [7], [3, 5], [2, 7], [2, 3, 5], [3, 7], [11], [2, 3, 7], [5, 7], [2, 11], [13], [2, 5, 7],
Lidia wants to doublecheck her work, so here is her request for you: given two integers, a and b, output a substring of her notebook from the position a to the position b (inclusive, counting from 1).
The first line contains two integers, a and b (1 ≤ a ≤ b ≤ 10^{18}; b − a ≤ 10^{5}).
Output the substring of the notebook described in the problem statement from the position a to the position b. You must write a line with exactly b−a+1 characters, including any leading and/or trailing spaces.
No.  Input file (input.txt ) 
Output file (output.txt ) 

1 


2 


Author:  NEERC 2015  Time limit:  2 sec  
Input file:  input.txt  Memory limit:  512 Mb  
Output file:  output.txt 
King Karl is a responsible and diligent ruler. Each year he travels across his country to make certain that all cities are doing well.
There are n cities in his country and m roads. In order to control the travelers, each road is unidirectional, that is a road from city a to city b can not be passed from b to a.
Karl wants to travel along the roads in such a way that he starts in the capital, visits every noncapital city exactly once, and finishes in the capital again.
As a transport minister, you are obliged to find such a route, or to determine that such a route doesn't exist.
The first line contains two integers n and m (2 ≤ n ≤ 100 000, 0 ≤ m ≤ n + 20) — the number of cities and the number of roads in the country.
Each of the next m lines contains two integers a_{i} and b_{i} (1 ≤ a_{i}, b_{i} ≤ n), meaning that there is a oneway road from city a_{i} to city b_{i}. Cities are numbered from 1 to n. The capital is numbered as 1.
If there is a route that passes through each noncapital city exactly once, starting and finishing in the capital, then output n+1 spaceseparated integers — a list of cities along the route. Do output the capital city both in the beginning and in the end of the route. If there is no desired route, output ``There is no route, Karl!'' (without quotation marks).
No.  Input file (input.txt ) 
Output file (output.txt ) 

1 


2 


Author:  NEERC 2015  Time limit:  2 sec  
Input file:  input.txt  Memory limit:  512 Mb  
Output file:  output.txt 
Louis L Le RoiUnivers has ordered to improve the landscape that is seen from the royal palace. His Majesty prefers to see a high mountain.
The Chief Landscape Manager is going to raise a mountain for Louis. He represents a landscape as a flat picture on a grid of unit squares. Some of the squares are already filled with rock, while others are empty. This greatly simplifies the design. Unit squares are small enough, and the landscape seems to be smooth from the royal palace.
The Chief Landscape Manager has a plan of the landscape — the heights of all rockfilled columns for each unit of width. He is going to add at most n square units of stones atop of the existing landscape to make a mountain with as high peak as possible. Unfortunately, piles of stones are quite unstable. A unit square of stones may be placed only exactly on top of the other filled square of stones or rock, moreover the squares immediately to the bottomleft and to bottomright of it should be already filled.
Your task is to help The Chief Landscape Manager to determine the maximum height of the highest mountain he can build.
The first line of the input file contains two integers w — the width of the existing landscape and n — the maximum number of squares of stones to add (1 ≤ w ≤ 100 000, 0 ≤ n ≤ 10^{18}).
Each of the following w lines contains a single integer h_{i} — the height of the existing landscape column (1 ≤ h_{i} ≤ 10^{9}).
The output file shall contain the single integer — the maximum possible landscape height after at most n unit squares of stones are added in a stable way.
No.  Input file (input.txt ) 
Output file (output.txt ) 

1 


2 


Author:  NEERC 2013  Time limit:  3 sec  
Input file:  hack.in  Memory limit:  512 Mb  
Output file:  hack.out 
Pavel is sending to his friend Egor some array of nonnegative integers. He wants to be sure, that nobody hacks the array before his friend gets it. To solve this problem Pavel need to compute some kind of a checksum or a digest for his array. Pavel has an innovative mind, so he invents the following algorithm to compute the digest for his array: count the number of subarrays in which the bitwise xor of the numbers in the subarray is equal to the bitwise and of the same numbers.
For example, consider an array of four binary numbers “01”, “10”, “11”, and “11”. The table below to the left lists the results of the bitwise xor of numbers for each subarray of this array, and the table below to the right list the results of the bitwise and of numbers for each subarray of this array. The rows of the table correspond to the starting elements of the subarray from the 1st element of the array to the 4th one, while columns correspond to the ending elements of the subarray. Matching values are highlighted with gray background.
Your task is to help Pavel compute this kind of a digest of the given array.
The first line contains one integer n (1 ≤ n ≤ 100 000). The second line contains n nonnegative integers a_{i}(0 ≤ a_{i} ≤ 2^{31} − 1) that are written in decimal notation.
On the first line of the output print Pavel’s digest of the given array.
No.  Input file (hack.in ) 
Output file (hack.out ) 

1 


Author:  NEERC 2013  Time limit:  3 sec  
Input file:  kabaleo.in  Memory limit:  512 Mb  
Output file:  kabaleo.out 
Kabaleo Lite is a board game. The board consists of several stacks of conical chips of various colors. Only the color of the top chip of the stack is visible.
Each player has a unique target color and a set of colored chips. The target color is hidden from other players, while the set of chips is visible to them. On his turn, player selects one of his chips and puts it on one of the board stacks, thus recoloring it to the color of the chosen chip.
After the last turn, the number of visible board chips of each color is calculated. The winning color is the color that occurs the maximum times. The player (if any) that has this color as his target color, wins the game. If there is no such player or if there are two or more colors that occur the maximum times, the game ends in a draw.
You are playing your last chip in the Kabaleo Lite game. Other players also have one chip left. You want to determine all possible moves that lead you to winning the game. You do not know the target colors of other players and you cannot predict their moves, so your move must guarantee your victory regardless of moves of your opponents.
The first line contains four integers n, p, c and h — the number of stacks on the board (1 ≤ n ≤ 10^{6}), the number of players (1 ≤ p ≤ 10^{6}), the number of chips’ colors (p≤c≤10^{6}), and your hidden color (1 ≤ h ≤ c).
The second line contains n integers b_{i} — the color of the visible board chip for each stack on the board (1 ≤ b_{i} ≤ c).
The third line contains p integers l_{i} — the color of the last chip for each player (1 ≤ l_{i} ≤ c). The players are numbered from one (you) to n in the order of their turns.
The first line must contain w — the number of winning moves.
The second line must contain w distinct numbers m_{i} — the numbers of the stacks on which your chip should be put to win. Stacks are numbered starting from 1 in the order that their visible colors are given in the input file. You can output their numbers in any order on this line.
Remember, that your move should be winning regardless of the moves of all other players.
No.  Input file (kabaleo.in ) 
Output file (kabaleo.out ) 

1 


Author:  NEERC 2011  Time limit:  3 sec  
Input file:  dictionary.in  Memory limit:  512 Mb  
Output file:  dictionary.out 
The Kingdom consists of n cities connected by n − 1 roads in such a way that there is exactly one way to travel from one city to another.
The King is a busy man and he constantly travels from city to city. Unfortunately, during one of his travels one of the roads got damaged and needed serious repairs. As a result, the King was unable to reach his destination in time.
After the incident the King decided to improve reliability of the road system. It was decided that the improved road system shall be able to withstand one damaged road, i.e. there shall always be a path from one city to another even when one road in the Kingdom is damaged. As always, the budget is limited so you need to minimize the number of new roads.
For example, the picture below shows 5 Kingdom’s cities numbered from 1 to 5 and roads between them in solid lines. One of the ways to build new roads is shown in dashed lines.
Your task is to build as few new roads as possible so that there is always a path between any two cities even if one of the roads gets unusable for any reason. There may be multiple optimal solutions. Any one can be used.
The first line of the input file contains integer n — the number of cities in the kingdom (2 ≤ n ≤ 100 000). The following n − 1 lines contain two integers u_{i}, vi each — the cities connected by ith road (1 ≤ ui, vi ≤ n).
The first line of the output file shall contain one integer k — the number of roads to be built. The following k lines shall contain two integers a_{i}, b_{i} each — the cities which should be connected by ith new road (1 ≤ ai, bi ≤ n).
The first line must contain w — the number of winning moves.
The second line must contain w distinct numbers m_{i} — the numbers of the stacks on which your chip should be put to win. Stacks are numbered starting from 1 in the order that their visible colors are given in the input file. You can output their numbers in any order on this line.
Remember, that your move should be winning regardless of the moves of all other players.
Author:  NEERC 2011  Time limit:  3 sec  
Input file:  gcd.in  Memory limit:  512 Mb  
Output file:  gcd.out 
Paul had a birthday yesterday, and they were playing a guessing game there with Andrew: Andrew was trying to guess Paul’s age. Andrew knew that Paul’s age is an integer between 1 and n, inclusive. Andrew can guess any number x between 1 and n, and Paul will tell him what is the greatest common divisor of x and his age.
Here’s a possible course of the game for n = 6. Andrew starts with guessing 3, and Paul replies that the greatest common divisor of 3 and his age is 1. That means that Paul’s age can’t be 3 or 6, but can still be 1, 2, 4 or 5. Andrew continues with guessing 2, and Paul replies 2. That means that Paul’s age can’t be 1 or 5, and the only two remaining choices are 2 and 4. Finally, Andrew guesses 4, and Paul replies 2. That means that Paul’s age is 2, and the game is over.
Andrew needed three guesses in the above example, but it’s possible to always determine Paul’s age in at most two guesses for n = 6. The optimal strategy for Andrew is: at the first step, guess 6. If Paul says 1, then its 1 or 5 and he can check which one by guessing 5. If Paul says 2, then its 2 or 4, and he can check by guesing 4 as we’ve seen above. If Paul says 3, then we already know the answer is 3. Finally, if Paul says 6, the answer is 6.
What is the number of guesses required in the worst case if Andrew guesses optimally for the given n?
The input file contains one integer n, 2 ≤ n ≤ 10 000.
Output one integer — the number of guesses Andrew will need to make in the worst case.
No.  Input file (gcd.in ) 
Output file (gcd.out ) 

1 


Author:  NEERC 2011  Time limit:  3 sec  
Input file:  kingdom.in  Memory limit:  512 Mb  
Output file:  kingdom.out 
The Kingdom consists of n cities connected by n − 1 roads in such a way that there is exactly one way to travel from one city to another.
The King is a busy man and he constantly travels from city to city. Unfortunately, during one of his travels one of the roads got damaged and needed serious repairs. As a result, the King was unable to reach his destination in time.
After the incident the King decided to improve reliability of the road system. It was decided that the improved road system shall be able to withstand one damaged road, i.e. there shall always be a path from one city to another even when one road in the Kingdom is damaged. As always, the budget is limited so you need to minimize the number of new roads.
For example, the picture below shows 5 Kingdom’s cities numbered from 1 to 5 and roads between them in solid lines. One of the ways to build new roads is shown in dashed lines.
Your task is to build as few new roads as possible so that there is always a path between any two cities even if one of the roads gets unusable for any reason. There may be multiple optimal solutions. Any one can be used.
The first line of the input file contains integer n — the number of cities in the kingdom (2 ≤ n ≤ 100 000). The following n − 1 lines contain two integers u_{i}, vi each — the cities connected by ith road (1 ≤ ui, vi ≤ n).
The first line of the output file shall contain one integer k — the number of roads to be built. The following k lines shall contain two integers a_{i}, b_{i} each — the cities which should be connected by ith new road (1 ≤ ai, bi ≤ n).
The first line must contain w — the number of winning moves.
The second line must contain w distinct numbers m_{i} — the numbers of the stacks on which your chip should be put to win. Stacks are numbered starting from 1 in the order that their visible colors are given in the input file. You can output their numbers in any order on this line.
Remember, that your move should be winning regardless of the moves of all other players.
No.  Input file (kingdom.in ) 
Output file (kingdom.out ) 

1 


2 

