Greedy Algorithm

ID 38122. Acowdemia III

Farmer John opened a pasture to help Besie and her friends.
The PD pasture can be viewed as a large 2D grid of square cells. Each cell is labeled like this:

• C if the cell contains a cow
• G if the cell contains grass
• . if there is no cow or grass in the cell

ID 38141. Year of the Cow - 2

It is known that the signs of the zodiac in the Chinese calendar follow a 12-year cycle: Ox, Tiger, Rabbit, Dragon, Snake, Horse, Goat, Monkey, Rooster, Dog, Pig, Rat, and then Ox again. Less well known is the fact that at the end of each Ox year, a time portal opens, allowing cows to travel to any other Ox year in the past or future.

Cow Besi wants to visit N his predecessors who lived much earlier (\(1<=N<=0x10000\)). 0x10000 is a number in hexadecimal, which is 65536 in decimal.

Unfortunately, time travel is tedious, and Besi prefers to do no more K jumps in time (\(1<=K<= N\)). Help Besie determine the minimum number of years Besie needs to visit all her predecessors and return to the current year with no more K jumps along the way.

Besi doesn't have to use time spent in this Ox year if she doesn't want to. Time portals connect the first days of each of the Ox years to each other, so for example, if Besi used a time portal and then waited 12 years for the next time portal, she would spend exactly 12 years on the process. Besi starts her journey on the first day of the current Ox year, so she can travel back. None of Besi's predecessors lived in the Ox years.

Examples

ID 34851. Leapfrog

The path is paved with tiles in one row, the tiles are numbered from 1 to 1000. On the tiles with numbers A, B and C (A < B < C) there are three grasshoppers who play leapfrog according to the following rules:
1. Only one grasshopper can be placed on one tile.
2. In one move, one of the two outer grasshoppers (that is, from tile A or from tile C) can jump over the middle grasshopper (tile B) and stand on a tile that is exactly in the middle between the two remaining grasshoppers (that is, between B and C or A and B respectively). If there is an even number of tiles between the two remaining grasshoppers, then he can choose any of the two central tiles.
For example, if the grasshoppers originally sat on tiles number 1, 5, 10, then on the first move, the grasshopper from tile number 10 can jump to tile number 3 (it is in the middle between 1 and 5), or the grasshopper from tile number 1 can jump to tile number 7 or 8 (these two tiles are in the middle between tiles 5 and 10).
Three numbers are given: A, B, C. Determine the maximum number of moves the game can go on.

Input data format
The program receives as input three integers A, B and C (1 <= A < B < C <= 1000) written on separate lines.
Output data format
Print one number — the maximum number of moves that the game can go on.
 

ID 38337. Cookie Clicker

In Cookie Clicker, the player earns cookies by clicking on a large cookie with the mouse. By spending the cookies earned, the player can buy various upgrades (farm, factory, etc.) that also produce additional cookies.

Consider a simplified version of this game. Let the player be able to make one mouse click per second, which earns him one cookie. Also, at any time, the player can spend C cookies to buy a factory (at the same time, the player must have at least C cookies, after buying a factory, the number of his cookies instantly decreases by C ). Each factory bought increases the production of cookies per second by P pieces (i.e. if the player has one factory, then he gets 1  + P cookies per second, two factories — 1  +  2 P cookies, three factories &mdash 1  +  3 P cookies, etc.). The player can purchase an unlimited number of factories worth C cookies each. The factory starts producing additional cookies immediately, for example, if after some second of the game the player has C cookies, then the player can buy a factory and in the next second his production of cookies will increase by P pieces.

The original game never ends, but we will assume that the goal of the game is to collect N cookies. Determine the minimum time in which the goal of the game can be reached.

Input
The program receives as input three positive integers written on separate lines: C (factory cost), P (productivity of one factory) and N (required number of cookies).

Imprint
The program should output a single integer — the minimum time in seconds for which the player can get at least N cookies.

Examples

ID 38343. Round Equality

Given a valid equality of the form a₁+a₂+…+a_N=b₁+b₂+…b_M, where a₁,a₂,…,a<sub>N, b1,b2,…,bM – some real (not necessarily integer) numbers. Required to "round up" this is equality, i.e. get a new correct equality c1+c2+…+cN=d1+d2+…+dM, where c1,c2,…,cN< /sub>,d1,d2,…,dM — integers, and at the same time c1 is obtained by rounding the number a1 up or down to an integer (for example, the number 1.7 can be rounded up to either 1 or 2) , c2 obtained by rounding a2, …, cN – rounding aN, d1 – rounding b1, …, dM – rounding bM. If any of the numbers in the original equality was an integer, it should remain unchanged.

Input
The input file is given first the number N, then N numbers a1, a2, …, aN, then the number M, then the numbers b1, b2, …, bM. Each number is given on a separate line. M and N – natural numbers not exceeding 1000. Other numbers — real, each of them does not exceed 1000 in absolute value and contains no more than 6 digits after the decimal point. Here a1+a2+…+aN=b1+b2 +…bM.

Imprint
If "round up" equality is possible, then output the numbers c1,c2,…,cN, and then the numbers d 1,d2,…,dM. All numbers must be integers and printed without a decimal point. Numbers must be separated by spaces or newlines. If there are several solutions, print any of them.

If it is impossible to round the original equality to a true integer equality, print a single number 0.</sub>

Examples

ID 38473. weighing stones

Jack found N stones and arranged them in order of increasing mass. The masses of all stones are different. The lightest stone was number 1, the next ≤ 2 and so on, the heaviest one was numbered N.

Jack has a scale and decided to put all the stones on it in some order. The order in which he will place the stones is known, and which stone will land on which bowl.

Your task — determine the state of the scales after adding each stone. The exact weights of the stones are not known — only their numbers are given.

Input
The first line contains the integer N (1  N ≤ 100000).

Each of the next N lines contains two integers: R (1 ≤ R ≤ N) and S (1 ≤ S ≤ 2). R is the number of the stone that will be placed on the bowl S. All Rs will be different.

Imprint
Output N lines -  one for each stone. If bowl 1 is heavier after adding the corresponding stone, print “<”. If side 2 is heavier, print “>”. If it is impossible to determine what state the scales will be in, print “?”.

Examples

<
>
>
?
>

ID 38546. Sale

Stores for promotional purposes often arrange sales. For example, one of the major chains of stationery stores announced two promotional offers: "Buy N identical products and get one more product for free" and "Buy K products for the price of K&minus 1 product".

To hold the Olympiad, the organizers need to print out the conditions for the participants, which takes a lot of paper. Each pack costs B rubles. What is the maximum number of packs of paper that can be purchased for A rubles, using promotional offers correctly?

Input
The input file contains integers N, K, A and B (1 ≤ N ≤ 100, 2 ≤ K ≤ 100, 1 ≤ A ≤ 10⁹, 1 ≤ B ≤ 10⁹), separated by spaces.

Imprint
Print a single integer - the maximum number of packs of paper that the organizers of the Olympiad can buy.

Note
In the first example, using the second promotional offer twice, you can buy 8 packs of paper, paying for 6.

In the second example, promotional offers cannot be used.

In the third example, you can use each of the two promotional offers once and buy another pack of paper with the remaining ruble.

Examples

ID 38571. Buses

The new President of Far Far Away began his work with a complete revision of the country's public transport system. As a result, on the basis of sociological surveys of the population, an ideal daily schedule of intercity buses was compiled, approved by the Parliament of the Republic.

Moreover, it was decided to replace the entire bus fleet with the same new, very expensive, but much more reliable, beautiful and comfortable cars.

The bus network of the country covers N cities, numbered with integers from 1 to N.

The ideal schedule contains M daily flights, the i-th flight starts in city Fi at time Xi and ends in some other city Gi at time Yi. The duration of each flight is non-zero and strictly less than 24 hours. Flight i is performed by one of the buses located at time Xi in the city Fi.

New buses do not require repairs and can operate around the clock, so a bus that arrives at some point in time in a certain city is always ready at the same time or later to go to service any other flight from this city. The bus can leave the city only on a scheduled flight.

It is assumed that the schedule will operate indefinitely, so it may not be possible to serve it with any finite number of buses.

Determine the smallest number of new buses sufficient to keep the schedule running for an unlimited period of time.

Input
The first line contains integers N and M (1 ≤ N, M ≤ 100 000) — number of cities and bus routes respectively.

Each of the following M lines contains a description of the bus route: departure city number Fi, departure time Xi, destination city number Gi (Fi ≠ Gi), arrival time Yi, separated from each other by one space. Arrival and departure times are specified in the HH:MM format, where HH — hours from 00 to 23, MM — minutes from 00 to 59.

Imprint
Print one number — the minimum required number of buses. If the schedule cannot be served for an unlimited period of time by a finite number of buses, print the number -1.

Examples

ID 38572. Now a birch, then a mountain ash ...

In order to improve the landscape architecture and environmental situation, the municipal administration has developed a draft program for greening the central avenue. According to the project, on one side of the avenue, it is planned to plant trees of K different species in a row, for which tree seedlings were purchased, and a_i seedlings were purchased.

To achieve the aesthetic perfection of the planted row of trees, it is required that among any P consecutive trees, all trees be of different species. If the number of trees in a row is less than P, then they must all be different.

It is required to write a program that finds the maximum number of trees in an aesthetically perfect row planted from purchased seedlings.

Input
The first line contains two integers: K — number of different tree species (1 ≤ K ≤ 100,000), and P — the required number of consecutive trees of different species (2 ≤ P ≤ K). The next K lines of  input data contain integers ai, specifying the number of purchased tree seedlings of the i-th type  (1 ≤ a_i ≤ 10⁹), by one number per line.

Imprint
Print a single number — the maximum number of trees that, planted in a row in some order, achieves aesthetic perfection.

 

Examples

ID 38920. elves and deer

The New Year is coming soon and Santa Claus has already started preparing his magical reindeer team, on which he delivers gifts to children. It is known that the team is driven by several magical deer, each of which is ridden by two elves.

But the magical deer – obstinate animals, so not any two elves can ride any deer. Namely, each deer is characterized by some obstinacy a_i, and each elf – temperament b_i. Two elves j and k can ride the i-th reindeer if and only if either b_j < a_i < b_k or b_k < a_i < b_j.

To make his appearance as spectacular as possible, Santa Claus wants his team to have as many reindeer as possible. About every deer Santa knows his obstinacy, and about every elf – his temperament.

Help Santa figure out the maximum number of reindeer he can include in his team, which reindeer he should choose, and which elves should ride them.

Input
The first line contains two integers m and n – the number of deer and elves, respectively ( 1 ≤ m, n ≤ 100,000).

The second line contains m integers ai – deer obstinacy ( 0 ≤ a_i ≤ 10⁹). The third line contains n integers bi – elves temperament ( 0 ≤ b_i ≤ 10⁹).

Imprint
In the first line  print a single number k – the maximum number of reindeer that Santa Claus can include in his team. In the next k lines print three integers each: d_i, e_i, 1, e_i, 2 – for each reindeer in the team print its number and the numbers of the elves that will ride it. If there are several solutions, print any one.

Both elves and deer are numbered, starting from one, in the order in which they are given in the input.

Examples

ID 27220. paired up

ID 39672. Tom Sawyer and the word on the fence

While painting the fence, Tom Sawyer wrote the word s on it. However, he then decided that palindrome words looked prettier.
Now he wants to add another word g to the given word s on the right so that the resulting word sg is a palindrome. However, in order to save paint, the length g should be as short as possible.
Help Tom Sawyer identify the word g.

Input:
The first line contains the word s (1 <= |s| <= 200000) consisting of lowercase Latin letters.

Output:
Print the minimum possible length of the word g that needs to be completed so that the word sg on the fence becomes a palindrome. If you don't need to add anything, then print '-'.

Examples:
 

ID 40022. Interregional Olympiad

At the Interregional Robot Programming Olympiad, competitions are held in one round and in an unusual format. The tasks are given to the participants sequentially, not all at the very beginning of the round, and each i-th task (1 ≤ i ≤ n) becomes available to the participants at its time s_i. Upon receipt of the next task, each participant must immediately determine whether he will solve it or not. If he chooses to solve this problem, then he has t_i minutes to submit its solution for verification, and during this time he cannot switch to solving another problem. If the participant refuses to solve this problem, then in the future he cannot return to it. At the moment when the time allotted for the task that the participant is solving has ended, he can start solving another task that became available at the same moment, if there is such a task, or wait for another task to appear. At the same time, for the correct solution of the i-th problem, the participant receives c_i points.

Artur, who represents one of the regional artificial intelligence centers at the interregional Olympiad, understands that not only the ability to solve problems, but also the correct strategic calculation of which problems need to be solved and which ones to skip, plays an important role at such an Olympiad. He, like all participants, before the start of the tour knows at what point in time each task will become available, how much time will be allotted for its solution and how many points you can get for solving it. Artur is a talented student and therefore will be able to successfully solve any problem he chooses to solve at the Olympiad in the allotted time and pass for verification.

It is required to write a program that determines the maximum number of points Arthur can get with the optimal choice of problems that he will solve, as well as the number and list of such problems.

Input
The first line contains one integer n (1 ≤ n ≤ 10⁵) the number of problems in the Olympiad.

The next n lines contain descriptions of the problems, three numbers on each line: si the moment the i-th problem appears in minutes, t_i the time allotted for its solution in minutes, and ci how many points the participant will receive for solving this problem (1 ≤ s_i, t_i, c_i ≤ 10⁹).

Imprint
First line  must contain a single number – the maximum number of points that Arthur can get at the Olympiad.

The second line should contain one integer m - the number of tasks to be solved with the optimal choice.

The third line should contain m space-separated integers - the numbers of these problems in the order in which they were solved. The tasks are numbered, starting from one, in the order they are described in the input file.

If there are several optimal answers, print any of them.

Examples

ID 43034. Sorter Tommy

Tommy has a children's toy "sorter", with n pegs arranged in a row. There is now no more than one disk on each peg (that is, there is a disk on some peg, but on some it No). Tommy wants to rearrange the given disks on the pegs so that they form a non-decreasing sequence when viewed from left to right. That is, on each next peg, the number of disks must be no less than on the previous one.  What is the minimum number of Tommy's disks that need to be shifted?

Examples

8
0 0 1 1 1 1 1 1

0

eleven
1 1 0 0 1 0 0 1 1 1 0

3

ID 43714. joyful figure

Little Misha loves to play with counting sticks. He takes counting sticks from his sister, a first grader. Since he rarely gives them back, Mom often has to buy new sticks. Therefore, not all Misha's sticks are the same, but all sticks have an integer length.
Today Misha is building the next figure out of sticks. He started from the corner of the room. We will denote, conditionally, this angle by the coordinate (0, 0). Then Misha lays out the stick parallel to one of the two walls coming from the given corner. We will assume that the walls are even and form an angle of 90 degrees with each other at the point (0, 0). At the same time, Misha never lays out two sticks in a row at the same time parallel to the same wall (in other words, he always alternates the direction of the sticks).
Misha, although he is small and does not know geometry, is always happy if the end of his figure is as far as possible from the starting angle. Help Misha lay out a figure that will make him happy. Any two sticks that Misha places always have at least one point of contact or intersection.

Input
The program receives several lines as input. The first line contains the integer n (1<= n <= 100000) — the number of sticks Misha has. The second line contains n integers a1,...,a n (1 <= ai <= 10000) - lengths of Misha sticks.

Imprint
Print a single integer — square of the maximum distance from the corner with coordinate (0,0) to the end point of the shape that Misha built.
 
 

Examples

ID 43718. Misha's Cubes

Little Misha has cubes, each of which has one English lowercase letter written on it. Yesterday he laid out the cubes in two rows. In the first row Misha has n cubes with letters, in the second - m cubes with letters. It so happened that in these two rows there are no matching letters. In other words, no letter is contained in both rows at the same time.
Today little Misha decided to continue playing with blocks. But now he takes any one cube from any row and makes a third row of them, always adding a cube to the end. Little Misha never takes more than k dice in a row from the same row. Misha stopped playing when he ran out of cubes in one row (in the first or in the second).
Dad, who was watching the game, noticed that playing in this way, Misha got the lexicographically smallest line. Using the known two strings, which are formed by reading the letters of the first and second rows and the number k determine the string that little Misha received.

The string x is lexicographically less than the string y only and only if one of the following conditions is true:
- x is a prefix of y, but x != y;
- in the first position, where x and y differ, in the string x there is a letter that is in the alphabet earlier than the corresponding letter y.


Input
The program receives several lines as input. The first line contains three numbers: n - the number of cubes in the first row, m - the number of cubes in the second row, k > is an integer(1 <= n, m, k <= 100). The second line contains a string a of length n - a string formed by reading the letters written on the cubes of the first row. In the third line - string b of length m - a string formed by reading the letters written on the cubes of the second row.

Imprint
Print the answer to the problem.
 
 

Examples