1337xyz1337xyz/codeforces-editorial-full-2026-07-16 huggingface dataset:
Candy Boxes
Contest: Codeforces Round 278 (Div. 2)
Difficulty rating: 1900
Tags: brute force, constructive algorithms, math

There is an old tradition of keeping 4 boxes of candies in the house in Cyberland. The numbers of candies are special if their arithmetic mean, their median and their range are all equal. By definition, for a set {x1, x2, x3, x4} (x1 ≤ x2 ≤ x3 ≤ x4) arithmetic mean is $$\frac{x_{1}+x_{2}+x_{3}+x_{4}}{4}$$, median is $$\frac{x_{2}+x_{3}}{2}$$ and range is x4 - x1. The arithmetic mean and median are not necessary integer. It is well-known that if those three numbers are same, boxes will create a "debugging field" and codes in the field will have no bugs.

For example, 1, 1, 3, 3 is the example of 4 numbers meeting the condition because their mean, median and range are all equal to 2.

Jeff has 4 special boxes of candies. However, something bad has happened! Some of the boxes could have been lost and now there are only n (0 ≤ n ≤ 4) boxes remaining. The i-th remaining box contains ai candies.

Now Jeff wants to know: is there a possible way to find the number of candies of the 4 - n missing boxes, meeting the condition above (the mean, median and range are equal)?

Input format:
The first line of input contains an only integer n (0 ≤ n ≤ 4).

The next n lines contain integers ai, denoting the number of candies in the i-th box (1 ≤ ai ≤ 500).

Output format:
In the first output line, print "YES" if a solution exists, or print "NO" if there is no solution.

If a solution exists, you should output 4 - n more lines, each line containing an integer b, denoting the number of candies in a missing box.

All your numbers b must satisfy inequality 1 ≤ b ≤ 106. It is guaranteed that if there exists a positive integer solution, you can always find such b's meeting the condition. If there are multiple answers, you are allowed to print any of them.

Given numbers ai may follow in any order in the input, not necessary in non-decreasing.

ai may have stood at any positions in the original set, not necessary on lowest n first positions.

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

Note:
For the first sample, the numbers of candies in 4 boxes can be 1, 1, 3, 3. The arithmetic mean, the median and the range of them are all 2.

For the second sample, it's impossible to find the missing number of candies.

In the third example no box has been lost and numbers satisfy the condition.

You may output b in any order.

Example input:
2
1
1

Example output:
YES
3
3

Example input:
3
1
1
1

Example output:
NO

Editorial:
Cifera
Contest: Codeforces Beta Round 86 (Div. 2 Only)
Difficulty rating: 1000
Tags: math

When Petya went to school, he got interested in large numbers and what they were called in ancient times. For instance, he learned that the Russian word "tma" (which now means "too much to be counted") used to stand for a thousand and "tma tmyschaya" (which literally means "the tma of tmas") used to stand for a million.

Petya wanted to modernize the words we use for numbers and invented a word petricium that represents number k. Moreover, petricium la petricium stands for number k2, petricium la petricium la petricium stands for k3 and so on. All numbers of this form are called petriciumus cifera, and the number's importance is the number of articles la in its title.

Petya's invention brought on a challenge that needed to be solved quickly: does some number l belong to the set petriciumus cifera? As Petya is a very busy schoolboy he needs to automate the process, he asked you to solve it.

Input format:
The first input line contains integer number k, the second line contains integer number l (2 ≤ k, l ≤ 231 - 1).

Output format:
You should print in the first line of the output "YES", if the number belongs to the set petriciumus cifera and otherwise print "NO". If the number belongs to the set, then print on the seconds line the only number — the importance of number l.

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

Example input:
5
25

Example output:
YES
1

Example input:
3
8

Example output:
NO

Editorial:
PFAST Inc.
Contest: Codeforces Beta Round 86 (Div. 2 Only)
Difficulty rating: 1500
Tags: bitmasks, brute force, graphs

When little Petya grew up and entered the university, he started to take part in АСМ contests. Later he realized that he doesn't like how the АСМ contests are organised: the team could only have three members (and he couldn't take all his friends to the competitions and distribute the tasks between the team members efficiently), so he decided to organize his own contests PFAST Inc. — Petr and Friends Are Solving Tasks Corporation. PFAST Inc. rules allow a team to have unlimited number of members.

To make this format of contests popular he organised his own tournament. To create the team he will prepare for the contest organised by the PFAST Inc. rules, he chose several volunteers (up to 16 people) and decided to compile a team from them. Petya understands perfectly that if a team has two people that don't get on well, then the team will perform poorly. Put together a team with as many players as possible given that all players should get on well with each other.

Input format:
The first line contains two integer numbers n (1 ≤ n ≤ 16) — the number of volunteers, and m ($$0 \leq m \leq \frac{n(n-1)}{2}$$) — the number of pairs that do not get on. Next n lines contain the volunteers' names (each name is a non-empty string consisting of no more than 10 uppercase and/or lowercase Latin letters). Next m lines contain two names — the names of the volunteers who do not get on. The names in pair are separated with a single space. Each pair of volunteers who do not get on occurs exactly once. The strings are case-sensitive. All n names are distinct.

Output format:
The first output line should contain the single number k — the number of people in the sought team. Next k lines should contain the names of the sought team's participants in the lexicographical order. If there are several variants to solve the problem, print any of them. Petya might not be a member of the sought team.

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

Example input:
3 1
Petya
Vasya
Masha
Petya Vasya

Example output:
2
Masha
Petya

Example input:
3 0
Pasha
Lesha
Vanya

Example output:
3
Lesha
Pasha
Vanya

Editorial:
Increasing Sequence
Contest: Codeforces Round 899 (Div. 2)
Difficulty rating: 800
Tags: greedy

You are given a sequence $$$a_{1}, a_{2}, \ldots, a_{n}$$$. A sequence $$$b_{1}, b_{2}, \ldots, b_{n}$$$ is called good, if it satisfies all of the following conditions:

- $$$b_{i}$$$ is a positive integer for $$$i = 1, 2, \ldots, n$$$;
- $$$b_{i} \neq a_{i}$$$ for $$$i = 1, 2, \ldots, n$$$;
- $$$b_{1} < b_{2} < \ldots < b_{n}$$$.

Input format:
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 100$$$). The description of the test cases follows.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 100$$$).

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^{9}$$$).

Output format:
For each test case, print a single integer — the minimum value of $$$b_{n}$$$ among all good sequences $$$b$$$.

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

Note:
In the first test case, $$$b = [2, 4, 5, 7, 8]$$$ is a good sequence. It can be proved that there is no good $$$b$$$ with $$$b_{5} < 8$$$.

In the second test case, $$$b = [1, 2, 3, 4]$$$ is an optimal good sequence.

In the third test case, $$$b = [2]$$$ is an optimal good sequence.

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

Example output:
8
4
2

Editorial:
Greedy solution. Continue constructing $$$b$$$ as small as possible.
If $$$a_{1} = 1$$$, $$$b_{1} = 2$$$. Else, $$$b_{1} = 1$$$.
And, for $$$i \ge 2$$$, if $$$a_{i} = b_{i-1} + 1$$$, $$$b_{i} = b_{i-1} + 2$$$. Else, $$$b_{i} = b_{i-1} + 1$$$.
$$$b_{n}$$$ calculated by this process is the answer.
Time complexity is $$$\mathcal{O}(n)$$$ per test case.