1337xyz1337xyz/codeforces-editorial-full-2026-07-16 huggingface dataset:
Kitchen Utensils
Contest: Technocup 2019 - Elimination Round 3
Difficulty rating: 900

The king's birthday dinner was attended by $$$k$$$ guests. The dinner was quite a success: every person has eaten several dishes (though the number of dishes was the same for every person) and every dish was served alongside with a new set of kitchen utensils.

All types of utensils in the kingdom are numbered from $$$1$$$ to $$$100$$$. It is known that every set of utensils is the same and consist of different types of utensils, although every particular type may appear in the set at most once. For example, a valid set of utensils can be composed of one fork, one spoon and one knife.

After the dinner was over and the guests were dismissed, the king wondered what minimum possible number of utensils could be stolen. Unfortunately, the king has forgotten how many dishes have been served for every guest but he knows the list of all the utensils left after the dinner. Your task is to find the minimum possible number of stolen utensils.

Input format:
The first line contains two integer numbers $$$n$$$ and $$$k$$$ ($$$1 \le n \le 100, 1 \le k \le 100$$$)  — the number of kitchen utensils remaining after the dinner and the number of guests correspondingly.

The next line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 100$$$)  — the types of the utensils remaining. Equal values stand for identical utensils while different values stand for different utensils.

Output format:
Output a single value — the minimum number of utensils that could be stolen by the guests.

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

Note:
In the first example it is clear that at least one utensil of type $$$3$$$ has been stolen, since there are two guests and only one such utensil. But it is also possible that every person received only one dish and there were only six utensils in total, when every person got a set $$$(1, 2, 3)$$$ of utensils. Therefore, the answer is $$$1$$$.

One can show that in the second example at least $$$2$$$ dishes should have been served for every guest, so the number of utensils should be at least $$$24$$$: every set contains $$$4$$$ utensils and every one of the $$$3$$$ guests gets two such sets. Therefore, at least $$$14$$$ objects have been stolen. Please note that utensils of some types (for example, of types $$$2$$$ and $$$4$$$ in this example) may be not present in the set served for dishes.

Example input:
5 2
1 2 2 1 3

Example output:
1

Example input:
10 3
1 3 3 1 3 5 5 5 5 100

Example output:
14

Editorial:
Suppose we've found the minimum possible number $$$p$$$ of dishes served for each person. If the input contains utensils of $$$t$$$ types exactly, it's clear that the total number of utensils used is at least $$$p \cdot t \cdot k$$$ and the number of utensils stolen is at least $$$p \cdot t \cdot k - n$$$. Moreover, it's easy to construct an example with this exact number of stolen utensils having our $$$n$$$ objects served.
It is also easy to note that the minimum $$$p$$$ is equal to the ratio of the maximum number of utensils of one type and the number of guests, rounded up.
Personalized Cup
Contest: Technocup 2019 - Elimination Round 3
Difficulty rating: 1200

At many competitions that have a word «cup» in its official name the winner is presented with an actual cup. This time the organizers of one unusual programming competition have decided to please the winner even more and to add a nameplate to the cup with the handle of the winner.

The nameplate is to be rectangular and the text on it will be printed as a table of several rows and columns. Having some measurements done, the organizers have found out that the number $$$a$$$ of rows cannot be greater than $$$5$$$ while the number $$$b$$$ of columns cannot exceed $$$20$$$. Every cell of the table will contain either an asterisk («*») or a letter of user's handle.

Furthermore, the organizers want the rows of the table to be uniform, which means that the number of asterisks used in different rows should differ by at most one (i.e. you can't have two asterisks in the first row and none in the second). The main goal, however, is to obtain the winner's handle precisely when reading the table from top to bottom and from left to right in every row (skipping asterisks).

The organizers want for the nameplate to have as few rows as possible and among all valid tables with the minimum number of rows they want to choose the one that has the minimum number of columns.

The winner is not yet determined so your task is to write a program that, given a certain handle, generates the necessary table.

Input format:
The only line contains one string $$$s$$$ ($$$1 \le |s| \le 100$$$), comprised of uppercase and lowercase Latin letters,  — the handle of the winner.

Output format:
In the first line output the minimum number $$$a$$$ of rows in the table and the minimum number $$$b$$$ of columns in an optimal table with rows.

The following $$$a$$$ lines should contain $$$b$$$ characters each  — any valid table.

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

Example input:
tourist

Example output:
1 7
tourist

Example input:
MyNameIsLifeIAmForeverByYourSideMyNameIsLife

Example output:
3 15
MyNameIsLifeIAm
ForeverByYourSi
deMyNameIsL*ife

Editorial:
Let's iterate over all possible pairs $$$(a, b)$$$ with $$$1 \leq a \leq 5$$$ and $$$1 \leq b \leq 20$$$ to find the optimal one satisfying the inequality $$$a \cdot b \geq |s|$$$. So now we need to place the characters of $$$s$$$ in the same relative order through the table. Possibly, several cells will remain unused, but we will distribute them over the table and place at most one asterisk in every row.
One can show that we will have at most one asterisk in each row, because otherwise we would have been able to reduce the value of $$$b$$$.
Playing Piano
Contest: Technocup 2019 - Elimination Round 3
Difficulty rating: 1700
Tags: constructive algorithms, dp

Little Paul wants to learn how to play piano. He already has a melody he wants to start with. For simplicity he represented this melody as a sequence $$$a_1, a_2, \ldots, a_n$$$ of key numbers: the more a number is, the closer it is to the right end of the piano keyboard.

Paul is very clever and knows that the essential thing is to properly assign fingers to notes he's going to play. If he chooses an inconvenient fingering, he will then waste a lot of time trying to learn how to play the melody by these fingers and he will probably not succeed.

Let's denote the fingers of hand by numbers from $$$1$$$ to $$$5$$$. We call a fingering any sequence $$$b_1, \ldots, b_n$$$ of fingers numbers. A fingering is convenient if for all $$$1\leq i \leq n - 1$$$ the following holds:

- if $$$a_i < a_{i+1}$$$ then $$$b_i < b_{i+1}$$$, because otherwise Paul needs to take his hand off the keyboard to play the $$$(i+1)$$$-st note;
- if $$$a_i > a_{i+1}$$$ then $$$b_i > b_{i+1}$$$, because of the same;
- if $$$a_i = a_{i+1}$$$ then $$$b_i\neq b_{i+1}$$$, because using the same finger twice in a row is dumb. Please note that there is $$$\neq$$$, not $$$=$$$ between $$$b_i$$$ and $$$b_{i+1}$$$.

Please provide any convenient fingering or find out that there is none.

Input format:
The first line contains a single integer $$$n$$$ ($$$1 \le n \le 10^5$$$) denoting the number of notes.

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 2\cdot10^5$$$) denoting the positions of notes on the keyboard.

Output format:
If there is no convenient fingering, print $$$-1$$$. Otherwise, print $$$n$$$ numbers $$$b_1, b_2, \ldots, b_n$$$, each from $$$1$$$ to $$$5$$$, denoting a convenient fingering, separated by spaces.

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

Note:
The third sample test is kinda "Non stop" song by Reflex.

Example input:
5
1 1 4 2 2

Example output:
1 4 5 4 5

Example input:
7
1 5 7 8 10 3 1

Example output:
1 2 3 4 5 4 3

Editorial:
Let $$$dp[i][j]$$$ be $$$-1$$$ if we cannot play the first $$$i$$$ notes in such a way that the $$$i$$$-th note is played by the $$$j$$$-th finger, otherwise let this be the number of the previous finger in any of possible fingerings. This $$$dp$$$ can be easily calculated for about $$$5n\cdot 5$$$ operations.
Barcelonian Distance
Contest: Technocup 2019 - Elimination Round 3
Difficulty rating: 1900
Tags: geometry, implementation

In this problem we consider a very simplified model of Barcelona city.

Barcelona can be represented as a plane with streets of kind $$$x = c$$$ and $$$y = c$$$ for every integer $$$c$$$ (that is, the rectangular grid). However, there is a detail which makes Barcelona different from Manhattan. There is an avenue called Avinguda Diagonal which can be represented as a the set of points $$$(x, y)$$$ for which $$$ax + by + c = 0$$$.

One can walk along streets, including the avenue. You are given two integer points $$$A$$$ and $$$B$$$ somewhere in Barcelona. Find the minimal possible distance one needs to travel to get to $$$B$$$ from $$$A$$$.

Input format:
The first line contains three integers $$$a$$$, $$$b$$$ and $$$c$$$ ($$$-10^9\leq a, b, c\leq 10^9$$$, at least one of $$$a$$$ and $$$b$$$ is not zero) representing the Diagonal Avenue.

The next line contains four integers $$$x_1$$$, $$$y_1$$$, $$$x_2$$$ and $$$y_2$$$ ($$$-10^9\leq x_1, y_1, x_2, y_2\leq 10^9$$$) denoting the points $$$A = (x_1, y_1)$$$ and $$$B = (x_2, y_2)$$$.

Output format:
Find the minimum possible travel distance between $$$A$$$ and $$$B$$$. Your answer is considered correct if its absolute or relative error does not exceed $$$10^{-6}$$$.

Formally, let your answer be $$$a$$$, and the jury's answer be $$$b$$$. Your answer is accepted if and only if $$$\frac{|a - b|}{\max{(1, |b|)}} \le 10^{-6}$$$.

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

Note:
The first example is shown on the left picture while the second example us shown on the right picture below. The avenue is shown with blue, the origin is shown with the black dot.

Example input:
1 1 -3
0 3 3 0

Example output:
4.2426406871

Example input:
3 1 -9
0 3 3 -1

Example output:
6.1622776602

Editorial:
One way is to handle some cases: intersect the line with the border of the bounding box of $$$(x_1, y_1)$$$ and $$$(x_2, y_2)$$$, and relax answer by some values depending on the mutual location of intersection points, as on the pics below. Another way is to intersect horizontal and vertical lines through $$$(x_1, y_1)$$$ and $$$(x_2, y_2)$$$, intersect them with the $$$ax + by + c = 0$$$ line, consider the obtained 6 points as vertices of a graph, add all horizontal and vertical edges in this graph, run Floyd/Ford-Bellman/Dijkstra algorithm.
Vasya and Maximum Matching
Contest: Technocup 2019 - Elimination Round 3
Difficulty rating: 2400
Tags: dp, trees

Vasya has got a tree consisting of $$$n$$$ vertices. He wants to delete some (possibly zero) edges in this tree such that the maximum matching in the resulting graph is unique. He asks you to calculate the number of ways to choose a set of edges to remove.

A matching in the graph is a subset of its edges such that there is no vertex incident to two (or more) edges from the subset. A maximum matching is a matching such that the number of edges in the subset is maximum possible among all matchings in this graph.

Since the answer may be large, output it modulo $$$998244353$$$.

Input format:
The first line contains one integer $$$n$$$ ($$$1 \le n \le 3 \cdot 10^5$$$) — the number of vertices in the tree.

Each of the next $$$n − 1$$$ lines contains two integers $$$u$$$ and $$$v$$$ ($$$1 \le u, v \le n, u \neq v$$$) denoting an edge between vertex $$$u$$$ and vertex $$$v$$$. It is guaranteed that these edges form a tree.

Output format:
Print one integer — the number of ways to delete some (possibly empty) subset of edges so that the maximum matching in the resulting graph is unique. Print the answer modulo $$$998244353$$$.

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

Note:
Possible ways to delete edges in the first example:

- delete $$$(1, 2)$$$ and $$$(1, 3)$$$.
- delete $$$(1, 2)$$$ and $$$(1, 4)$$$.
- delete $$$(1, 3)$$$ and $$$(1, 4)$$$.
- delete all edges.

Possible ways to delete edges in the second example:

- delete no edges.
- delete $$$(1, 2)$$$ and $$$(2, 3)$$$.
- delete $$$(1, 2)$$$ and $$$(3, 4)$$$.
- delete $$$(2, 3)$$$ and $$$(3, 4)$$$.
- delete $$$(2, 3)$$$.
- delete all edges.

Example input:
4
1 2
1 3
1 4

Example output:
4

Example input:
4
1 2
2 3
3 4

Example output:
6

Editorial:
Firstly let's understand when the maximum matching in the tree is unique — and it is unique if and only if it's perfect (i. e. every vertex having at least one incident edge is saturated). So the problem is reduced to counting the number of ways to split the tree so that each component having size $$$2$$$ or more has a perfect matching.
Let's use dynamic programming to do this. Let $$$dp_{v,0 \dots 2}$$$ be the number of ways to delete edges in the subtree of $$$v$$$ so that in this subtree every component is valid (if its size is more than $$$1$$$, then it has a perfect matching). The second parameter can take one of three values:
$$$dp_{v,0}$$$ — $$$v$$$ can be used for the matching (but it's not necessary to do it).
$$$dp_{v,1}$$$ — $$$v$$$ is already used in the matching.
$$$dp_{v,2}$$$ — $$$v$$$ is not used in the matching yet, but we have to match it to some vertex.
Then
$$$dp_{v, 0} = \prod\limits_{to}{dp_{to, 0}} + \sum\limits_{to} (dp_{to, 1} \cdot \prod\limits_{to', to' \ne to}(dp_{to', 0} + dp_{to', 2}) )$$$,
$$$dp_{v, 1} = \prod\limits_{to}(dp_{to, 0} + dp_{to, 2})$$$,
$$$dp_{v, 2} = \sum\limits_{to} (dp_{to, 1} \cdot \prod\limits_{to', to' \ne to}(dp_{to', 0} + dp_{to', 2}) )$$$,
where $$$to$$$ and $$$to'$$$ are children of $$$v$$$.
Chattering
Contest: Technocup 2019 - Elimination Round 3
Difficulty rating: 2900

There are $$$n$$$ parrots standing in a circle. Each parrot has a certain level of respect among other parrots, namely $$$r_i$$$. When a parrot with respect level $$$x$$$ starts chattering, $$$x$$$ neighbours to the right and to the left of it start repeating the same words in 1 second. Their neighbours then start repeating as well, and so on, until all the birds begin to chatter.

You are given the respect levels of all parrots. For each parrot answer a question: if this certain parrot starts chattering, how many seconds will pass until all other birds will start repeating it?

Input format:
In the first line of input there is a single integer $$$n$$$, the number of parrots ($$$1 \leq n \leq 10^5$$$).

In the next line of input there are $$$n$$$ integers $$$r_1$$$, ..., $$$r_n$$$, the respect levels of parrots in order they stand in the circle ($$$1 \leq r_i \leq n$$$).

Output format:
Print $$$n$$$ integers. $$$i$$$-th of them should equal the number of seconds that is needed for all parrots to start chattering if the $$$i$$$-th parrot is the first to start.

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

Example input:
4
1 1 4 1

Example output:
2 2 1 2

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

Example output:
3 3 2 2 1 2 2 3

Editorial:
Let us for a moment think that parrots stand in a line. We want to compute a series of values $$$r_{i, k}$$$ and $$$l_{i, k}$$$. $$$l_{i, k}$$$ is the index of the leftmost parrot that will chatter in $$$2^k$$$ seconds after the $$$i$$$-th parrot starts chattering. $$$r_{i, k}$$$ is defined similarly. Clearly, $$$l_{i, 0} = i - a_i$$$ and $$$r_{i, 0} = i + a_i$$$.
We calculate $$$l_{i, k}$$$ using the values with lesser $$$k$$$. Precisely, $$$l_{i, k} = \min l_{t, k-1}$$$, where $$$t$$$ goes in range $$$[l_{i, k-1}, r_{i, k-1}]$$$. Explanation: the $$$i$$$-th parrot triggered some $$$t$$$-th parrot in $$$2^{k-1}$$$ seconds, then the $$$t$$$-th parrot triggered some other parrot in next $$$2^{k-1}$$$ seconds. Thus we want to find such $$$t$$$ that the leftmost parrot triggered by $$$t$$$ is minimum possible.
We use a segment tree or a sparse table on the values of the $$$(k-1)$$$-th level to compute the value of the DP on the $$$k$$$-th level.
The idea for the solution on a circle is essentially the same, but you must consider segments more carefully. One rather simple way to do it is to duplicate all the parrots, now numbering them $$$\dots, -2, -1, 0, 1, \dots, n-1, n, n+1, \dots$$$ such that the numbers with the same remainder modulo $$$n$$$ denote the same parrot. Then we can bound the values for $$$l_{i, k}$$$ and $$$r_{i, k}$$$ between $$$-n$$$ and $$$2n$$$. Now a range query over a circle transforms to a constant number of range queries over a segment.
Time complexity: $$$O(n \log^2 n)$$$.
Factorial
Contest: Unknown Language Round 1
Difficulty rating: 1300
Tags: *special, implementation

Print the factorial of the given integer number n. The factorial of n is equal to 1·2·...·n.

Input format:
The only line contains n (1 ≤ n ≤ 10).

Output format:
Print the factorial of n.

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

Example input:
3

Example output:
6

Example input:
5

Example output:
120

Editorial:
Expression
Contest: Unknown Language Round 1
Difficulty rating: 1500
Tags: *special, expression parsing

You are given a line «n#m», where «n» and «m» are digits, and «#» is a sign «+» or «-». Print the value of the given expression.

Input format:
The only given line has a string in form «n#m», where «n» and «m» are digits (from 0 to 9), and «#» is a sign «+» or «-».

Output format:
Print the value of the given expression.

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

Example input:
1-5

Example output:
-4

Editorial:
Table
Contest: Unknown Language Round 1
Difficulty rating: 1600
Tags: *special, greedy, implementation, math

The integer numbers from 1 to nm was put into rectangular table having n rows and m columns. The numbers was put from left to right, from top to bottom, i.e. the first row contains integers 1, 2, ..., m, the second — m + 1, m + 2, ..., 2 * m and so on.

After it these numbers was written on the paper in another order: from top to bottom, from left to right. First, the numbers in the first column was written (from top to bottom) and so on.

Print the k-th number on the paper.

Input format:
The only line in the input contains three integer numbers n, m and k (1 ≤ n, m ≤ 20000, 1 ≤ k ≤ nm).

Output format:
Print the required number.

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

Example input:
3 4 11

Example output:
8

Example input:
20000 10000 200000000

Example output:
200000000

Editorial:
Presents
Contest: Unknown Language Round 1
Difficulty rating: 1800
Tags: *special, greedy

You are given the prices of three presents. Also there are three sisters. It is known that the most valuable present is for the eldest sister. The second (by price) is for the second sister. And the less valuable present is for the youngest sister. If two (or three) presents have the same price, corresponding sisters may get the in a random way.

Input format:
The only line contains three integer numbers a1, a2, a3 (1 ≤ a1, a2, a3 ≤ 100) — the prices of the presents.

Output format:
Print three numbers i1, i2, i3 (1 ≤ i1, i2, i3 ≤ 3), all of them should be distinct. The first number stands for the seniority of the sister which will get the first present (1 stands for the eldest, 3 for the youngest). The second and third numbers mean the seniority of the sisters which get the second and the third present respectively.

If there are multiple answers, print any of them.

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

Note:
In the second sample another possible answer is "2 3 1".

Example input:
11 13 1

Example output:
2 1 3

Example input:
30 10 30

Example output:
1 3 2

Editorial:
Prime Segment
Contest: Unknown Language Round 1
Difficulty rating: 1800
Tags: *special, brute force, math, number theory

Positive integer number x is called prime, if it has exactly two positive integer divisors. For example, 2, 3, 17, 97 are primes, but 1, 10, 120 are not.

You are given an integer number n, find the shortest segment [a, b], which contains n (i.e. a ≤ n ≤ b) and a, b are primes.

Input format:
The only given line contains an integer number n (2 ≤ n ≤ 10000).

Output format:
Print the space separated pair of the required numbers a, b.

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

Example input:
10

Example output:
7 11

Example input:
97

Example output:
97 97

Editorial:
Domain
Contest: Unknown Language Round 1
Difficulty rating: 2000
Tags: *special, expression parsing

This problem doesn't contain real-world specifications about domains, just use the problem statement as a formal document to solve the problem.

The given string s is a domain name if it contains the characters "a"-"z", "0"-"9" and dots. No two dots shoud follow one after another (consecutive). The dots split the given string s into the parts, the last (most right) part should have the length 2 or 3. Domain can't start or end with a dot.

You are given the string s, check if it is domain name.

Input format:
The only line of the input contains given string s. The string may contain any characters with ASCII codes from 33 to 127, inclusive. The string length is between 1 and 100, inclusive.

Output format:
Print "YES" if the given string s is a domain name, or print "NO" if it is not.

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

Example input:
codeforces.com

Example output:
YES

Example input:
mail.v-kontakte.ru

Example output:
NO

Editorial:
Path Canonization
Contest: Unknown Language Round 1
Difficulty rating: 2200
Tags: *special

A path in some Unix-similar file system is given. The path consists of elements separated with characters "/". For example: "/usr/share/mysql/../tomcat6/conf/server.xml". The path starts with the root directory (i.e. starts with the character "/"). Each element means a name of file or directory, or it is one of two special elements: "." или "..". First of them stands for the current directory (for example, path "/./usr/././share" is equal to "/usr/share"). The second element ".." stands for the moving to the parent directory (for example, path "/usr/share/../lib" is equal to "/usr/lib").

You task is to convert the given path to such a path, which doesn't contain special elements "." and/or "..". If it is impossible, print "-1". The only reason for it is an attempt to move to the parent directory from the root.

Input format:
The only line contains the given path. The path starts with "/" and consists of elements separated with "/". No two "/" follow one after another (consecutively). The only path which can end with "/" is the root directory path equal to "/".

Each element may contain "a"-"z", "0"-"9" and dots. Any element different from specials "." and ".." contains at least one character different from the dots.

The path length is between 1 and 1000 inclusively.

Output format:
Print the required path or "-1".

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

Example input:
/usr/share/mysql/../tomcat6/conf/server.xml

Example output:
/usr/share/tomcat6/conf/server.xml

Example input:
/a/./././..

Example output:
/

Editorial: