1337xyz1337xyz/codeforces-editorial-full-2026-07-16 huggingface dataset:
DZY Loves Chessboard
Contest: Codeforces Round 254 (Div. 2)
Difficulty rating: 1200
Tags: dfs and similar, implementation

DZY loves chessboard, and he enjoys playing with it.

He has a chessboard of n rows and m columns. Some cells of the chessboard are bad, others are good. For every good cell, DZY wants to put a chessman on it. Each chessman is either white or black. After putting all chessmen, DZY wants that no two chessmen with the same color are on two adjacent cells. Two cells are adjacent if and only if they share a common edge.

You task is to find any suitable placement of chessmen on the given chessboard.

Input format:
The first line contains two space-separated integers n and m (1 ≤ n, m ≤ 100).

Each of the next n lines contains a string of m characters: the j-th character of the i-th string is either "." or "-". A "." means that the corresponding cell (in the i-th row and the j-th column) is good, while a "-" means it is bad.

Output format:
Output must contain n lines, each line must contain a string of m characters. The j-th character of the i-th string should be either "W", "B" or "-". Character "W" means the chessman on the cell is white, "B" means it is black, "-" means the cell is a bad cell.

If multiple answers exist, print any of them. It is guaranteed that at least one answer exists.

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

Note:
In the first sample, DZY puts a single black chessman. Of course putting a white one is also OK.

In the second sample, all 4 cells are good. No two same chessmen share an edge in the sample output.

In the third sample, no good cells are adjacent. So you can just put 3 chessmen, no matter what their colors are.

Example input:
1 1
.

Example output:
B

Example input:
2 2
..
..

Example output:
BW
WB

Editorial:
DZY Loves Chemistry
Contest: Codeforces Round 254 (Div. 2)
Difficulty rating: 1400
Tags: dfs and similar, dsu, greedy

DZY loves chemistry, and he enjoys mixing chemicals.

DZY has n chemicals, and m pairs of them will react. He wants to pour these chemicals into a test tube, and he needs to pour them in one by one, in any order.

Let's consider the danger of a test tube. Danger of an empty test tube is 1. And every time when DZY pours a chemical, if there are already one or more chemicals in the test tube that can react with it, the danger of the test tube will be multiplied by 2. Otherwise the danger remains as it is.

Find the maximum possible danger after pouring all the chemicals one by one in optimal order.

Input format:
The first line contains two space-separated integers n and m $$( 1 \leq n \leq 50 ; \; 0 \leq m \leq \frac { n ( n - 1 ) } { 2 } )$$.

Each of the next m lines contains two space-separated integers xi and yi (1 ≤ xi < yi ≤ n). These integers mean that the chemical xi will react with the chemical yi. Each pair of chemicals will appear at most once in the input.

Consider all the chemicals numbered from 1 to n in some order.

Output format:
Print a single integer — the maximum possible danger.

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

Note:
In the first sample, there's only one way to pour, and the danger won't increase.

In the second sample, no matter we pour the 1st chemical first, or pour the 2nd chemical first, the answer is always 2.

In the third sample, there are four ways to achieve the maximum possible danger: 2-1-3, 2-3-1, 1-2-3 and 3-2-1 (that is the numbers of the chemicals in order of pouring).

Example input:
1 0

Example output:
1

Example input:
2 1
1 2

Example output:
2

Editorial:
Arya and Bran
Contest: Codeforces Round 428 (Div. 2)
Difficulty rating: 900
Tags: implementation

Bran and his older sister Arya are from the same house. Bran like candies so much, so Arya is going to give him some Candies.

At first, Arya and Bran have 0 Candies. There are n days, at the i-th day, Arya finds ai candies in a box, that is given by the Many-Faced God. Every day she can give Bran at most 8 of her candies. If she don't give him the candies at the same day, they are saved for her and she can give them to him later.

Your task is to find the minimum number of days Arya needs to give Bran k candies before the end of the n-th day. Formally, you need to output the minimum day index to the end of which k candies will be given out (the days are indexed from 1 to n).

Print -1 if she can't give him k candies during n given days.

Input format:
The first line contains two integers n and k (1 ≤ n ≤ 100, 1 ≤ k ≤ 10000).

The second line contains n integers a1, a2, a3, ..., an (1 ≤ ai ≤ 100).

Output format:
If it is impossible for Arya to give Bran k candies within n days, print -1.

Otherwise print a single integer — the minimum number of days Arya needs to give Bran k candies before the end of the n-th day.

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

Note:
In the first sample, Arya can give Bran 3 candies in 2 days.

In the second sample, Arya can give Bran 17 candies in 3 days, because she can give him at most 8 candies per day.

In the third sample, Arya can't give Bran 9 candies, because she can give him at most 8 candies per day and she must give him the candies within 1 day.

Example input:
2 3
1 2

Example output:
2

Example input:
3 17
10 10 10

Example output:
3

Editorial:
Let t be number of her candies. At i-th day , we increase t by ai ,then we give Bran min(8, t) . So we decrease k from this value. We will print the answer once k becomes smaller or equal to 0 . Or we will print  - 1 if it does’n happen after n days.
Game of the Rows
Contest: Codeforces Round 428 (Div. 2)
Difficulty rating: 1900
Tags: brute force, greedy, implementation

Daenerys Targaryen has an army consisting of k groups of soldiers, the i-th group contains ai soldiers. She wants to bring her army to the other side of the sea to get the Iron Throne. She has recently bought an airplane to carry her army through the sea. The airplane has n rows, each of them has 8 seats. We call two seats neighbor, if they are in the same row and in seats {1, 2}, {3, 4}, {4, 5}, {5, 6} or {7, 8}.

A row in the airplane

Daenerys Targaryen wants to place her army in the plane so that there are no two soldiers from different groups sitting on neighboring seats.

Your task is to determine if there is a possible arranging of her army in the airplane such that the condition above is satisfied.

Input format:
The first line contains two integers n and k (1 ≤ n ≤ 10000, 1 ≤ k ≤ 100) — the number of rows and the number of groups of soldiers, respectively.

The second line contains k integers a1, a2, a3, ..., ak (1 ≤ ai ≤ 10000), where ai denotes the number of soldiers in the i-th group.

It is guaranteed that a1 + a2 + ... + ak ≤ 8·n.

Output format:
If we can place the soldiers in the airplane print "YES" (without quotes). Otherwise print "NO" (without quotes).

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

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

Note:
In the first sample, Daenerys can place the soldiers like in the figure below:

In the second sample, there is no way to place the soldiers in the plane since the second group soldier will always have a seat neighboring to someone from the first group.

In the third example Daenerys can place the first group on seats (1, 2, 7, 8), and the second group an all the remaining seats.

In the fourth example she can place the first two groups on seats (1, 2) and (7, 8), the third group on seats (3), and the fourth group on seats (5, 6).

Example input:
2 2
5 8

Example output:
YES

Example input:
1 2
7 1

Example output:
NO

Editorial:
Use greedy solution. Consider a group with x ≥ 4 members, put 4 of them in seats [3, 6] of some row, and throw the row. Now we have x - 4 members in this group now. Continue till all of the seats in the range [3, 6] become full, continue with [1, 2] and [7, 8]. Now handle groups with size  ≤ 3.
For groups with size  = 3, allocate 4 seats in range [3, 6] or 4 seats in range [1, 2] or [7, 8].
For groups with size  = 2, allocate 2 seats in range [1, 2] or [7, 8] or 3 seats in range [3, 6]. If no seat found, divide this group and make it two groups with size 1.
Fill the other parts with groups with groups with size  = 1.
If in any part we ran out of seat, the answer is NO, YES otherwise.
Journey
Contest: Codeforces Round 428 (Div. 2)
Difficulty rating: 1500
Tags: dfs and similar, dp, graphs, probabilities, trees

There are n cities and n - 1 roads in the Seven Kingdoms, each road connects two cities and we can reach any city from any other by the roads.

Theon and Yara Greyjoy are on a horse in the first city, they are starting traveling through the roads. But the weather is foggy, so they can’t see where the horse brings them. When the horse reaches a city (including the first one), it goes to one of the cities connected to the current city. But it is a strange horse, it only goes to cities in which they weren't before. In each such city, the horse goes with equal probabilities and it stops when there are no such cities.

Let the length of each road be 1. The journey starts in the city 1. What is the expected length (expected value of length) of their journey? You can read about expected (average) value by the link https://en.wikipedia.org/wiki/Expected_value.

Input format:
The first line contains a single integer n (1 ≤ n ≤ 100000) — number of cities.

Then n - 1 lines follow. The i-th line of these lines contains two integers ui and vi (1 ≤ ui, vi ≤ n, ui ≠ vi) — the cities connected by the i-th road.

It is guaranteed that one can reach any city from any other by the roads.

Output format:
Print a number — the expected length of their journey. The journey starts in the city 1.

Your answer will be considered correct if its absolute or relative error does not exceed 10 - 6.

Namely: let's assume that your answer is a, and the answer of the jury is b. The checker program will consider your answer correct, if $$\frac{|a-b|}{\max(1,b)} \leq 10^{-6}$$.

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

Note:
In the first sample, their journey may end in cities 3 or 4 with equal probability. The distance to city 3 is 1 and to city 4 is 2, so the expected length is 1.5.

In the second sample, their journey may end in city 4 or 5. The distance to the both cities is 2, so the expected length is 2.

Example input:
4
1 2
1 3
2 4

Example output:
1.500000000000000

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

Example output:
2.000000000000000

Editorial:
Let the cities be vertices and roads be edges of a tree and vertex 1 be the root of the tree.
Let ans[i] be the answer for the i-th vertex (the expected value if they start their journey from that vertex and the horse doesn't go to it's parent). Now we can calculate ans[i] by knowing the answer for it’s children. Let v1, v2, …., vk be the children of i-th vertex , then $${ \it ans}[i]=\frac{{\it ans}[{v}_{1}]+{\it ans}[{v}_{2}]+\ldots+{\it ans}[{v}_{k}]}{k}+1$$ . Because when we are at i-th vertex , we have k choices with equal probabilities and  + 1 for going to one of them (length of the edge between i-th vertex and it’s children).
So if we know the answer of some vertex’s children, we can calculate its expected value and we can do it by a simple DFS (note that the answer for a leave is 0).
Integer Points
Contest: Codeforces Round 594 (Div. 2)
Difficulty rating: 1000
Tags: geometry, math

DLS and JLS are bored with a Math lesson. In order to entertain themselves, DLS took a sheet of paper and drew $$$n$$$ distinct lines, given by equations $$$y = x + p_i$$$ for some distinct $$$p_1, p_2, \ldots, p_n$$$.

Then JLS drew on the same paper sheet $$$m$$$ distinct lines given by equations $$$y = -x + q_i$$$ for some distinct $$$q_1, q_2, \ldots, q_m$$$.

DLS and JLS are interested in counting how many line pairs have integer intersection points, i.e. points with both coordinates that are integers. Unfortunately, the lesson will end up soon, so DLS and JLS are asking for your help.

Input format:
The first line contains one integer $$$t$$$ ($$$1 \le t \le 1000$$$), the number of test cases in the input. Then follow the test case descriptions.

The first line of a test case contains an integer $$$n$$$ ($$$1 \le n \le 10^5$$$), the number of lines drawn by DLS.

The second line of a test case contains $$$n$$$ distinct integers $$$p_i$$$ ($$$0 \le p_i \le 10^9$$$) describing the lines drawn by DLS. The integer $$$p_i$$$ describes a line given by the equation $$$y = x + p_i$$$.

The third line of a test case contains an integer $$$m$$$ ($$$1 \le m \le 10^5$$$), the number of lines drawn by JLS.

The fourth line of a test case contains $$$m$$$ distinct integers $$$q_i$$$ ($$$0 \le q_i \le 10^9$$$) describing the lines drawn by JLS. The integer $$$q_i$$$ describes a line given by the equation $$$y = -x + q_i$$$.

The sum of the values of $$$n$$$ over all test cases in the input does not exceed $$$10^5$$$. Similarly, the sum of the values of $$$m$$$ over all test cases in the input does not exceed $$$10^5$$$.

In hacks it is allowed to use only one test case in the input, so $$$t=1$$$ should be satisfied.

Output format:
For each test case in the input print a single integer — the number of line pairs with integer intersection points.

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

Note:
The picture shows the lines from the first test case of the example. Black circles denote intersection points with integer coordinates.

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

Example output:
3
1
0

Editorial:
Consider two lines $$$y = x + p$$$ и $$$y = -x + q$$$:
$$$\begin{cases} y = x + p \\ y = -x + q \end{cases} \Rightarrow \begin{cases} 2y = p + q \\ y = -x + q \end{cases} \Rightarrow \begin{cases} y = \frac{p + q}{2} \\ y = -x + q \end{cases} \Rightarrow \begin{cases} y = \frac{p + q}{2} \\ x = \frac{q - p}{2} \end{cases}$$$
It's clear that they will have integral intersection point iff $$$p$$$ and $$$q$$$ have the same parity. Let's find $$$p_0$$$ и $$$p_1$$$ — number of even and odd $$$p_i$$$ respectively. Moreover let's find $$$q_0$$$ and $$$q_1$$$ for $$$q_i$$$. Now answer is $$$p_0 \cdot q_0 + p_1 \cdot q_1$$$. Complexity: $$$O(n + m)$$$.
Pay attention that answer does not fit in 32-bit data type.
Jamie and Alarm Snooze
Contest: Codeforces Round 457 (Div. 2)
Difficulty rating: 900
Tags: brute force, implementation, math

Jamie loves sleeping. One day, he decides that he needs to wake up at exactly hh: mm. However, he hates waking up, so he wants to make waking up less painful by setting the alarm at a lucky time. He will then press the snooze button every x minutes until hh: mm is reached, and only then he will wake up. He wants to know what is the smallest number of times he needs to press the snooze button.

A time is considered lucky if it contains a digit '7'. For example, 13: 07 and 17: 27 are lucky, while 00: 48 and 21: 34 are not lucky.

Note that it is not necessary that the time set for the alarm and the wake-up time are on the same day. It is guaranteed that there is a lucky time Jamie can set so that he can wake at hh: mm.

Formally, find the smallest possible non-negative integer y such that the time representation of the time x·y minutes before hh: mm contains the digit '7'.

Jamie uses 24-hours clock, so after 23: 59 comes 00: 00.

Input format:
The first line contains a single integer x (1 ≤ x ≤ 60).

The second line contains two two-digit integers, hh and mm (00 ≤ hh ≤ 23, 00 ≤ mm ≤ 59).

Output format:
Print the minimum number of times he needs to press the button.

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

Note:
In the first sample, Jamie needs to wake up at 11:23. So, he can set his alarm at 11:17. He would press the snooze button when the alarm rings at 11:17 and at 11:20.

In the second sample, Jamie can set his alarm at exactly at 01:07 which is lucky.

Example input:
3
11 23

Example output:
2

Example input:
5
01 07

Example output:
0

Editorial:
Jamie and Binary Sequence (changed after round)
Contest: Codeforces Round 457 (Div. 2)
Difficulty rating: 2000
Tags: bitmasks, greedy, math

Jamie is preparing a Codeforces round. He has got an idea for a problem, but does not know how to solve it. Help him write a solution to the following problem:

Find k integers such that the sum of two to the power of each number equals to the number n and the largest integer in the answer is as small as possible. As there may be multiple answers, you are asked to output the lexicographically largest one.

To be more clear, consider all integer sequence with length k (a1, a2, ..., ak) with $$\sum_{i=1}^{k} 2^{a_i} = n$$. Give a value $$y = \max_{1 \leq i \leq k} a_i$$ to each sequence. Among all sequence(s) that have the minimum y value, output the one that is the lexicographically largest.

For definitions of powers and lexicographical order see notes.

Input format:
The first line consists of two integers n and k (1 ≤ n ≤ 1018, 1 ≤ k ≤ 105) — the required sum and the length of the sequence.

Output format:
Output "No" (without quotes) in a single line if there does not exist such sequence. Otherwise, output "Yes" (without quotes) in the first line, and k numbers separated by space in the second line — the required sequence.

It is guaranteed that the integers in the answer sequence fit the range [ - 1018, 1018].

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

Note:
Sample 1:

23 + 23 + 22 + 21 + 20 = 8 + 8 + 4 + 2 + 1 = 23

Answers like (3, 3, 2, 0, 1) or (0, 1, 2, 3, 3) are not lexicographically largest.

Answers like (4, 1, 1, 1, 0) do not have the minimum y value.

Sample 2:

It can be shown there does not exist a sequence with length 2.

Sample 3:

$$2^{-1} + 2^{-1} = \frac{1}{2} + \frac{1}{2} = 1$$

Powers of 2:

If x > 0, then 2x = 2·2·2·...·2 (x times).

If x = 0, then 2x = 1.

If x < 0, then $$2^x = \frac{1}{2^{-x}}$$.

Lexicographical order:

Given two different sequences of the same length, (a1, a2, ... , ak) and (b1, b2, ... , bk), the first one is smaller than the second one for the lexicographical order, if and only if ai < bi, for the first i where ai and bi differ.

Example input:
23 5

Example output:
Yes
3 3 2 1 0

Example input:
13 2

Example output:
No

Editorial:
Jamie and Interesting Graph
Contest: Codeforces Round 457 (Div. 2)
Difficulty rating: 1600
Tags: constructive algorithms, graphs, shortest paths

Jamie has recently found undirected weighted graphs with the following properties very interesting:

- The graph is connected and contains exactly n vertices and m edges.
- All edge weights are integers and are in range [1, 109] inclusive.
- The length of shortest path from 1 to n is a prime number.
- The sum of edges' weights in the minimum spanning tree (MST) of the graph is a prime number.
- The graph contains no loops or multi-edges.

If you are not familiar with some terms from the statement you can find definitions of them in notes section.

Help Jamie construct any graph with given number of vertices and edges that is interesting!

Input format:
First line of input contains 2 integers n, m $$( 2 \leq n \leq 10^{5}, n - 1 \leq m \leq min ( \frac { n ( n - 1 ) } { 2 }, 1 0 ^ { 5 } ) )$$ — the required number of vertices and edges.

Output format:
In the first line output 2 integers sp, mstw (1 ≤ sp, mstw ≤ 1014) — the length of the shortest path and the sum of edges' weights in the minimum spanning tree.

In the next m lines output the edges of the graph. In each line output 3 integers u, v, w (1 ≤ u, v ≤ n, 1 ≤ w ≤ 109) describing the edge connecting u and v and having weight w.

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

Note:
The graph of sample 1:  Shortest path sequence: {1, 2, 3, 4}. MST edges are marked with an asterisk (*).

Definition of terms used in the problem statement:

A shortest path in an undirected graph is a sequence of vertices (v1, v2, ... , vk) such that vi is adjacent to vi + 1 1 ≤ i < k and the sum of weight $$\sum_{i=1}^{n-1} w(v_i, v_{i+1})$$ is minimized where w(i, j) is the edge weight between i and j. (https://en.wikipedia.org/wiki/Shortest_path_problem)

A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself. (https://en.wikipedia.org/wiki/Prime_number)

A minimum spanning tree (MST) is a subset of the edges of a connected, edge-weighted undirected graph that connects all the vertices together, without any cycles and with the minimum possible total edge weight. (https://en.wikipedia.org/wiki/Minimum_spanning_tree)

https://en.wikipedia.org/wiki/Multiple_edges

Example input:
4 4

Example output:
7 7
1 2 3
2 3 2
3 4 2
2 4 4

Example input:
5 4

Example output:
7 13
1 2 2
1 3 4
1 4 3
4 5 4

Editorial:
Petya and Origami
Contest: Codeforces Round 524 (Div. 2)
Difficulty rating: 800
Tags: math

Petya is having a party soon, and he has decided to invite his $$$n$$$ friends.

He wants to make invitations in the form of origami. For each invitation, he needs two red sheets, five green sheets, and eight blue sheets. The store sells an infinite number of notebooks of each color, but each notebook consists of only one color with $$$k$$$ sheets. That is, each notebook contains $$$k$$$ sheets of either red, green, or blue.

Find the minimum number of notebooks that Petya needs to buy to invite all $$$n$$$ of his friends.

Input format:
The first line contains two integers $$$n$$$ and $$$k$$$ ($$$1\leq n, k\leq 10^8$$$) — the number of Petya's friends and the number of sheets in each notebook respectively.

Output format:
Print one number — the minimum number of notebooks that Petya needs to buy.

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

Note:
In the first example, we need $$$2$$$ red notebooks, $$$3$$$ green notebooks, and $$$5$$$ blue notebooks.

In the second example, we need $$$5$$$ red notebooks, $$$13$$$ green notebooks, and $$$20$$$ blue notebooks.

Example input:
3 5

Example output:
10

Example input:
15 6

Example output:
38

Editorial:
Let's calculate how many notebooks we need for each color separately, and the answer, obviously, will be their sum. We need $$$2 \cdot n$$$ red sheets, $$$5 \cdot n$$$ green sheets, and $$$8 \cdot n$$$ blue sheets. So we need $$$\lceil \frac {2n}{k} \rceil$$$ notebooks with red sheets, $$$\lceil \frac{5n}{k} \rceil$$$ and $$$\lceil \frac{8n}{k} \rceil$$$ notebooks with of green sheets and blue sheets, respectively.