1337xyz1337xyz/codeforces-editorial-full-2026-07-16 huggingface dataset:
BerPaint
Contest: School Team Contest 2 (Winter Computer School 2010/11)
Difficulty rating: 2700
Tags: geometry, graphs

Anfisa the monkey got disappointed in word processors as they aren't good enough at reflecting all the range of her emotions, that's why she decided to switch to graphics editors. Having opened the BerPaint, she saw a white rectangle W × H in size which can be painted on. First Anfisa learnt to navigate the drawing tool which is used to paint segments and quickly painted on that rectangle a certain number of black-colored segments. The resulting picture didn't seem bright enough to Anfisa, that's why she turned her attention to the "fill" tool which is used to find a point on the rectangle to paint and choose a color, after which all the area which is the same color as the point it contains, is completely painted the chosen color. Having applied the fill several times, Anfisa expressed her emotions completely and stopped painting. Your task is by the information on the painted segments and applied fills to find out for every color the total area of the areas painted this color after all the fills.

Input format:
The first input line has two integers W and H (3 ≤ W, H ≤ 104) — the sizes of the initially white rectangular painting area. The second line contains integer n — the number of black segments (0 ≤ n ≤ 100). On the next n lines are described the segments themselves, each of which is given by coordinates of their endpoints x1, y1, x2, y2 (0 < x1, x2 < W, 0 < y1, y2 < H). All segments have non-zero length. The next line contains preset number of fills m (0 ≤ m ≤ 100). Each of the following m lines defines the fill operation in the form of "x y color", where (x, y) are the coordinates of the chosen point (0 < x < W, 0 < y < H), and color — a line of lowercase Latin letters from 1 to 15 symbols in length, determining the color. All coordinates given in the input are integers. Initially the rectangle is "white" in color, whereas the segments are drawn "black" in color.

Output format:
For every color present in the final picture print on the single line the name of the color and the total area of areas painted that color with an accuracy of 10 - 6. Print the colors in any order.

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

Note:
Initially the black segments painted by Anfisa can also be painted a color if any of the chosen points lays on the segment. The segments have areas equal to 0. That is why if in the final picture only parts of segments is painted some color, then the area, painted the color is equal to 0.

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

Example output:
blue 0.00000000
white 20.00000000

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

Example output:
green 4.00000000
white 21.00000000

Editorial:
Phone Number
Contest: School Team Contest 2 (Winter Computer School 2010/11)
Difficulty rating: 1700
Tags: dp

Alas, finding one's true love is not easy. Masha has been unsuccessful in that yet. Her friend Dasha told Masha about a way to determine the phone number of one's Prince Charming through arithmancy.

The phone number is divined like that. First one needs to write down one's own phone numbers. For example, let's suppose that Masha's phone number is 12345. After that one should write her favorite digit from 0 to 9 under the first digit of her number. That will be the first digit of the needed number. For example, Masha's favorite digit is 9. The second digit is determined as a half sum of the second digit of Masha's number and the already written down first digit from her beloved one's number. In this case the arithmetic average equals to (2 + 9) / 2 = 5.5. Masha can round the number up or down, depending on her wishes. For example, she chooses the digit 5. Having written down the resulting digit under the second digit of her number, Masha moves to finding the third digit in the same way, i.e. finding the half sum the the third digit of her number and the second digit of the new number. The result is (5 + 3) / 2 = 4. In this case the answer is unique. Thus, every i-th digit is determined as an arithmetic average of the i-th digit of Masha's number and the i - 1-th digit of her true love's number. If needed, the digit can be rounded up or down. For example, Masha can get:

12345

95444

Input format:
The first line contains nonempty sequence consisting of digits from 0 to 9 — Masha's phone number. The sequence length does not exceed 50.

Output format:
Output the single number — the number of phone numbers Masha will dial.

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

Example input:
12345

Example output:
48

Example input:
09

Example output:
15

Editorial:
Toys
Contest: School Team Contest 2 (Winter Computer School 2010/11)
Difficulty rating: 2300
Tags: brute force, combinatorics

Little Masha loves arranging her toys into piles on the floor. And she also hates it when somebody touches her toys. One day Masha arranged all her n toys into several piles and then her elder brother Sasha came and gathered all the piles into one. Having seen it, Masha got very upset and started crying. Sasha still can't calm Masha down and mom is going to come home soon and punish Sasha for having made Masha crying. That's why he decides to restore the piles' arrangement. However, he doesn't remember at all the way the toys used to lie. Of course, Masha remembers it, but she can't talk yet and can only help Sasha by shouting happily when he arranges the toys in the way they used to lie. That means that Sasha will have to arrange the toys in every possible way until Masha recognizes the needed arrangement. The relative position of the piles and toys in every pile is irrelevant, that's why the two ways of arranging the toys are considered different if can be found two such toys that when arranged in the first way lie in one and the same pile and do not if arranged in the second way. Sasha is looking for the fastest way of trying all the ways because mom will come soon. With every action Sasha can take a toy from any pile and move it to any other pile (as a result a new pile may appear or the old one may disappear). Sasha wants to find the sequence of actions as a result of which all the pile arrangement variants will be tried exactly one time each. Help Sasha. As we remember, initially all the toys are located in one pile.

Input format:
The first line contains an integer n (1 ≤ n ≤ 10) — the number of toys.

Output format:
In the first line print the number of different variants of arrangement of toys into piles. Then print all the ways of arranging toys into piles in the order in which Sasha should try them (i.e. every next way must result from the previous one through the operation described in the statement). Every way should be printed in the following format. In every pile the toys should be arranged in ascending order of the numbers. Then the piles should be sorted in ascending order of the numbers of the first toys there. Output every way on a single line. Cf. the example to specify the output data format. If the solution is not unique, output any of them.

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

Example input:
3

Example output:
5
{1,2,3}
{1,2},{3}
{1},{2,3}
{1},{2},{3}
{1,3},{2}

Editorial:
Triminoes
Contest: School Team Contest 2 (Winter Computer School 2010/11)
Difficulty rating: 2000
Tags: constructive algorithms, greedy

There are many interesting tasks on domino tilings. For example, an interesting fact is known. Let us take a standard chessboard (8 × 8) and cut exactly two squares out of it. It turns out that the resulting board can always be tiled using dominoes 1 × 2, if the two cut out squares are of the same color, otherwise it is impossible.

Petya grew bored with dominoes, that's why he took a chessboard (not necessarily 8 × 8), cut some squares out of it and tries to tile it using triminoes. Triminoes are reactangles 1 × 3 (or 3 × 1, because triminoes can be rotated freely), also the two extreme squares of a trimino are necessarily white and the square in the middle is black. The triminoes are allowed to put on the chessboard so that their squares matched the colors of the uncut squares of the chessboard, and also the colors must match: the black squares must be matched with the black ones only and the white ones — with the white squares. The triminoes must not protrude above the chessboard or overlap each other. All the uncut squares of the board must be covered with triminoes.

Help Petya find out if it is possible to tile his board using triminos in the described way and print one of the variants of tiling.

Input format:
The first line contains two integers n and m (1 ≤ n, m ≤ 1000) — the board size. Next n lines contain m symbols each and represent the board description. If some position contains ".", then the square in this position has been cut out. Symbol "w" stands for a white square, "b" stands for a black square. It is guaranteed that through adding the cut squares can result in a correct chessboard (i.e. with alternating black and white squares), thought, perhaps, of a non-standard size.

Output format:
If at least one correct tiling exists, in the first line print "YES" (without quotes), and then — the tiling description. The description must contain n lines, m symbols in each. The cut out squares, as well as in the input data, are marked by ".". To denote triminoes symbols "a", "b", "c", "d" can be used, and all the three squares of each trimino must be denoted by the same symbol. If two triminoes share a side, than they must be denoted by different symbols. Two triminoes not sharing a common side can be denoted by one and the same symbol (c.f. sample).

If there are multiple correct ways of tiling, it is allowed to print any. If it is impossible to tile the board using triminoes or the correct tiling, for which four symbols "a", "b", "c", "d" would be enough, doesn't exist, print "NO" (without quotes) in the first line.

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

Example input:
6 10
.w.wbw.wbw
wbwbw.w.w.
bw.wbwbwbw
w.wbw.wbwb
...wbw.w.w
..wbw.wbw.

Example output:
YES
.a.aaa.ccc
baccc.c.a.
ba.dddcbab
b.aaa.cbab
...bbb.b.b
..ccc.ddd.

Example input:
2 2
wb
bw

Example output:
NO

Editorial:
Game
Contest: Codeforces Round 483 (Div. 2) [Thanks, Botan Investments and Victor Shaburov!]
Difficulty rating: 800
Tags: sortings

Two players play a game.

Initially there are $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ written on the board. Each turn a player selects one number and erases it from the board. This continues until there is only one number left on the board, i. e. $$$n - 1$$$ turns are made. The first player makes the first move, then players alternate turns.

The first player wants to minimize the last number that would be left on the board, while the second player wants to maximize it.

You want to know what number will be left on the board after $$$n - 1$$$ turns if both players make optimal moves.

Input format:
The first line contains one integer $$$n$$$ ($$$1 \le n \le 1000$$$) — the number of numbers on the board.

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^6$$$).

Output format:
Print one number that will be left on the board.

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

Note:
In the first sample, the first player erases $$$3$$$ and the second erases $$$1$$$. $$$2$$$ is left on the board.

In the second sample, $$$2$$$ is left on the board regardless of the actions of the players.

Example input:
3
2 1 3

Example output:
2

Example input:
3
2 2 2

Example output:
2

Editorial:
First let's notice that the first player makes $$$\lceil \frac{n - 1}{2} \rceil$$$ turns and the second one makes $$$\lfloor \frac{n - 1}{2} \rfloor$$$.
So, if numbers are $$$1$$$-indexed and sorted, first player can make the answer not more than $$$(n - \lceil \frac{n - 1}{2} \rceil)$$$-th by deleting maximal number every time. The second can make it not less than $$$(\lfloor \frac{n - 1}{2} \rfloor + 1)$$$-th.
But $$$n - \lceil \frac{n - 1}{2} \rceil = \lfloor \frac{n - 1}{2} \rfloor + 1$$$, because $$$n - 1 = \lceil \frac{n - 1}{2} \rceil + \lfloor \frac{n - 1}{2} \rfloor$$$.
So the answer has minimal and maximal values, which are the same. So the answer is $$$(\lfloor \frac{n - 1}{2} \rfloor + 1)$$$-th number ascending.
Asymptotics is $$$O(n \cdot log(n)$$$ or $$$O(n^2)$$$
Solution
Minesweeper
Contest: Codeforces Round 483 (Div. 2) [Thanks, Botan Investments and Victor Shaburov!]
Difficulty rating: 1100
Tags: implementation

One day Alex decided to remember childhood when computers were not too powerful and lots of people played only default games. Alex enjoyed playing Minesweeper that time. He imagined that he saved world from bombs planted by terrorists, but he rarely won.

Alex has grown up since then, so he easily wins the most difficult levels. This quickly bored him, and he thought: what if the computer gave him invalid fields in the childhood and Alex could not win because of it?

He needs your help to check it.

A Minesweeper field is a rectangle $$$n \times m$$$, where each cell is either empty, or contains a digit from $$$1$$$ to $$$8$$$, or a bomb. The field is valid if for each cell:

- if there is a digit $$$k$$$ in the cell, then exactly $$$k$$$ neighboring cells have bombs.
- if the cell is empty, then all neighboring cells have no bombs.

Two cells are neighbors if they have a common side or a corner (i. e. a cell has at most $$$8$$$ neighboring cells).

Input format:
The first line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n, m \le 100$$$) — the sizes of the field.

The next $$$n$$$ lines contain the description of the field. Each line contains $$$m$$$ characters, each of them is "." (if this cell is empty), "*" (if there is bomb in this cell), or a digit from $$$1$$$ to $$$8$$$, inclusive.

Output format:
Print "YES", if the field is valid and "NO" otherwise.

You can choose the case (lower or upper) for each letter arbitrarily.

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

Note:
In the second example the answer is "NO" because, if the positions of the bombs are preserved, the first line of the field should be *2*1.

You can read more about Minesweeper in Wikipedia's article.

Example input:
3 3
111
1*1
111

Example output:
YES

Example input:
2 4
*.*.
1211

Example output:
NO

Editorial:
Let's make two-dimensional array $$$d[n][m]$$$. For each cell $$$i,j$$$ if it has bomb in it we add $$$1$$$ in $$$d[g][h]$$$ where $$$g,h$$$ is neighboring cell for $$$i,j$$$. Now $$$d[i][j]$$$ is a number of bombs in neighboring cells of $$$i,j$$$ and we can check validity of field according to the condition of the problem:
• If there is a number $$$k$$$ in the cell, then exacly $$$k$$$ of neighboring cells have bombs.
• Otherwise, if cell has no bomb, then neighboring cells have no bombs.
Solution
AB-Strings
Contest: Codeforces Round 500 (Div. 1) [based on EJOI]
Difficulty rating: 2800
Tags: constructive algorithms, strings

There are two strings s and t, consisting only of letters a and b. You can make the following operation several times: choose a prefix of s, a prefix of t and swap them. Prefixes can be empty, also a prefix can coincide with a whole string.

Your task is to find a sequence of operations after which one of the strings consists only of a letters and the other consists only of b letters. The number of operations should be minimized.

Input format:
The first line contains a string s (1 ≤ |s| ≤ 2·105).

The second line contains a string t (1 ≤ |t| ≤ 2·105).

Here |s| and |t| denote the lengths of s and t, respectively. It is guaranteed that at least one of the strings contains at least one a letter and at least one of the strings contains at least one b letter.

Output format:
The first line should contain a single integer n (0 ≤ n ≤ 5·105) — the number of operations.

Each of the next n lines should contain two space-separated integers ai, bi — the lengths of prefixes of s and t to swap, respectively.

If there are multiple possible solutions, you can print any of them. It's guaranteed that a solution with given constraints exists.

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

Note:
In the first example, you can solve the problem in two operations:

1. Swap the prefix of the first string with length 1 and the prefix of the second string with length 0. After this swap, you'll have strings ab and bbb.
2. Swap the prefix of the first string with length 1 and the prefix of the second string with length 3. After this swap, you'll have strings bbbb and a.

In the second example, the strings are already appropriate, so no operations are needed.

Example input:
bab
bb

Example output:
2
1 0
1 3

Example input:
bbbb
aaa

Example output:
0

Editorial:
The solution is basically like following:
Note that we can compress equal adjacent letters.
Now we can do a dynamic programming with params (first letter of s, length of s, first letter of t, length of t).
However, the amount of transactions and even states is too large. But we can write a slow, but surely correct solution, and examine the transactions, which are made in dp.
Basically, the most typical transaction is to just make a swap of first group in s with first group in t. However there special cases, like when the first letters are the same or when the lengths are very small.
Running a slow dynamic programming helps to get all the cases for the solution.
Formally, the correctness of this algorithm can be proven by induction and the large cases analyses, which we skip for clarity.
Another approach is to consider different first operations, and then go a greedy after it algorithm. See the second solution for the details. We don't prove it.
Ber Patio
Contest: 2016-2017 ACM-ICPC, NEERC, Southern Subregional Contest (Online Mirror, ACM-ICPC Rules, Teams Preferred)
Difficulty rating: 3100

Polycarp is a regular customer at the restaurant "Ber Patio". He likes having lunches there.

"Ber Patio" has special discount program for regular customers. A customer can collect bonuses and partially cover expenses in the restaurant.

Let's assume a customer currently has b bonuses and she has to pay r burles for a lunch. In this case the customer can use bonuses (1 bonus = 1 burle) to reduce the payment. She can cover at most half of the payment using bonuses. However, 1 bonus will be added to the customer's bonus balance per each 10 burles she paid.

Formally:

1. a customer can choose any number x of bonuses to use ($$0 \leq x \leq \min(b, \left\lfloor \frac{r}{2} \right\rfloor)$$)),
2. the customer's bonus balance is reduced by x,
3. the customer pays r - x burles,
4. the customer's bonus balance is increased by ⌊(r - x) / 10⌋ (i.e. integer division rounded down is used).

Initially, there are b bonuses on Polycarp's account. Polycarp is going to have a lunch in "Ber Patio" for the next n days. He estimated the values a1, a2, ..., an, where ai is the number of burles in a receipt for the i-th day. The sum over all receipts doesn't exceed 105 burles.

Write a program to find the minimum number of burles Polycarp has to spend and an optimal strategy to use bonuses.

Input format:
The first line contains two integer numbers n and b (1 ≤ n ≤ 5000, 0 ≤ b ≤ 105) — number of days and initial number of bonuses Polycarp has.

The second line contains the integer sequence a1, a2, ..., an (1 ≤ ai ≤ 1000), where ai is the amount of burles in the i-th day's receipt.

It is guaranteed that the sum of all receipts does not exceed 105 burles.

Output format:
On the first line, print the expected minimal number of burles to pay for all n receipts.

On the second line, print the sequence of integer numbers b1, b2, ..., bn, where bi is the number of bonuses to use on the i-th day. If there are multiple solutions, print any of them.

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

Example input:
3 21
12 75 52

Example output:
110
2 5 22

Example input:
3 39
58 64 33

Example output:
107
28 4 16

Editorial:
Delete Them
Contest: 2016-2017 ACM-ICPC, NEERC, Southern Subregional Contest (Online Mirror, ACM-ICPC Rules, Teams Preferred)
Difficulty rating: 1300
Tags: constructive algorithms, implementation

Polycarp is a beginner programmer. He is studying how to use a command line.

Polycarp faced the following problem. There are n files in a directory and he needs to delete some of them. Polycarp wants to run a single delete command with filename pattern as an argument. All the files to be deleted should match the pattern and all other files shouldn't match the pattern.

Polycarp doesn't know about an asterisk '*', the only special character he knows is a question mark '?' which matches any single character. All other characters in the pattern match themselves only.

Formally, a pattern matches a filename if and only if they have equal lengths and all characters in the corresponding positions are equal except when the character in the pattern is '?', in which case the corresponding filename character does not matter.

For example, the filename pattern "a?ba?":

- matches filenames "aabaa", "abba.", "a.ba9" and "a.ba.";
- does not match filenames "aaba", "abaab", "aabaaa" and "aabaa.".

Help Polycarp find a pattern which matches files to be deleted and only them or report if there is no such pattern.

Input format:
The first line of the input contains two integers n and m (1 ≤ m ≤ n ≤ 100) — the total number of files and the number of files to be deleted.

The following n lines contain filenames, single filename per line. All filenames are non-empty strings containing only lowercase English letters, digits and dots ('.'). The length of each filename doesn't exceed 100. It is guaranteed that all filenames are distinct.

The last line of the input contains m distinct integer numbers in ascending order a1, a2, ..., am (1 ≤ ai ≤ n) — indices of files to be deleted. All files are indexed from 1 to n in order of their appearance in the input.

Output format:
If the required pattern exists, print "Yes" in the first line of the output. The second line should contain the required pattern. If there are multiple solutions, print any of them.

If the required pattern doesn't exist, print the only line containing "No".

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

Example input:
3 2
ab
ac
cd
1 2

Example output:
Yes
a?

Example input:
5 3
test
tezt
test.
.est
tes.
1 4 5

Example output:
Yes
?es?

Editorial:
At first if not all of the filenames, which we need to delete, have equal length print "No" and end algorithm.
Then let's build the needed pattern from the left to the right. Let the current position in the pattern is i. Now we need to count the number of different letters in position i in all filenames which need to be deleted. If only 1 letter can be found in position i we need to add this letter to the pattern. In the other case we need to add symbol '?' to the pattern.
After we built pattern we need to iterate through all given filenames and find a list of the filenames which will be deleted if we will use pattern which we built. If this list equal to the list given in input the answer is 'Yes', else the answer is 'No'.