1337xyz1337xyz/codeforces-editorial-full-2026-07-16 huggingface dataset:
Ivan the Fool VS Gorynych the Dragon
Contest: School Personal Contest #3 (Winter Computer School 2010/11) - Codeforces Beta Round 45 (ACM-ICPC Rules)
Difficulty rating: 2100
Tags: dp, games, graphs

Once upon a time in a kingdom far, far away… Okay, let’s start at the point where Ivan the Fool met Gorynych the Dragon. Ivan took out his magic sword and the battle began. First Gorynych had h heads and t tails. With each strike of the sword Ivan can either cut off several heads (from 1 to n, but not more than Gorynych has at the moment), or several tails (from 1 to m, but not more than Gorynych has at the moment). At the same time, horrible though it seems, Gorynych the Dragon can also grow new heads and tails. And the number of growing heads and tails is determined uniquely by the number of heads or tails cut by the current strike. When the total number of heads and tails exceeds R, Gorynych the Dragon strikes its final blow and destroys Ivan the Fool. That’s why Ivan aims to cut off all the dragon’s heads and tails as quickly as possible and win. The events can also develop in a third way: neither of the opponents can win over the other one and they will continue fighting forever.

The tale goes like this; easy to say, hard to do. Your task is to write a program that will determine the battle’s outcome. Consider that Ivan strikes consecutively. After each blow Gorynych grows a number of new heads and tails depending on the number of cut ones. Gorynych the Dragon is defeated if after the blow he loses all his heads and tails and can’t grow new ones. Ivan fights in the optimal way (fools are lucky), i.e.

- if Ivan can win, he wins having struck the least number of blows;
- if it is impossible to defeat Gorynych, but is possible to resist him for an infinitely long period of time, then that’s the strategy Ivan chooses;
- if Gorynych wins in any case, Ivan aims to resist him for as long as possible.

Input format:
The first line contains three integers h, t and R (0 ≤ h, t, R ≤ 200, 0 < h + t ≤ R) which represent the initial numbers of Gorynych’s heads and tails and the largest total number of heads and tails with which Gorynych the Dragon does not yet attack. The next line contains integer n (1 ≤ n ≤ 200). The next n contain pairs of non-negative numbers "hi ti" which represent the number of heads and the number of tails correspondingly, that will grow if Gorynych has i heads (1 ≤ i ≤ n) cut. The next line contains an integer m (1 ≤ m ≤ 200) and then — the description of Gorynych’s behavior when his tails are cut off in the format identical to the one described above. All the numbers in the input file do not exceed 200.

Output format:
Print "Ivan" (without quotes) in the first line if Ivan wins, or "Zmey" (that means a dragon in Russian) if Gorynych the Dragon wins. In the second line print a single integer which represents the number of blows Ivan makes. If the battle will continue forever, print in the first line "Draw".

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Example input:
2 2 4
2
1 0
0 1
3
0 1
0 1
0 0

Example output:
Ivan
2

Example input:
2 2 4
1
0 1
1
1 0

Example output:
Draw

Editorial:
Snow sellers
Contest: School Personal Contest #3 (Winter Computer School 2010/11) - Codeforces Beta Round 45 (ACM-ICPC Rules)
Difficulty rating: 2800
Tags: greedy, sortings

The New Year celebrations in Berland last n days. Only this year the winter is snowless, that’s why the winter celebrations’ organizers should buy artificial snow. There are m snow selling companies in Berland. Every day the i-th company produces wi cubic meters of snow. Next day the snow thaws and the company has to produce wi cubic meters of snow again. During the celebration new year discounts are on, that’s why the snow cost decreases every day. It is known that on the first day the total cost of all the snow produced by the i-th company is equal to ci bourles. Every day this total cost decreases by ai bourles, i.e. on the second day it is equal to ci - ai,and on the third day — to ci - 2ai, and so on. It is known that for one company the cost of the snow produced by it does not get negative or equal to zero. You have to organize the snow purchase so as to buy every day exactly W snow cubic meters. At that it is not necessary to buy from any company all the snow produced by it. If you buy ni cubic meters of snow (0 ≤ ni ≤ wi, the number ni is not necessarily integer!) from the i-th company at one of the days when the cost of its snow is equal to si, then its price will total to $$\frac{n_i s_i}{w_i}$$ bourles. During one day one can buy the snow from several companies. In different days one can buy the snow from different companies. It is required to make the purchases so as to spend as little money as possible. It is guaranteed that the snow produced by the companies will be enough.

Input format:
The first line contains integers n, m and W (1 ≤ n ≤ 100, 1 ≤ m ≤ 500000, 1 ≤ W ≤ 109) which represent the number of days, the number of companies and the amount of snow that needs to be purchased on every one of the n days. The second line contains m integers wi. The third line contains m integers ci. The fourth line contains m integers ai. All the numbers are strictly positive and do not exceed 109. For all the i the inequation ci - (n - 1)ai > 0 holds true.

Output format:
Print a single number — the answer to the given problem. Print the answer in the format with the decimal point (even if the answer is integer, it must contain the decimal point), without "e" and without leading zeroes. The answer should differ with the right one by no more than 10 - 9.

Constraints:
Time limit: 10.0 s
Memory limit: 256.0 MB

Example input:
2 3 10
4 4 4
5 5 8
1 2 5

Example output:
22.000000000000000

Example input:
100 2 1000000000
999999998 999999999
1000000000 1000000000
1 1

Example output:
99999995149.999995249999991

Editorial:
Galaxy Union
Contest: School Personal Contest #3 (Winter Computer School 2010/11) - Codeforces Beta Round 45 (ACM-ICPC Rules)
Difficulty rating: 2700
Tags: dp, trees, two pointers

In a far away galaxy there are n inhabited planets numbered with numbers from 1 to n. One day the presidents of all the n planets independently from each other came up with an idea of creating the Galaxy Union. Now they need to share this wonderful idea with their galaxymates, that’s why each president is busy working out a project of negotiating with the other presidents.

For negotiations between some pairs of the planets there are bidirectional communication channels, each of which is characterized with "dial duration" ti which, as a rule, takes several hours and exceeds the call duration greatly. Overall the galaxy has n communication channels and they unite all the planets into a uniform network. That means that it is possible to phone to any planet v from any planet u, perhaps, using some transitional planets v1, v2, ..., vm via the existing channels between u and v1, v1 and v2, ..., vm - 1 and vm, vm and v. At that the dial duration from u to v will be equal to the sum of dial durations of the used channels.

So, every president has to talk one by one to the presidents of all the rest n - 1 planets. At that the negotiations take place strictly consecutively, and until the negotiations with a planet stop, the dial to another one does not begin. As the matter is urgent, from the different ways to call the needed planet every time the quickest one is chosen. Little time is needed to assure another president on the importance of the Galaxy Union, that’s why the duration of the negotiations with each planet can be considered equal to the dial duration time for those planets. As the presidents know nothing about each other’s plans, they do not take into consideration the possibility that, for example, the sought president may call himself or already know about the founding of the Galaxy Union from other sources.

The governments of all the n planets asked you to work out the negotiation plans. First you are to find out for every president how much time his supposed negotiations will take.

Input format:
The first line contains an integer n (3 ≤ n ≤ 200000) which represents the number of planets in the Galaxy and the number of communication channels equal to it. The next n lines contain three integers each ai, bi and ti (1 ≤ ai, bi ≤ n, ai ≠ bi, 1 ≤ ti ≤ 103) that represent the numbers of planet joined by a communication channel and its "dial duration". There can be no more than one communication channel between a pair of planets.

Output format:
In the first line output n integers — the durations of the supposed negotiations for each president. Separate the numbers by spaces.

Constraints:
Time limit: 3.0 s
Memory limit: 256.0 MB

Example input:
3
1 2 3
2 3 2
1 3 1

Example output:
4 5 3

Example input:
3
1 2 3
2 3 2
1 3 5

Example output:
8 5 7

Editorial:
Black and White
Contest: School Personal Contest #3 (Winter Computer School 2010/11) - Codeforces Beta Round 45 (ACM-ICPC Rules)
Difficulty rating: 2800
Tags: constructive algorithms

According to the legends the king of Berland Berl I was noted for his love of beauty and order. One day he ordered to tile the palace hall's floor where balls and receptions used to take place with black and white tiles according to a regular geometrical pattern invented by him. However, as is after the case, due to low financing there were only a black and b white tiles delivered to the palace. The other c tiles were black and white (see the picture).

The initial plan failed! Having learned of that, the king gave a new command: tile the floor with the available tiles so that no black side of a tile touched a white one. The tiles are squares of one size 1 × 1, every black and white tile can be rotated in one of the four ways.

The court programmer was given the task to work out the plan of tiling and he coped with the task and didn't suffer the consequences of disobedience. And can you cope with it?

Input format:
The first line contains given integers n and m (1 ≤ n, m ≤ 100) which represent the sizes of the rectangle that needs to be tiled. The next line contains non-negative numbers a, b and c, a + b + c = nm, c ≥ m.

Output format:
Print 2n lines containing 2m characters each — the tiling scheme. Every tile is represented by a square 2 × 2 in the following manner (the order corresponds to the order of the picture above):

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Example input:
2 2
0 0 4

Example output:
\
../
#
\
/#
\
##/
.
\
/.

Example input:
2 3
1 2 3

Example output:
###/
\
#
##/..
\
#/....
/.....

Editorial:
Team Olympiad
Contest: Codeforces Round 279 (Div. 2)
Difficulty rating: 800
Tags: greedy, implementation, sortings

The School №0 of the capital of Berland has n children studying in it. All the children in this school are gifted: some of them are good at programming, some are good at maths, others are good at PE (Physical Education). Hence, for each child we know value ti:

- ti = 1, if the i-th child is good at programming,
- ti = 2, if the i-th child is good at maths,
- ti = 3, if the i-th child is good at PE

Each child happens to be good at exactly one of these three subjects.

The Team Scientific Decathlon Olympias requires teams of three students. The school teachers decided that the teams will be composed of three children that are good at different subjects. That is, each team must have one mathematician, one programmer and one sportsman. Of course, each child can be a member of no more than one team.

What is the maximum number of teams that the school will be able to present at the Olympiad? How should the teams be formed for that?

Input format:
The first line contains integer n (1 ≤ n ≤ 5000) — the number of children in the school. The second line contains n integers t1, t2, ..., tn (1 ≤ ti ≤ 3), where ti describes the skill of the i-th child.

Output format:
In the first line output integer w — the largest possible number of teams.

Then print w lines, containing three numbers in each line. Each triple represents the indexes of the children forming the team. You can print both the teams, and the numbers in the triplets in any order. The children are numbered from 1 to n in the order of their appearance in the input. Each child must participate in no more than one team. If there are several solutions, print any of them.

If no teams can be compiled, print the only line with value w equal to 0.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Example input:
7
1 3 1 3 2 1 2

Example output:
2
3 5 2
6 7 4

Example input:
4
2 1 1 2

Example output:
0

Editorial:
Queue
Contest: Codeforces Round 279 (Div. 2)
Difficulty rating: 1500
Tags: dsu, implementation

During the lunch break all n Berland State University students lined up in the food court. However, it turned out that the food court, too, has a lunch break and it temporarily stopped working.

Standing in a queue that isn't being served is so boring! So, each of the students wrote down the number of the student ID of the student that stands in line directly in front of him, and the student that stands in line directly behind him. If no one stands before or after a student (that is, he is the first one or the last one), then he writes down number 0 instead (in Berland State University student IDs are numerated from 1).

After that, all the students went about their business. When they returned, they found out that restoring the queue is not such an easy task.

Help the students to restore the state of the queue by the numbers of the student ID's of their neighbors in the queue.

Input format:
The first line contains integer n (2 ≤ n ≤ 2·105) — the number of students in the queue.

Then n lines follow, i-th line contains the pair of integers ai, bi (0 ≤ ai, bi ≤ 106), where ai is the ID number of a person in front of a student and bi is the ID number of a person behind a student. The lines are given in the arbitrary order. Value 0 is given instead of a neighbor's ID number if the neighbor doesn't exist.

The ID numbers of all students are distinct. It is guaranteed that the records correspond too the queue where all the students stand in some order.

Output format:
Print a sequence of n integers x1, x2, ..., xn — the sequence of ID numbers of all the students in the order they go in the queue from the first student to the last one.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
The picture illustrates the queue for the first sample.

Example input:
4
92 31
0 7
31 0
7 141

Example output:
92 7 31 141

Editorial:
Hacking Cypher
Contest: Codeforces Round 279 (Div. 2)
Difficulty rating: 1700
Tags: brute force, math, number theory, strings

Polycarpus participates in a competition for hacking into a new secure messenger. He's almost won.

Having carefully studied the interaction protocol, Polycarpus came to the conclusion that the secret key can be obtained if he properly cuts the public key of the application into two parts. The public key is a long integer which may consist of even a million digits!

Polycarpus needs to find such a way to cut the public key into two nonempty parts, that the first (left) part is divisible by a as a separate number, and the second (right) part is divisible by b as a separate number. Both parts should be positive integers that have no leading zeros. Polycarpus knows values a and b.

Help Polycarpus and find any suitable method to cut the public key.

Input format:
The first line of the input contains the public key of the messenger — an integer without leading zeroes, its length is in range from 1 to 106 digits. The second line contains a pair of space-separated positive integers a, b (1 ≤ a, b ≤ 108).

Output format:
In the first line print "YES" (without the quotes), if the method satisfying conditions above exists. In this case, next print two lines — the left and right parts after the cut. These two parts, being concatenated, must be exactly identical to the public key. The left part must be divisible by a, and the right part must be divisible by b. The two parts must be positive integers having no leading zeros. If there are several answers, print any of them.

If there is no answer, print in a single line "NO" (without the quotes).

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Example input:
116401024
97 1024

Example output:
YES
11640
1024

Example input:
284254589153928171911281811000
1009 1000

Example output:
YES
2842545891539
28171911281811000

Editorial:
Chocolate
Contest: Codeforces Round 279 (Div. 2)
Difficulty rating: 1900
Tags: brute force, dfs and similar, math, meet-in-the-middle, number theory

Polycarpus likes giving presents to Paraskevi. He has bought two chocolate bars, each of them has the shape of a segmented rectangle. The first bar is a1 × b1 segments large and the second one is a2 × b2 segments large.

Polycarpus wants to give Paraskevi one of the bars at the lunch break and eat the other one himself. Besides, he wants to show that Polycarpus's mind and Paraskevi's beauty are equally matched, so the two bars must have the same number of squares.

To make the bars have the same number of squares, Polycarpus eats a little piece of chocolate each minute. Each minute he does the following:

- he either breaks one bar exactly in half (vertically or horizontally) and eats exactly a half of the bar,
- or he chips of exactly one third of a bar (vertically or horizontally) and eats exactly a third of the bar.

In the first case he is left with a half, of the bar and in the second case he is left with two thirds of the bar.

Both variants aren't always possible, and sometimes Polycarpus cannot chip off a half nor a third. For example, if the bar is 16 × 23, then Polycarpus can chip off a half, but not a third. If the bar is 20 × 18, then Polycarpus can chip off both a half and a third. If the bar is 5 × 7, then Polycarpus cannot chip off a half nor a third.

What is the minimum number of minutes Polycarpus needs to make two bars consist of the same number of squares? Find not only the required minimum number of minutes, but also the possible sizes of the bars after the process.

Input format:
The first line of the input contains integers a1, b1 (1 ≤ a1, b1 ≤ 109) — the initial sizes of the first chocolate bar. The second line of the input contains integers a2, b2 (1 ≤ a2, b2 ≤ 109) — the initial sizes of the second bar.

You can use the data of type int64 (in Pascal), long long (in С++), long (in Java) to process large integers (exceeding 231 - 1).

Output format:
In the first line print m — the sought minimum number of minutes. In the second and third line print the possible sizes of the bars after they are leveled in m minutes. Print the sizes using the format identical to the input format. Print the sizes (the numbers in the printed pairs) in any order. The second line must correspond to the first bar and the third line must correspond to the second bar. If there are multiple solutions, print any of them.

If there is no solution, print a single line with integer -1.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Example input:
2 6
2 3

Example output:
1
1 6
2 3

Example input:
36 5
10 16

Example output:
3
16 5
5 16

Editorial:
Restoring Increasing Sequence
Contest: Codeforces Round 279 (Div. 2)
Difficulty rating: 2000
Tags: binary search, brute force, greedy, implementation

Peter wrote on the board a strictly increasing sequence of positive integers a1, a2, ..., an. Then Vasil replaced some digits in the numbers of this sequence by question marks. Thus, each question mark corresponds to exactly one lost digit.

Restore the the original sequence knowing digits remaining on the board.

Input format:
The first line of the input contains integer n (1 ≤ n ≤ 105) — the length of the sequence. Next n lines contain one element of the sequence each. Each element consists only of digits and question marks. No element starts from digit 0. Each element has length from 1 to 8 characters, inclusive.

Output format:
If the answer exists, print in the first line "YES" (without the quotes). Next n lines must contain the sequence of positive integers — a possible variant of Peter's sequence. The found sequence must be strictly increasing, it must be transformed from the given one by replacing each question mark by a single digit. All numbers on the resulting sequence must be written without leading zeroes. If there are multiple solutions, print any of them.

If there is no answer, print a single line "NO" (without the quotes).

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Example input:
3
?
18
1?

Example output:
YES
1
18
19

Example input:
2
??
?

Example output:
NO

Editorial:
Treeland Tour
Contest: Codeforces Round 279 (Div. 2)
Difficulty rating: 2200
Tags: data structures, dfs and similar, dp, trees

The "Road Accident" band is planning an unprecedented tour around Treeland. The RA fans are looking forward to the event and making bets on how many concerts their favorite group will have.

Treeland consists of n cities, some pairs of cities are connected by bidirectional roads. Overall the country has n - 1 roads. We know that it is possible to get to any city from any other one. The cities are numbered by integers from 1 to n. For every city we know its value ri — the number of people in it.

We know that the band will travel along some path, having concerts in some cities along the path. The band's path will not pass one city twice, each time they move to the city that hasn't been previously visited. Thus, the musicians will travel along some path (without visiting any city twice) and in some (not necessarily all) cities along the way they will have concerts.

The band plans to gather all the big stadiums and concert halls during the tour, so every time they will perform in a city which population is larger than the population of the previously visited with concert city. In other words, the sequence of population in the cities where the concerts will be held is strictly increasing.

In a recent interview with the leader of the "road accident" band promised to the fans that the band will give concert in the largest possible number of cities! Thus the band will travel along some chain of cities of Treeland and have concerts in some of these cities, so that the population number will increase, and the number of concerts will be the largest possible.

The fans of Treeland are frantically trying to figure out how many concerts the group will have in Treeland. Looks like they can't manage without some help from a real programmer! Help the fans find the sought number of concerts.

Input format:
The first line of the input contains integer n (2 ≤ n ≤ 6000) — the number of cities in Treeland. The next line contains n integers r1, r2, ..., rn (1 ≤ ri ≤ 106), where ri is the population of the i-th city. The next n - 1 lines contain the descriptions of the roads, one road per line. Each road is defined by a pair of integers aj, bj (1 ≤ aj, bj ≤ n) — the pair of the numbers of the cities that are connected by the j-th road. All numbers in the lines are separated by spaces.

Output format:
Print the number of cities where the "Road Accident" band will have concerts.

Constraints:
Time limit: 5.0 s
Memory limit: 256.0 MB

Example input:
6
1 2 3 4 5 1
1 2
2 3
3 4
3 5
3 6

Example output:
4

Example input:
5
1 2 3 4 5
1 2
1 3
2 4
3 5

Example output:
3

Editorial: