1337xyz1337xyz/codeforces-editorial-full-2026-07-16 huggingface dataset:
s-palindrome
Contest: Educational Codeforces Round 14
Difficulty rating: 1600
Tags: implementation, strings

Let's call a string "s-palindrome" if it is symmetric about the middle of the string. For example, the string "oHo" is "s-palindrome", but the string "aa" is not. The string "aa" is not "s-palindrome", because the second half of it is not a mirror reflection of the first half.

English alphabet

You are given a string s. Check if the string is "s-palindrome".

Input format:
The only line contains the string s (1 ≤ |s| ≤ 1000) which consists of only English letters.

Output format:
Print "TAK" if the string s is "s-palindrome" and "NIE" otherwise.

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

Example input:
oXoxoXo

Example output:
TAK

Example input:
bod

Example output:
TAK

Editorial:
Exponential notation
Contest: Educational Codeforces Round 14
Difficulty rating: 1800
Tags: implementation, strings

You are given a positive decimal number x.

Your task is to convert it to the "simple exponential notation".

Let x = a·10b, where 1 ≤ a < 10, then in general case the "simple exponential notation" looks like "aEb". If b equals to zero, the part "Eb" should be skipped. If a is an integer, it should be written without decimal point. Also there should not be extra zeroes in a and b.

Input format:
The only line contains the positive decimal number x. The length of the line will not exceed 106. Note that you are given too large number, so you can't use standard built-in data types "float", "double" and other.

Output format:
Print the only line — the "simple exponential notation" of the given number x.

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

Example input:
16

Example output:
1.6E1

Example input:
01.23400

Example output:
1.234

Editorial:
Swaps in Permutation
Contest: Educational Codeforces Round 14
Difficulty rating: 1700
Tags: dfs and similar, dsu, math

You are given a permutation of the numbers 1, 2, ..., n and m pairs of positions (aj, bj).

At each step you can choose a pair from the given positions and swap the numbers in that positions. What is the lexicographically maximal permutation one can get?

Let p and q be two permutations of the numbers 1, 2, ..., n. p is lexicographically smaller than the q if a number 1 ≤ i ≤ n exists, so pk = qk for 1 ≤ k < i and pi < qi.

Input format:
The first line contains two integers n and m (1 ≤ n, m ≤ 106) — the length of the permutation p and the number of pairs of positions.

The second line contains n distinct integers pi (1 ≤ pi ≤ n) — the elements of the permutation p.

Each of the last m lines contains two integers (aj, bj) (1 ≤ aj, bj ≤ n) — the pairs of positions to swap. Note that you are given a positions, not the values to swap.

Output format:
Print the only line with n distinct integers p'i (1 ≤ p'i ≤ n) — the lexicographically maximal permutation one can get.

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

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

Example output:
7 8 9 4 5 6 1 2 3

Editorial:
Xor-sequences
Contest: Educational Codeforces Round 14
Difficulty rating: 1900
Tags: matrices

You are given n integers a1,  a2,  ...,  an.

A sequence of integers x1,  x2,  ...,  xk is called a "xor-sequence" if for every 1  ≤  i  ≤  k - 1 the number of ones in the binary representation of the number xi $$\times$$ xi  +  1's is a multiple of 3 and $$x_i \in \{a_1, a_2, \ldots, a_n\}$$ for all 1 ≤ i ≤ k. The symbol $$\times$$ is used for the binary exclusive or operation.

How many "xor-sequences" of length k exist? Output the answer modulo 109 + 7.

Note if a = [1, 1] and k = 1 then the answer is 2, because you should consider the ones from a as different.

Input format:
The first line contains two integers n and k (1 ≤ n ≤ 100, 1 ≤ k ≤ 1018) — the number of given integers and the length of the "xor-sequences".

The second line contains n integers ai (0 ≤ ai ≤ 1018).

Output format:
Print the only integer c — the number of "xor-sequences" of length k modulo 109 + 7.

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

Example input:
5 2
15 1 2 4 8

Example output:
13

Example input:
5 1
15 1 2 4 8

Example output:
5

Editorial:
Password
Contest: Educational Codeforces Round 137 (Rated for Div. 2)
Difficulty rating: 800
Tags: brute force, combinatorics, implementation, math

Monocarp has forgotten the password to his mobile phone. The password consists of $$$4$$$ digits from $$$0$$$ to $$$9$$$ (note that it can start with the digit $$$0$$$).

Monocarp remembers that his password had exactly two different digits, and each of these digits appeared exactly two times in the password. Monocarp also remembers some digits which were definitely not used in the password.

You have to calculate the number of different sequences of $$$4$$$ digits that could be the password for Monocarp's mobile phone (i. e. these sequences should meet all constraints on Monocarp's password).

Input format:
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 200$$$) — the number of testcases.

The first line of each testcase contains a single integer $$$n$$$ ($$$1 \le n \le 8$$$) — the number of digits for which Monocarp remembers that they were not used in the password.

The second line contains $$$n$$$ different integers $$$a_1, a_2, \dots a_n$$$ ($$$0 \le a_i \le 9$$$) representing the digits that were not used in the password. Note that the digits $$$a_1, a_2, \dots, a_n$$$ are given in ascending order.

Output format:
For each testcase, print one integer — the number of different $$$4$$$-digit sequences that meet the constraints.

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

Note:
In the first example, all possible passwords are: "3377", "3737", "3773", "7337", "7373", "7733".

Example input:
2
8
0 1 2 4 5 6 8 9
1
8

Example output:
6
216

Editorial:
There are two possible solutions for the problem.
The first solution is basically brute force. Each password can be obtained from an integer from $$$0$$$ to $$$9999$$$. If the number is from $$$1000$$$ to $$$9999$$$, then it's already a password of length $$$4$$$. Otherwise, you have to prepend it with enough zeros so that it becomes length $$$4$$$.
Then you have to check if the password is valid. First, check if it consists of exactly two different digits: make a set of all its characters (set<char> in case of C++, for example) and check its size. Then check if the first digit of the password appears exactly twice. It would mean that the other digits appears exactly twice as well. Finally, check if neither of the found digits are forbidden.
The second solution is based on combinatorics. First, choose the two digits that will appear in the password: $$$C(10 - n, 2)$$$. Since $$$n$$$ digits are prohibited, the remaining $$$10 - n$$$ are allowed. Second, choose the positions that will be taken by the first one: $$$C(4, 2)$$$. The answer is the product of these two values.
Permutation Value
Contest: Educational Codeforces Round 137 (Rated for Div. 2)
Difficulty rating: 800
Tags: constructive algorithms, greedy

You are given an integer $$$n$$$. You have to construct a permutation of size $$$n$$$.

A permutation is an array where each integer from $$$1$$$ to $$$s$$$ (where $$$s$$$ is the size of permutation) occurs exactly once. For example, $$$[2, 1, 4, 3]$$$ is a permutation of size $$$4$$$; $$$[1, 2, 4, 5, 3]$$$ is a permutation of size $$$5$$$; $$$[1, 4, 3]$$$ is not a permutation (the integer $$$2$$$ is absent), $$$[2, 1, 3, 1]$$$ is not a permutation (the integer $$$1$$$ appears twice).

A subsegment of a permutation is a contiguous subsequence of that permutation. For example, the permutation $$$[2, 1, 4, 3]$$$ has $$$10$$$ subsegments: $$$[2]$$$, $$$[2, 1]$$$, $$$[2, 1, 4]$$$, $$$[2, 1, 4, 3]$$$, $$$[1]$$$, $$$[1, 4]$$$, $$$[1, 4, 3]$$$, $$$[4]$$$, $$$[4, 3]$$$ and $$$[3]$$$.

The value of the permutation is the number of its subsegments which are also permutations. For example, the value of $$$[2, 1, 4, 3]$$$ is $$$3$$$ since the subsegments $$$[2, 1]$$$, $$$[1]$$$ and $$$[2, 1, 4, 3]$$$ are permutations.

You have to construct a permutation of size $$$n$$$ with minimum possible value among all permutations of size $$$n$$$.

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

Then, $$$t$$$ lines follow. The $$$i$$$-th of them contains one integer $$$n$$$ ($$$3 \le n \le 50$$$) representing the $$$i$$$-th test case.

Output format:
For each test case, print $$$n$$$ integers — the permutation of size $$$n$$$ with minimum possible value. If there are multiple such permutations, print any of them.

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

Note:
In the first example, the permutation $$$[1, 4, 3, 5, 2]$$$ is one of the possible answers; its value is $$$2$$$.

In the second example, the permutation $$$[4, 1, 6, 2, 5, 3]$$$ is one of the possible answers; its value is $$$2$$$.

Example input:
2
5
6

Example output:
1 4 3 5 2
4 1 6 2 5 3

Editorial:
The subsegment $$$[1]$$$, as well as the whole permutation, will always be a permutation, so the value is at least $$$2$$$. Let's try to find a way to generate a permutation of $$$n$$$ elements with value equal to $$$2$$$.
Every permutation must contain the number $$$1$$$. Let's try to construct the answer in such a way that if a subsegment contains the number $$$1$$$, then it also contains the number $$$n$$$ (if it is so, it can only be a permutation if it contains all $$$n$$$ numbers). If we begin our permutation with the numbers $$$1$$$ and $$$n$$$, we will reach our goal: the only subsegment which does not contain $$$n$$$ but contains $$$1$$$ is $$$[1]$$$, and the only subsegment which contains $$$n$$$ and also a permutation is the whole permutation itself. So, any permutation that begins with $$$[1, n \dots]$$$ can be the answer.
Not Adding
Contest: Codeforces Round 766 (Div. 2)
Difficulty rating: 1900
Tags: brute force, dp, math, number theory

You have an array $$$a_1, a_2, \dots, a_n$$$ consisting of $$$n$$$ distinct integers. You are allowed to perform the following operation on it:

- Choose two elements from the array $$$a_i$$$ and $$$a_j$$$ ($$$i \ne j$$$) such that $$$\gcd(a_i, a_j)$$$ is not present in the array, and add $$$\gcd(a_i, a_j)$$$ to the end of the array. Here $$$\gcd(x, y)$$$ denotes greatest common divisor (GCD) of integers $$$x$$$ and $$$y$$$.

Note that the array changes after each operation, and the subsequent operations are performed on the new array.

What is the maximum number of times you can perform the operation on the array?

Input format:
The first line consists of a single integer $$$n$$$ ($$$2 \le n \le 10^6$$$).

The second line consists of $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \leq a_i \leq 10^6$$$). All $$$a_i$$$ are distinct.

Output format:
Output a single line containing one integer — the maximum number of times the operation can be performed on the given array.

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

Note:
In the first example, one of the ways to perform maximum number of operations on the array is:

- Pick $$$i = 1, j= 5$$$ and add $$$\gcd(a_1, a_5) = \gcd(4, 30) = 2$$$ to the array.
- Pick $$$i = 2, j= 4$$$ and add $$$\gcd(a_2, a_4) = \gcd(20, 25) = 5$$$ to the array.
- Pick $$$i = 2, j= 5$$$ and add $$$\gcd(a_2, a_5) = \gcd(20, 30) = 10$$$ to the array.

It can be proved that there is no way to perform more than $$$3$$$ operations on the original array.

In the second example one can add $$$3$$$, then $$$1$$$, then $$$5$$$, and $$$2$$$.

Example input:
5
4 20 1 25 30

Example output:
3

Example input:
3
6 10 15

Example output:
4

Editorial:
Note that the $$$\gcd$$$ of two numbers cannot exceed their maximum. Let the maximum element of the array be $$$A$$$. So for every number from $$$1$$$ to $$$A$$$, we try to check whether that element can be included in the array after performing some operations or not.
How to check for a particular number $$$x$$$?
For $$$x$$$ to be in the final array, either:
• It already exists in the initial array.
• Or, the $$$\gcd$$$ of all multiples of $$$x$$$ present in the initial array equals $$$x$$$.
Proof
For $$$x$$$ to be added after some operations, there must be some subset of the array which has a $$$\gcd$$$ equal to $$$x$$$. We can perform the operations by taking the current gcd and one element from the subset at a time and at the end we will obtain $$$x$$$.
Note that such a subset can only contain multiples of $$$x$$$. So it is enough to check that the $$$\gcd$$$ of all multiples is equal to $$$x$$$.
Thus, the overall solution takes $$$\mathcal{O}(n + A \log{A})$$$.
Transmigration
Contest: Codeforces Beta Round 81
Difficulty rating: 1700
Tags: implementation

In Disgaea as in most role-playing games, characters have skills that determine the character's ability to use certain weapons or spells. If the character does not have the necessary skill, he cannot use it. The skill level is represented as an integer that increases when you use this skill. Different character classes are characterized by different skills.

Unfortunately, the skills that are uncommon for the given character's class are quite difficult to obtain. To avoid this limitation, there is the so-called transmigration.

Transmigration is reincarnation of the character in a new creature. His soul shifts to a new body and retains part of his experience from the previous life.

As a result of transmigration the new character gets all the skills of the old character and the skill levels are reduced according to the k coefficient (if the skill level was equal to x, then after transmigration it becomes equal to [kx], where [y] is the integral part of y). If some skill's levels are strictly less than 100, these skills are forgotten (the character does not have them any more). After that the new character also gains the skills that are specific for his class, but are new to him. The levels of those additional skills are set to 0.

Thus, one can create a character with skills specific for completely different character classes via transmigrations. For example, creating a mage archer or a thief warrior is possible.

You are suggested to solve the following problem: what skills will the character have after transmigration and what will the levels of those skills be?

Input format:
The first line contains three numbers n, m and k — the number of skills the current character has, the number of skills specific for the class into which the character is going to transmigrate and the reducing coefficient respectively; n and m are integers, and k is a real number with exactly two digits after decimal point (1 ≤ n, m ≤ 20, 0.01 ≤ k ≤ 0.99).

Then follow n lines, each of which describes a character's skill in the form "name exp" — the skill's name and the character's skill level: name is a string and exp is an integer in range from 0 to 9999, inclusive.

Then follow m lines each of which contains names of skills specific for the class, into which the character transmigrates.

All names consist of lowercase Latin letters and their lengths can range from 1 to 20 characters, inclusive. All character's skills have distinct names. Besides the skills specific for the class into which the player transmigrates also have distinct names.

Output format:
Print on the first line number z — the number of skills the character will have after the transmigration. Then print z lines, on each of which print a skill's name and level, separated by a single space. The skills should be given in the lexicographical order.

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

Example input:
5 4 0.75
axe 350
impaler 300
ionize 80
megafire 120
magicboost 220
heal
megafire
shield
magicboost

Example output:
6
axe 262
heal 0
impaler 225
magicboost 165
megafire 0
shield 0

Editorial:
Dark Assembly
Contest: Codeforces Beta Round 81
Difficulty rating: 1800
Tags: brute force, probabilities

Dark Assembly is a governing body in the Netherworld. Here sit the senators who take the most important decisions for the player. For example, to expand the range of the shop or to improve certain characteristics of the character the Dark Assembly's approval is needed.

The Dark Assembly consists of n senators. Each of them is characterized by his level and loyalty to the player. The level is a positive integer which reflects a senator's strength. Loyalty is the probability of a positive decision in the voting, which is measured as a percentage with precision of up to 10%.

Senators make decisions by voting. Each of them makes a positive or negative decision in accordance with their loyalty. If strictly more than half of the senators take a positive decision, the player's proposal is approved.

If the player's proposal is not approved after the voting, then the player may appeal against the decision of the Dark Assembly. To do that, player needs to kill all the senators that voted against (there's nothing wrong in killing senators, they will resurrect later and will treat the player even worse). The probability that a player will be able to kill a certain group of senators is equal to A / (A + B), where A is the sum of levels of all player's characters and B is the sum of levels of all senators in this group. If the player kills all undesired senators, then his proposal is approved.

Senators are very fond of sweets. They can be bribed by giving them candies. For each received candy a senator increases his loyalty to the player by 10%. It's worth to mention that loyalty cannot exceed 100%. The player can take no more than k sweets to the courtroom. Candies should be given to the senators before the start of voting.

Determine the probability that the Dark Assembly approves the player's proposal if the candies are distributed among the senators in the optimal way.

Input format:
The first line contains three integers n, k and A (1 ≤ n, k ≤ 8, 1 ≤ A ≤ 9999).

Then n lines follow. The i-th of them contains two numbers — bi and li — the i-th senator's level and his loyalty.

The levels of all senators are integers in range from 1 to 9999 (inclusive). The loyalties of all senators are integers in range from 0 to 100 (inclusive) and all of them are divisible by 10.

Output format:
Print one real number with precision 10 - 6 — the maximal possible probability that the Dark Assembly approves the player's proposal for the best possible distribution of candies among the senators.

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

Note:
In the first sample the best way of candies' distribution is giving them to first three of the senators. It ensures most of votes.

It the second sample player should give all three candies to the fifth senator.

Example input:
5 6 100
11 80
14 90
23 70
80 30
153 70

Example output:
1.0000000000

Example input:
5 3 100
11 80
14 90
23 70
80 30
153 70

Example output:
0.9628442962

Editorial:
Lift and Throw
Contest: Codeforces Beta Round 81
Difficulty rating: 2500
Tags: brute force

You are given a straight half-line divided into segments of unit length, which we will call positions. The positions are numbered by positive integers that start with 1 from the end of half-line, i. e. 1, 2, 3 and so on. The distance between the positions is the absolute difference between the respective numbers.

Laharl, Etna and Flonne occupy some positions on the half-line and they want to get to the position with the largest possible number. They are originally placed in different positions.

Each of the characters can perform each of the following actions no more than once:

- Move a certain distance.
- Grab another character and lift him above the head.
- Throw the lifted character a certain distance.

Each character has a movement range parameter. They can only move to free positions, assuming that distance between those positions doesn't exceed the movement range.

One character can lift another character if the distance between the two characters equals 1, and no one already holds that another character. We can assume that the lifted character moves to the same position as the person who has lifted him, and the position in which he stood before becomes free. A lifted character cannot perform any actions and the character that holds him cannot walk.

Also, each character has a throwing range parameter. It is the distance at which this character can throw the one lifted above his head. He can only throw a character to a free position, and only when there is a lifted character.

We accept the situation when one person grabs another one who in his turn has the third character in his hands. This forms a "column" of three characters. For example, Laharl can hold Etna while Etna holds Flonne. In this case, Etna and the Flonne cannot perform any actions, and Laharl can only throw Etna (together with Flonne) at some distance.

Laharl, Etna and Flonne perform actions in any order. They perform actions in turns, that is no two of them can do actions at the same time.

Determine the maximum number of position at least one of the characters can reach. That is, such maximal number x so that one of the characters can reach position x.

Input format:
The first line contains three integers: Laharl's position, his movement range and throwing range. The second and the third lines describe Etna's and Flonne's parameters correspondingly in the similar form. It is guaranteed that the three characters occupy distinct positions. All numbers in the input are between 1 and 10, inclusive.

Output format:
Print a single number — the maximum ordinal number of position which either Laharl, Etna or Flonne can reach.

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

Note:
Let us explain how to reach position 15 in the sample.

Initially Laharl occupies position 9, Etna — position 4 and Flonne — position 2.

First Laharl moves to position 6.

Then Flonne moves to position 5 and grabs Etna.

Laharl grabs Flonne and throws to position 9.

Flonne throws Etna to position 12.

Etna moves to position 15.

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

Example output:
15

Editorial: