1337xyz1337xyz/codeforces-editorial-full-2026-07-16 huggingface dataset:
Ehab's Last Corollary
Contest: Codeforces Round 649 (Div. 2)
Difficulty rating: 2100
Tags: constructive algorithms, dfs and similar, graphs, greedy, implementation, trees

Given a connected undirected graph with $$$n$$$ vertices and an integer $$$k$$$, you have to either:

- either find an independent set that has exactly $$$\lceil\frac{k}{2}\rceil$$$ vertices.
- or find a simple cycle of length at most $$$k$$$.

An independent set is a set of vertices such that no two of them are connected by an edge. A simple cycle is a cycle that doesn't contain any vertex twice.

I have a proof that for any input you can always solve at least one of these problems, but it's left as an exercise for the reader.

Input format:
The first line contains three integers $$$n$$$, $$$m$$$, and $$$k$$$ ($$$3 \le k \le n \le 10^5$$$, $$$n-1 \le m \le 2 \cdot 10^5$$$) — the number of vertices and edges in the graph, and the parameter $$$k$$$ from the statement.

Each of the next $$$m$$$ lines contains two integers $$$u$$$ and $$$v$$$ ($$$1 \le u,v \le n$$$) that mean there's an edge between vertices $$$u$$$ and $$$v$$$. It's guaranteed that the graph is connected and doesn't contain any self-loops or multiple edges.

Output format:
If you choose to solve the first problem, then on the first line print $$$1$$$, followed by a line containing $$$\lceil\frac{k}{2}\rceil$$$ distinct integers not exceeding $$$n$$$, the vertices in the desired independent set.

If you, however, choose to solve the second problem, then on the first line print $$$2$$$, followed by a line containing one integer, $$$c$$$, representing the length of the found cycle, followed by a line containing $$$c$$$ distinct integers not exceeding $$$n$$$, the vertices in the desired cycle, in the order they appear in the cycle.

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

Note:
In the first sample:

Notice that printing the independent set $$$\{2,4\}$$$ is also OK, but printing the cycle $$$1-2-3-4$$$ isn't, because its length must be at most $$$3$$$.

In the second sample:

Notice that printing the independent set $$$\{1,3\}$$$ or printing the cycle $$$2-1-4$$$ is also OK.

In the third sample:

In the fourth sample:

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

Example output:
1
1 3

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

Example output:
2
3
2 3 4

Editorial:
X-OR
Contest: Codeforces Round 649 (Div. 2)
Difficulty rating: 2700
Tags: bitmasks, constructive algorithms, divide and conquer, interactive, probabilities

This is an interactive problem!

Ehab has a hidden permutation $$$p$$$ of length $$$n$$$ consisting of the elements from $$$0$$$ to $$$n-1$$$. You, for some reason, want to figure out the permutation. To do that, you can give Ehab $$$2$$$ different indices $$$i$$$ and $$$j$$$, and he'll reply with $$$(p_i|p_j)$$$ where $$$|$$$ is the bitwise-or operation.

Ehab has just enough free time to answer $$$4269$$$ questions, and while he's OK with answering that many questions, he's too lazy to play your silly games, so he'll fix the permutation beforehand and will not change it depending on your queries. Can you guess the permutation?

Input format:
The only line contains the integer $$$n$$$ $$$(3 \le n \le 2048)$$$ — the length of the permutation.

Interaction format:
To ask a question, print "? $$$i$$$ $$$j$$$" (without quotes, $$$i \neq j$$$) Then, you should read the answer, which will be $$$(p_i|p_j)$$$.

If we answer with $$$-1$$$ instead of a valid answer, that means you exceeded the number of queries or made an invalid query.

Exit immediately after receiving $$$-1$$$ and you will see wrong answer verdict. Otherwise, you can get an arbitrary verdict because your solution will continue to read from a closed stream.

To print the answer, print "! $$$p_1$$$ $$$p_2$$$ $$$\ldots$$$ $$$p_n$$$" (without quotes). Note that answering doesn't count as one of the $$$4269$$$ queries.

After printing a query or printing the answer, do not forget to output end of line and flush the output. Otherwise, you will get idleness limit exceeded. To do this, use:

- fflush(stdout) or cout.flush() in C++;
- System.out.flush() in Java;
- flush(output) in Pascal;
- stdout.flush() in Python;
- See the documentation for other languages.

Hacks:

The first line should contain the integer $$$n$$$ ($$$3 \le n \le 2^{11}$$$) — the length of the permutation $$$p$$$.

The second line should contain $$$n$$$ space-separated integers $$$p_1$$$, $$$p_2$$$, $$$\ldots$$$, $$$p_n$$$ ($$$0 \le p_i < n$$$) — the elements of the permutation $$$p$$$.

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

Note:
In the first sample, the permutation is $$$[1,0,2]$$$. You start by asking about $$$p_1|p_2$$$ and Ehab replies with $$$1$$$. You then ask about $$$p_1|p_3$$$ and Ehab replies with $$$3$$$. Finally, you ask about $$$p_2|p_3$$$ and Ehab replies with $$$2$$$. You then guess the permutation.

Example input:
3
1
3
2

Example output:
? 1 2
? 1 3
? 2 3
! 1 0 2

Editorial:
Lunch Rush
Contest: Codeforces Round 169 (Div. 2)
Difficulty rating: 900
Tags: implementation

Having written another programming contest, three Rabbits decided to grab some lunch. The coach gave the team exactly k time units for the lunch break.

The Rabbits have a list of n restaurants to lunch in: the i-th restaurant is characterized by two integers fi and ti. Value ti shows the time the Rabbits need to lunch in the i-th restaurant. If time ti exceeds the time k that the coach has given for the lunch break, then the Rabbits' joy from lunching in this restaurant will equal fi - (ti - k). Otherwise, the Rabbits get exactly fi units of joy.

Your task is to find the value of the maximum joy the Rabbits can get from the lunch, depending on the restaurant. The Rabbits must choose exactly one restaurant to lunch in. Note that the joy value isn't necessarily a positive value.

Input format:
The first line contains two space-separated integers — n (1 ≤ n ≤ 104) and k (1 ≤ k ≤ 109) — the number of restaurants in the Rabbits' list and the time the coach has given them to lunch, correspondingly. Each of the next n lines contains two space-separated integers — fi (1 ≤ fi ≤ 109) and ti (1 ≤ ti ≤ 109) — the characteristics of the i-th restaurant.

Output format:
In a single line print a single integer — the maximum joy value that the Rabbits will get from the lunch.

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

Example input:
2 5
3 3
4 5

Example output:
4

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

Example output:
3

Editorial:
Little Girl and Game
Contest: Codeforces Round 169 (Div. 2)
Difficulty rating: 1300
Tags: games, greedy

The Little Girl loves problems on games very much. Here's one of them.

Two players have got a string s, consisting of lowercase English letters. They play a game that is described by the following rules:

- The players move in turns; In one move the player can remove an arbitrary letter from string s.
- If the player before his turn can reorder the letters in string s so as to get a palindrome, this player wins. A palindrome is a string that reads the same both ways (from left to right, and vice versa). For example, string "abba" is a palindrome and string "abc" isn't.

Determine which player will win, provided that both sides play optimally well — the one who moves first or the one who moves second.

Input format:
The input contains a single line, containing string s (1 ≤ |s|  ≤  103). String s consists of lowercase English letters.

Output format:
In a single line print word "First" if the first player wins (provided that both players play optimally well). Otherwise, print word "Second". Print the words without the quotes.

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

Example input:
aba

Example output:
First

Example input:
abca

Example output:
Second

Editorial:
Little Girl and Maximum Sum
Contest: Codeforces Round 169 (Div. 2)
Difficulty rating: 1500
Tags: data structures, greedy, implementation, sortings

The little girl loves the problems on array queries very much.

One day she came across a rather well-known problem: you've got an array of $$$n$$$ elements (the elements of the array are indexed starting from 1); also, there are $$$q$$$ queries, each one is defined by a pair of integers $$$l_i$$$, $$$r_i$$$ $$$(1 \le l_i \le r_i \le n)$$$. You need to find for each query the sum of elements of the array with indexes from $$$l_i$$$ to $$$r_i$$$, inclusive.

The little girl found the problem rather boring. She decided to reorder the array elements before replying to the queries in a way that makes the sum of query replies maximum possible. Your task is to find the value of this maximum sum.

Input format:
The first line contains two space-separated integers $$$n$$$ ($$$1 \le n \le 2\cdot10^5$$$) and $$$q$$$ ($$$1 \le q \le 2\cdot10^5$$$) — the number of elements in the array and the number of queries, correspondingly.

The next line contains $$$n$$$ space-separated integers $$$a_i$$$ ($$$1 \le a_i \le 2\cdot10^5$$$) — the array elements.

Each of the following $$$q$$$ lines contains two space-separated integers $$$l_i$$$ and $$$r_i$$$ ($$$1 \le l_i \le r_i \le n$$$) — the $$$i$$$-th query.

Output format:
In a single line print, a single integer — the maximum sum of query replies after the array elements are reordered.

Please, do not use the %lld specifier to read or write 64-bit integers in C++. It is preferred to use the cin, cout streams or the %I64d specifier.

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

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

Example output:
25

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

Example output:
33

Editorial:
Little Girl and Maximum XOR
Contest: Codeforces Round 169 (Div. 2)
Difficulty rating: 1700
Tags: bitmasks, dp, greedy, implementation, math

A little girl loves problems on bitwise operations very much. Here's one of them.

You are given two integers l and r. Let's consider the values of $$a \oplus b$$ for all pairs of integers a and b (l ≤ a ≤ b ≤ r). Your task is to find the maximum value among all considered ones.

Expression $$x \oplus y$$ means applying bitwise excluding or operation to integers x and y. The given operation exists in all modern programming languages, for example, in languages C++ and Java it is represented as "^", in Pascal — as "xor".

Input format:
The single line contains space-separated integers l and r (1 ≤ l ≤ r ≤ 1018).

Please, do not use the %lld specifier to read or write 64-bit integers in C++. It is preferred to use the cin, cout streams or the %I64d specifier.

Output format:
In a single line print a single integer — the maximum value of $$a \oplus b$$ for all pairs of integers a, b (l ≤ a ≤ b ≤ r).

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

Example input:
1 2

Example output:
3

Example input:
8 16

Example output:
31

Editorial:
Little Girl and Problem on Trees
Contest: Codeforces Round 169 (Div. 2)
Difficulty rating: 2100
Tags: data structures, graphs, trees

A little girl loves problems on trees very much. Here's one of them.

A tree is an undirected connected graph, not containing cycles. The degree of node x in the tree is the number of nodes y of the tree, such that each of them is connected with node x by some edge of the tree.

Let's consider a tree that consists of n nodes. We'll consider the tree's nodes indexed from 1 to n. The cosidered tree has the following property: each node except for node number 1 has the degree of at most 2.

Initially, each node of the tree contains number 0. Your task is to quickly process the requests of two types:

- Request of form: 0 v x d. In reply to the request you should add x to all numbers that are written in the nodes that are located at the distance of at most d from node v. The distance between two nodes is the number of edges on the shortest path between them.
- Request of form: 1 v. In reply to the request you should print the current number that is written in node v.

Input format:
The first line contains integers n (2 ≤ n ≤ 105) and q (1 ≤ q ≤ 105) — the number of tree nodes and the number of requests, correspondingly.

Each of the next n  -  1 lines contains two integers ui and vi (1 ≤ ui, vi ≤ n, ui ≠ vi), that show that there is an edge between nodes ui and vi. Each edge's description occurs in the input exactly once. It is guaranteed that the given graph is a tree that has the property that is described in the statement.

Next q lines describe the requests.

- The request to add has the following format: 0 v x d (1 ≤ v ≤ n, 1 ≤ x ≤ 104, 1 ≤ d < n).
- The request to print the node value has the following format: 1 v (1 ≤ v ≤ n).

The numbers in the lines are separated by single spaces.

Output format:
For each request to print the node value print an integer — the reply to the request.

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

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

Example output:
9
9
6

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

Example output:
11
17
11
16
17
11

Editorial:
Rectangle Cutting
Contest: Codeforces Round 924 (Div. 2)
Difficulty rating: 800
Tags: geometry, math

Bob has a rectangle of size $$$a \times b$$$. He tries to cut this rectangle into two rectangles with integer sides by making a cut parallel to one of the sides of the original rectangle. Then Bob tries to form some other rectangle from the two resulting rectangles, and he can rotate and move these two rectangles as he wishes.

Note that if two rectangles differ only by a $$$90^{\circ}$$$ rotation, they are considered the same. For example, the rectangles $$$6 \times 4$$$ and $$$4 \times 6$$$ are considered the same.

Thus, from the $$$2 \times 6$$$ rectangle, another rectangle can be formed, because it can be cut into two $$$2 \times 3$$$ rectangles, and then these two rectangles can be used to form the $$$4 \times 3$$$ rectangle, which is different from the $$$2 \times 6$$$ rectangle.

However, from the $$$2 \times 1$$$ rectangle, another rectangle cannot be formed, because it can only be cut into two rectangles of $$$1 \times 1$$$, and from these, only the $$$1 \times 2$$$ and $$$2 \times 1$$$ rectangles can be formed, which are considered the same.

Help Bob determine if he can obtain some other rectangle, or if he is just wasting his time.

Input format:
Each test consists of multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — the number of test cases. This is followed by the description of the test cases.

The single line of each test case contains two integers $$$a$$$ and $$$b$$$ ($$$1 \le a, b \le 10^9$$$) — the size of Bob's rectangle.

Output format:
For each test case, output "Yes" if Bob can obtain another rectangle from the $$$a \times b$$$ rectangle. Otherwise, output "No".

You can output the answer in any case (upper or lower). For example, the strings "yEs", "yes", "Yes", and "YES" will be recognized as positive answers.

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

Note:
In the first test case, the $$$1 \times 1$$$ rectangle cannot be cut into two rectangles, so another rectangle cannot be obtained from it.

In the fourth test case, the $$$3 \times 2$$$ rectangle can be cut into two $$$3 \times 1$$$ rectangles, and from these, the $$$1 \times 6$$$ rectangle can be formed.

In the fifth test case, the $$$2 \times 2$$$ rectangle can be cut into two $$$1 \times 2$$$ rectangles, and from these, the $$$1 \times 4$$$ rectangle can be formed.

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

Example output:
No
No
Yes
Yes
Yes
Yes
No

Editorial:
Physical Education Lesson
Contest: Codeforces Round 924 (Div. 2)
Difficulty rating: 1600
Tags: brute force, math, number theory

In a well-known school, a physical education lesson took place. As usual, everyone was lined up and asked to settle in "the first–$$$k$$$-th" position.

As is known, settling in "the first–$$$k$$$-th" position occurs as follows: the first $$$k$$$ people have numbers $$$1, 2, 3, \ldots, k$$$, the next $$$k - 2$$$ people have numbers $$$k - 1, k - 2, \ldots, 2$$$, the next $$$k$$$ people have numbers $$$1, 2, 3, \ldots, k$$$, and so on. Thus, the settling repeats every $$$2k - 2$$$ positions. Examples of settling are given in the "Note" section.

The boy Vasya constantly forgets everything. For example, he forgot the number $$$k$$$ described above. But he remembers the position he occupied in the line, as well as the number he received during the settling. Help Vasya understand how many natural numbers $$$k$$$ fit under the given constraints.

Note that the settling exists if and only if $$$k > 1$$$. In particular, this means that the settling does not exist for $$$k = 1$$$.

Input format:
Each test consists of multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 100$$$) — the number of test cases. This is followed by the description of the test cases.

The only line of each test case contains two integers $$$n$$$ and $$$x$$$ ($$$1 \le x < n \le 10^9$$$) — Vasya's position in the line and the number Vasya received during the settling.

Output format:
For each test case, output a single integer — the number of different $$$k$$$ that fit under the given constraints.

It can be proven that under the given constraints, the answer is finite.

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

Note:
In the first test case, $$$k$$$ equals $$$2, 3, 5, 6$$$ are suitable.

An example of settling for these $$$k$$$:

$$$k$$$ / №$$$1$$$$$$2$$$$$$3$$$$$$4$$$$$$5$$$$$$6$$$$$$7$$$$$$8$$$$$$9$$$$$$10$$$$$$2$$$$$$1$$$$$$2$$$$$$1$$$$$$2$$$$$$1$$$$$$2$$$$$$1$$$$$$2$$$$$$1$$$$$$2$$$$$$3$$$$$$1$$$$$$2$$$$$$3$$$$$$2$$$$$$1$$$$$$2$$$$$$3$$$$$$2$$$$$$1$$$$$$2$$$$$$5$$$$$$1$$$$$$2$$$$$$3$$$$$$4$$$$$$5$$$$$$4$$$$$$3$$$$$$2$$$$$$1$$$$$$2$$$$$$6$$$$$$1$$$$$$2$$$$$$3$$$$$$4$$$$$$5$$$$$$6$$$$$$5$$$$$$4$$$$$$3$$$$$$2$$$

In the second test case, $$$k = 2$$$ is suitable.

Example input:
5
10 2
3 1
76 4
100 99
1000000000 500000000

Example output:
4
1
9
0
1

Editorial:
Whose sentence is it?
Contest: Codeforces Round 185 (Div. 2)
Difficulty rating: 1100
Tags: implementation, strings

One day, liouzhou_101 got a chat record of Freda and Rainbow. Out of curiosity, he wanted to know which sentences were said by Freda, and which were said by Rainbow. According to his experience, he thought that Freda always said "lala." at the end of her sentences, while Rainbow always said "miao." at the beginning of his sentences. For each sentence in the chat record, help liouzhou_101 find whose sentence it is.

Input format:
The first line of the input contains an integer n (1 ≤ n ≤ 10), number of sentences in the chat record. Each of the next n lines contains a sentence. A sentence is a string that contains only Latin letters (A-Z, a-z), underline (_), comma (,), point (.) and space ( ). Its length doesn’t exceed 100.

Output format:
For each sentence, output "Freda's" if the sentence was said by Freda, "Rainbow's" if the sentence was said by Rainbow, or "OMG>.< I don't know!" if liouzhou_101 can’t recognize whose sentence it is. He can’t recognize a sentence if it begins with "miao." and ends with "lala.", or satisfies neither of the conditions.

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

Example input:
5
I will go to play with you lala.
wow, welcome.
miao.lala.
miao.
miao .

Example output:
Freda's
OMG>.< I don't know!
OMG>.< I don't know!
Rainbow's
OMG>.< I don't know!

Editorial:
Archer
Contest: Codeforces Round 185 (Div. 2)
Difficulty rating: 1300
Tags: math, probabilities

SmallR is an archer. SmallR is taking a match of archer with Zanoes. They try to shoot in the target in turns, and SmallR shoots first. The probability of shooting the target each time is $${ \frac { a } { b } }$$ for SmallR while $$\frac{c}{d}$$ for Zanoes. The one who shoots in the target first should be the winner.

Output the probability that SmallR will win the match.

Input format:
A single line contains four integers $$a,b,c,d \ (1 \leq a,b,c,d \leq 1000, 0 < \frac{a}{b} < 1, 0 < \frac{c}{d} < 1)$$.

Output format:
Print a single real number, the probability that SmallR will win the match.

The answer will be considered correct if the absolute or relative error doesn't exceed 10 - 6.

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

Example input:
1 2 1 2

Example output:
0.666666666667

Editorial:
Number of Apartments
Contest: Educational Codeforces Round 96 (Rated for Div. 2)
Difficulty rating: 900
Tags: brute force, constructive algorithms, math

Recently a new building with a new layout was constructed in Monocarp's hometown. According to this new layout, the building consists of three types of apartments: three-room, five-room, and seven-room apartments. It's also known that each room of each apartment has exactly one window. In other words, a three-room apartment has three windows, a five-room — five windows, and a seven-room — seven windows.

Monocarp went around the building and counted $$$n$$$ windows. Now he is wondering, how many apartments of each type the building may have.

Unfortunately, Monocarp only recently has learned to count, so he is asking you to help him to calculate the possible quantities of three-room, five-room, and seven-room apartments in the building that has $$$n$$$ windows. If there are multiple answers, you can print any of them.

Here are some examples:

- if Monocarp has counted $$$30$$$ windows, there could have been $$$2$$$ three-room apartments, $$$2$$$ five-room apartments and $$$2$$$ seven-room apartments, since $$$2 \cdot 3 + 2 \cdot 5 + 2 \cdot 7 = 30$$$;
- if Monocarp has counted $$$67$$$ windows, there could have been $$$7$$$ three-room apartments, $$$5$$$ five-room apartments and $$$3$$$ seven-room apartments, since $$$7 \cdot 3 + 5 \cdot 5 + 3 \cdot 7 = 67$$$;
- if Monocarp has counted $$$4$$$ windows, he should have mistaken since no building with the aforementioned layout can have $$$4$$$ windows.

Input format:
Th first line contains one integer $$$t$$$ ($$$1 \le t \le 1000$$$) — the number of test cases.

The only line of each test case contains one integer $$$n$$$ ($$$1 \le n \le 1000$$$) — the number of windows in the building.

Output format:
For each test case, if a building with the new layout and the given number of windows just can't exist, print $$$-1$$$.

Otherwise, print three non-negative integers — the possible number of three-room, five-room, and seven-room apartments. If there are multiple answers, print any of them.

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

Example input:
4
30
67
4
14

Example output:
2 2 2
7 5 3
-1
0 0 2

Editorial: