1337xyz1337xyz/codeforces-editorial-full-2026-07-16 huggingface dataset:
Postcard
Contest: Codeforces Round 530 (Div. 2)
Difficulty rating: 1200
Tags: constructive algorithms, implementation

Andrey received a postcard from Irina. It contained only the words "Hello, Andrey!", and a strange string consisting of lowercase Latin letters, snowflakes and candy canes. Andrey thought that this string is an encrypted message, and decided to decrypt it.

Andrey noticed that snowflakes and candy canes always stand after the letters, so he supposed that the message was encrypted as follows. Candy cane means that the letter before it can be removed, or can be left. A snowflake means that the letter before it can be removed, left, or repeated several times.

For example, consider the following string:

This string can encode the message «happynewyear». For this, candy canes and snowflakes should be used as follows:

- candy cane 1: remove the letter w,
- snowflake 1: repeat the letter p twice,
- candy cane 2: leave the letter n,
- snowflake 2: remove the letter w,
- snowflake 3: leave the letter e.

Please note that the same string can encode different messages. For example, the string above can encode «hayewyar», «happpppynewwwwwyear», and other messages.

Andrey knows that messages from Irina usually have a length of $$$k$$$ letters. Help him to find out if a given string can encode a message of $$$k$$$ letters, and if so, give an example of such a message.

Input format:
The first line contains the string received in the postcard. The string consists only of lowercase Latin letters, as well as the characters «*» and «?», meaning snowflake and candy cone, respectively. These characters can only appear immediately after the letter. The length of the string does not exceed $$$200$$$.

The second line contains an integer number $$$k$$$ ($$$1 \leq k \leq 200$$$), the required message length.

Output format:
Print any message of length $$$k$$$ that the given string can encode, or «Impossible» if such a message does not exist.

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

Example input:
hw?ap*yn?eww*ye*ar
12

Example output:
happynewyear

Example input:
ab?a
2

Example output:
aa

Editorial:
If the string in the postcard does not contain any snowflakes or candy cones, $$$k$$$ must be equal to the length of the string, because the only string encoded by such message is the string itself, and in this case if $$$k$$$ is not equal to the length of the string, the answer is «Impossible».
Let's call the characters of the message mandatory if they are not followed by snowflakes or candy cones. Clearly $$$k$$$ should be at least the number of mandatory characters, otherwise the answer is «Impossible».
In case there a snowflake (*) in the message, we can repeat the preceding character enough times to get the length $$$k$$$, and remove the rest of non-mandatory characters.
If there are no snowflakes, but only candy cones, we should use the characters followed by candy cones until we get the desired length $$$k$$$. In case we don't have enough, the answer is «Impossible».
Toy Army
Contest: Codeforces Beta Round 72 (Div. 2 Only)
Difficulty rating: 900
Tags: math, number theory

The hero of our story, Valera, and his best friend Arcady are still in school, and therefore they spend all the free time playing turn-based strategy "GAGA: Go And Go Again". The gameplay is as follows.

There are two armies on the playing field each of which consists of n men (n is always even). The current player specifies for each of her soldiers an enemy's soldier he will shoot (a target) and then all the player's soldiers shot simultaneously. This is a game world, and so each soldier shoots perfectly, that is he absolutely always hits the specified target. If an enemy soldier is hit, he will surely die. It may happen that several soldiers had been indicated the same target. Killed soldiers do not participate in the game anymore.

The game "GAGA" consists of three steps: first Valera makes a move, then Arcady, then Valera again and the game ends.

You are asked to calculate the maximum total number of soldiers that may be killed during the game.

Input format:
The input data consist of a single integer n (2 ≤ n ≤ 108, n is even). Please note that before the game starts there are 2n soldiers on the fields.

Output format:
Print a single number — a maximum total number of soldiers that could be killed in the course of the game in three turns.

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

Note:
The first sample test:

1) Valera's soldiers 1 and 2 shoot at Arcady's soldier 1.

2) Arcady's soldier 2 shoots at Valera's soldier 1.

3) Valera's soldier 1 shoots at Arcady's soldier 2.

There are 3 soldiers killed in total: Valera's soldier 1 and Arcady's soldiers 1 and 2.

Example input:
2

Example output:
3

Example input:
4

Example output:
6

Editorial:
Biathlon
Contest: Codeforces Beta Round 72 (Div. 2 Only)
Difficulty rating: 1700
Tags: binary search, implementation

Perhaps many have heard that the World Biathlon Championship has finished. Although our hero Valera was not present at this spectacular event himself and only watched it on TV, it excited him so much that he decided to enroll in a biathlon section.

Of course, biathlon as any sport, proved very difficult in practice. It takes much time and effort. Workouts, workouts, and workouts, — that's what awaited Valera on his way to great achievements in biathlon.

As for the workouts, you all probably know that every professional biathlete should ski fast and shoot precisely at the shooting range. Only in this case you can hope to be successful, because running and shooting are the two main components of biathlon. Valera has been diligent in his ski trainings, which is why he runs really fast, however, his shooting accuracy is nothing to write home about.

On a biathlon base where Valera is preparing for the competition, there is a huge rifle range with n targets. Each target have shape of a circle, and the center of each circle is located on the Ox axis. At the last training session Valera made the total of m shots. To make monitoring of his own results easier for him, one rather well-known programmer (of course it is you) was commissioned to write a program that would reveal how many and which targets Valera hit. More specifically, for each target the program must print the number of the first successful shot (in the target), or "-1" if this was not hit. The target is considered hit if the shot is inside the circle or on its boundary. Valera is counting on you and perhaps, thanks to you he will one day win international competitions.

Input format:
The first line of the input file contains the integer n (1 ≤ n ≤ 104), which is the number of targets. The next n lines contain descriptions of the targets. Each target is a circle whose center is located on the Ox axis. Each circle is given by its coordinate of the center x ( - 2·104 ≤ x ≤ 2·104) and its radius r (1 ≤ r ≤ 1000). It is guaranteed that no two targets coincide, intersect or are nested into each other, but they can touch each other.

The next line contains integer m (1 ≤ m ≤ 2·105), which is the number of shots. Next m lines contain descriptions of the shots, which are points on the plane, given by their coordinates x and y ( - 2·104 ≤ x, y ≤ 2·104).

All the numbers in the input are integers.

Targets and shots are numbered starting from one in the order of the input.

Output format:
Print on the first line a single number, the number of targets hit by Valera. Print on the second line for each of the targets the number of its first hit or "-1" (without quotes) if this number does not exist. Separate numbers with spaces.

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

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

Example output:
2
3 3 -1

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

Example output:
3
1 2 4

Editorial:
Candies and Two Sisters
Contest: Codeforces Round 634 (Div. 3)
Difficulty rating: 800
Tags: math

There are two sisters Alice and Betty. You have $$$n$$$ candies. You want to distribute these $$$n$$$ candies between two sisters in such a way that:

- Alice will get $$$a$$$ ($$$a > 0$$$) candies;
- Betty will get $$$b$$$ ($$$b > 0$$$) candies;
- each sister will get some integer number of candies;
- Alice will get a greater amount of candies than Betty (i.e. $$$a > b$$$);
- all the candies will be given to one of two sisters (i.e. $$$a+b=n$$$).

Your task is to calculate the number of ways to distribute exactly $$$n$$$ candies between sisters in a way described above. Candies are indistinguishable.

Formally, find the number of ways to represent $$$n$$$ as the sum of $$$n=a+b$$$, where $$$a$$$ and $$$b$$$ are positive integers and $$$a>b$$$.

You have to answer $$$t$$$ independent test cases.

Input format:
The first line of the input contains one integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases. Then $$$t$$$ test cases follow.

The only line of a test case contains one integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^9$$$) — the number of candies you have.

Output format:
For each test case, print the answer — the number of ways to distribute exactly $$$n$$$ candies between two sisters in a way described in the problem statement. If there is no way to satisfy all the conditions, print $$$0$$$.

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

Note:
For the test case of the example, the $$$3$$$ possible ways to distribute candies are:

- $$$a=6$$$, $$$b=1$$$;
- $$$a=5$$$, $$$b=2$$$;
- $$$a=4$$$, $$$b=3$$$.

Example input:
6
7
1
2
3
2000000000
763243547

Example output:
3
0
0
1
999999999
381621773

Editorial:
The answer is $$$\lfloor\frac{n-1}{2}\rfloor$$$, where $$$\lfloor x \rfloor$$$ is $$$x$$$ rounded down.
Construct the String
Contest: Codeforces Round 634 (Div. 3)
Difficulty rating: 900
Tags: constructive algorithms

You are given three positive integers $$$n$$$, $$$a$$$ and $$$b$$$. You have to construct a string $$$s$$$ of length $$$n$$$ consisting of lowercase Latin letters such that each substring of length $$$a$$$ has exactly $$$b$$$ distinct letters. It is guaranteed that the answer exists.

You have to answer $$$t$$$ independent test cases.

Recall that the substring $$$s[l \dots r]$$$ is the string $$$s_l, s_{l+1}, \dots, s_{r}$$$ and its length is $$$r - l + 1$$$. In this problem you are only interested in substrings of length $$$a$$$.

Input format:
The first line of the input contains one integer $$$t$$$ ($$$1 \le t \le 2000$$$) — the number of test cases. Then $$$t$$$ test cases follow.

The only line of a test case contains three space-separated integers $$$n$$$, $$$a$$$ and $$$b$$$ ($$$1 \le a \le n \le 2000, 1 \le b \le \min(26, a)$$$), where $$$n$$$ is the length of the required string, $$$a$$$ is the length of a substring and $$$b$$$ is the required number of distinct letters in each substring of length $$$a$$$.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2000$$$ ($$$\sum n \le 2000$$$).

Output format:
For each test case, print the answer — such a string $$$s$$$ of length $$$n$$$ consisting of lowercase Latin letters that each substring of length $$$a$$$ has exactly $$$b$$$ distinct letters. If there are multiple valid answers, print any of them. It is guaranteed that the answer exists.

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

Note:
In the first test case of the example, consider all the substrings of length $$$5$$$:

- "tleel": it contains $$$3$$$ distinct (unique) letters,
- "leelt": it contains $$$3$$$ distinct (unique) letters,
- "eelte": it contains $$$3$$$ distinct (unique) letters.

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

Example output:
tleelte
qwerty
vvvvvv
abcde

Editorial:
If we represent letters with digits, then the answer can be represented as $$$1, 2, \dots, b, 1, 2, \dots, b, \dots$$$. There is no substring containing more than $$$b$$$ distinct characters and each substring of length $$$a$$$ contains exactly $$$b$$$ distinct characters because of the condition $$$b \le a$$$.
Time complexity: $$$O(n)$$$.