1337xyz1337xyz/codeforces-editorial-full-2026-07-16 huggingface dataset:
It's showtime
Contest: April Fools Day Contest 2020
Tags: *special

You are given a mysterious language (codenamed "UnknownX") available in "Custom Test" tab. Find out what this language is, and use it to solve the following problem.

You are given an integer $$$input = 1000 * n + mod$$$ ($$$1 \le n, mod \le 999$$$). Calculate double factorial of $$$n$$$ modulo $$$mod$$$.

Input format:
The input contains a single integer $$$input$$$ ($$$1001 \le input \le 999999$$$). You are guaranteed that $$$input \mod 1000 \neq 0$$$.

Output format:
Output a single number.

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

Note:
In the first test case you need to calculate $$$6!! \mod 100$$$; $$$6!! = 6 * 4 * 2 = 48$$$.

In the second test case you need to calculate $$$9!! \mod 900$$$; $$$9!! = 9 * 7 * 5 * 3 = 945$$$.

In the third test case you need to calculate $$$100!! \mod 2$$$; you can notice that $$$100!!$$$ is a multiple of 100 and thus is divisible by 2.

Example input:
6100

Example output:
48

Example input:
9900

Example output:
45

Editorial:
Data Recovery
Contest: Coder-Strike 2014 - Round 2
Difficulty rating: 1200
Tags: implementation

Not so long ago company R2 bought company R1 and consequently, all its developments in the field of multicore processors. Now the R2 laboratory is testing one of the R1 processors.

The testing goes in n steps, at each step the processor gets some instructions, and then its temperature is measured. The head engineer in R2 is keeping a report record on the work of the processor: he writes down the minimum and the maximum measured temperature in his notebook. His assistant had to write down all temperatures into his notebook, but (for unknown reasons) he recorded only m.

The next day, the engineer's assistant filed in a report with all the m temperatures. However, the chief engineer doubts that the assistant wrote down everything correctly (naturally, the chief engineer doesn't doubt his notes). So he asked you to help him. Given numbers n, m, min, max and the list of m temperatures determine whether you can upgrade the set of m temperatures to the set of n temperatures (that is add n - m temperatures), so that the minimum temperature was min and the maximum one was max.

Input format:
The first line contains four integers n, m, min, max (1 ≤ m < n ≤ 100; 1 ≤ min < max ≤ 100). The second line contains m space-separated integers ti (1 ≤ ti ≤ 100) — the temperatures reported by the assistant.

Note, that the reported temperatures, and the temperatures you want to add can contain equal temperatures.

Output format:
If the data is consistent, print 'Correct' (without the quotes). Otherwise, print 'Incorrect' (without the quotes).

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

Note:
In the first test sample one of the possible initial configurations of temperatures is [1, 2].

In the second test sample one of the possible initial configurations of temperatures is [2, 1, 3].

In the third test sample it is impossible to add one temperature to obtain the minimum equal to 1 and the maximum equal to 3.

Example input:
2 1 1 2
1

Example output:
Correct

Example input:
3 1 1 3
2

Example output:
Correct

Editorial:
Spyke Chatting
Contest: Coder-Strike 2014 - Round 2
Difficulty rating: 1300
Tags: implementation

The R2 company has n employees working for it. The work involves constant exchange of ideas, sharing the stories of success and upcoming challenging. For that, R2 uses a famous instant messaging program Spyke.

R2 has m Spyke chats just to discuss all sorts of issues. In each chat, some group of employees exchanges messages daily. An employee can simultaneously talk in multiple chats. If some employee is in the k-th chat, he can write messages to this chat and receive notifications about messages from this chat. If an employee writes a message in the chat, all other participants of the chat receive a message notification.

The R2 company is conducting an audit. Now the specialists study effective communication between the employees. For this purpose, they have a chat log and the description of chat structure. You, as one of audit specialists, are commissioned to write a program that will use this data to determine the total number of message notifications received by each employee.

Input format:
The first line contains three space-separated integers n, m and k (2 ≤ n ≤ 2·104; 1 ≤ m ≤ 10; 1 ≤ k ≤ 2·105) — the number of the employees, the number of chats and the number of events in the log, correspondingly.

Next n lines contain matrix a of size n × m, consisting of numbers zero and one. The element of this matrix, recorded in the j-th column of the i-th line, (let's denote it as aij) equals 1, if the i-th employee is the participant of the j-th chat, otherwise the element equals 0. Assume that the employees are numbered from 1 to n and the chats are numbered from 1 to m.

Next k lines contain the description of the log events. The i-th line contains two space-separated integers xi and yi (1 ≤ xi ≤ n; 1 ≤ yi ≤ m) which mean that the employee number xi sent one message to chat number yi. It is guaranteed that employee number xi is a participant of chat yi. It is guaranteed that each chat contains at least two employees.

Output format:
Print in the single line n space-separated integers, where the i-th integer shows the number of message notifications the i-th employee receives.

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

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

Example output:
3 3 1

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

Example output:
0 2 3 0

Editorial:
Jeopardy!
Contest: Coder-Strike 2014 - Round 2
Difficulty rating: 1400
Tags: greedy, math

'Jeopardy!' is an intellectual game where players answer questions and earn points. Company Q conducts a simplified 'Jeopardy!' tournament among the best IT companies. By a lucky coincidence, the old rivals made it to the finals: company R1 and company R2.

The finals will have n questions, m of them are auction questions and n - m of them are regular questions. Each question has a price. The price of the i-th question is ai points. During the game the players chose the questions. At that, if the question is an auction, then the player who chose it can change the price if the number of his current points is strictly larger than the price of the question. The new price of the question cannot be less than the original price and cannot be greater than the current number of points of the player who chose the question. The correct answer brings the player the points equal to the price of the question. The wrong answer to the question reduces the number of the player's points by the value of the question price.

The game will go as follows. First, the R2 company selects a question, then the questions are chosen by the one who answered the previous question correctly. If no one answered the question, then the person who chose last chooses again.

All R2 employees support their team. They want to calculate what maximum possible number of points the R2 team can get if luck is on their side during the whole game (they will always be the first to correctly answer questions). Perhaps you are not going to be surprised, but this problem was again entrusted for you to solve.

Input format:
The first line contains two space-separated integers n and m (1 ≤ n, m ≤ 100; m ≤ min(n, 30)) — the total number of questions and the number of auction questions, correspondingly. The second line contains n space-separated integers a1, a2, ..., an (1 ≤ ai ≤ 107) — the prices of the questions. The third line contains m distinct integers bi (1 ≤ bi ≤ n) — the numbers of auction questions. Assume that the questions are numbered from 1 to n.

Output format:
In the single line, print the answer to the problem — the maximum points the R2 company can get if it plays optimally well. It is guaranteed that the answer fits into the integer 64-bit signed type.

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

Example input:
4 1
1 3 7 5
3

Example output:
18

Example input:
3 2
10 3 8
2 3

Example output:
40

Editorial:
2048
Contest: Coder-Strike 2014 - Round 2
Difficulty rating: 2000
Tags: bitmasks, dp

The programmers from the R2 company love playing 2048. One day, they decided to invent their own simplified version of this game — 2k on a stripe.

Imagine an infinite in one direction stripe, consisting of unit squares (the side of each square is equal to the height of the stripe). Each square can either be empty or contain some number.

Initially, all squares are empty. Then at infinity one of the unit squares number 2 or 4 appears. Then the player presses a button once, and the appeared number begins to move towards the beginning of the stripe. Let's assume that some number x moves to the beginning of the stripe, then it will stop if:

1. it either gets in the first square of the stripe;
2. or it is in the square that is preceded by a square with number y (y ≠ x). But if number x at some point of time gets to the square with the same number then both numbers add to each other and result in 2x. The new number 2x continues moving to the beginning of the stripe by the same rules.

After the final stop of the number moving process, the infinity gets a new number 2 or 4 and the process repeats. Read the notes to the test samples to better understand the moving strategy.

I guess you've understood that the game progress fully depends on the order in which numbers 2 and 4 appear. Let's look at some sequence of numbers 2 and 4 in the game. We assume that the sequence is winning if it results in at least one square getting the number greater or equal than 2k.

The goal of the game is to make up a winning sequence of n numbers. But not everything is so simple, some numbers in the sequence are identified beforehand. You are given a sequence consisting of numbers 0, 2, 4. Count how many ways there are to replace each 0 of the sequence with 2 or 4 to get a winning sequence.

Input format:
The first line contains two integers n and k (1 ≤ n ≤ 2000; 3 ≤ k ≤ 11). The next line contains sequence of n integers, each of them is either 0, or 2, or 4.

Output format:
Print a single integer — the number of ways to replace zeroes by numbers 2 or 4 to get a winning sequence. As this number can be rather large, print it modulo 1000000007 (109 + 7).

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

Note:
Consider the first example. The beginning of the strip will look as follows:

2  →  4  →  8  →  8 2  →  8 4  →  8 4 2  →  16.

To better understand the game, you can see the original game on http://gabrielecirulli.github.io/2048/. Please note that the game that is described on the strip is slightly different from the original game (when the two numbers add up in the original game, they do not keep moving). Be careful, the game is addictive, there isn't much time for the contest!

Example input:
7 4
2 2 4 2 2 2 2

Example output:
1

Example input:
1 3
0

Example output:
0

Editorial:
Maze 2D
Contest: Coder-Strike 2014 - Round 2
Difficulty rating: 2200
Tags: data structures, divide and conquer

The last product of the R2 company in the 2D games' field is a new revolutionary algorithm of searching for the shortest path in a 2 × n maze.

Imagine a maze that looks like a 2 × n rectangle, divided into unit squares. Each unit square is either an empty cell or an obstacle. In one unit of time, a person can move from an empty cell of the maze to any side-adjacent empty cell. The shortest path problem is formulated as follows. Given two free maze cells, you need to determine the minimum time required to go from one cell to the other.

Unfortunately, the developed algorithm works well for only one request for finding the shortest path, in practice such requests occur quite often. You, as the chief R2 programmer, are commissioned to optimize the algorithm to find the shortest path. Write a program that will effectively respond to multiple requests to find the shortest path in a 2 × n maze.

Input format:
The first line contains two integers, n and m (1 ≤ n ≤ 2·105; 1 ≤ m ≤ 2·105) — the width of the maze and the number of queries, correspondingly. Next two lines contain the maze. Each line contains n characters, each character equals either '.' (empty cell), or 'X' (obstacle).

Each of the next m lines contains two integers vi and ui (1 ≤ vi, ui ≤ 2n) — the description of the i-th request. Numbers vi, ui mean that you need to print the value of the shortest path from the cell of the maze number vi to the cell number ui. We assume that the cells of the first line of the maze are numbered from 1 to n, from left to right, and the cells of the second line are numbered from n + 1 to 2n from left to right. It is guaranteed that both given cells are empty.

Output format:
Print m lines. In the i-th line print the answer to the i-th request — either the size of the shortest path or -1, if we can't reach the second cell from the first one.

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

Example input:
4 7
.X..
...X
5 1
1 3
7 7
1 4
6 1
4 7
5 7

Example output:
1
4
0
5
2
2
2

Example input:
10 3
X...X..X..
..X...X..X
11 7
7 18
18 10

Example output:
9
-1
3

Editorial:
Panoramix's Prediction
Contest: Codeforces Beta Round 69 (Div. 2 Only)
Difficulty rating: 800
Tags: brute force

A prime number is a number which has exactly two distinct divisors: one and itself. For example, numbers 2, 7, 3 are prime, and 1, 6, 4 are not.

The next prime number after x is the smallest prime number greater than x. For example, the next prime number after 2 is 3, and the next prime number after 3 is 5. Note that there is exactly one next prime number after each number. So 5 is not the next prime number for 2.

One cold April morning Panoramix predicted that soon Kakofonix will break free from his straitjacket, and this will be a black day for the residents of the Gallic countryside.

Panoramix's prophecy tells that if some day Asterix and Obelix beat exactly x Roman soldiers, where x is a prime number, and next day they beat exactly y Roman soldiers, where y is the next prime number after x, then it's time to wait for Armageddon, for nothing can shut Kakofonix up while he sings his infernal song.

Yesterday the Gauls beat n Roman soldiers and it turned out that the number n was prime! Today their victims were a troop of m Romans (m > n). Determine whether the Gauls should wait for the black day after today's victory of Asterix and Obelix?

Input format:
The first and only input line contains two positive integers — n and m (2 ≤ n < m ≤ 50). It is guaranteed that n is prime.

Pretests contain all the cases with restrictions 2 ≤ n < m ≤ 4.

Output format:
Print YES, if m is the next prime number after n, or NO otherwise.

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

Example input:
3 5

Example output:
YES

Example input:
7 11

Example output:
YES

Editorial:
Depression
Contest: Codeforces Beta Round 69 (Div. 2 Only)
Difficulty rating: 1200
Tags: geometry, math

Do you remember a kind cartoon "Beauty and the Beast"? No, no, there was no firing from machine guns or radiation mutants time-travels!

There was a beauty named Belle. Once she had violated the Beast's order and visited the West Wing. After that she was banished from the castle...

Everybody was upset. The beautiful Belle was upset, so was the Beast, so was Lumiere the candlestick. But the worst thing was that Cogsworth was upset. Cogsworth is not a human, but is the mantel clock, which was often used as an alarm clock.

Due to Cogsworth's frustration all the inhabitants of the castle were in trouble: now they could not determine when it was time to drink morning tea, and when it was time for an evening stroll.

Fortunately, deep in the basement are lying digital clock showing the time in the format HH:MM. Now the residents of the castle face a difficult task. They should turn Cogsworth's hour and minute mustache hands in such a way, that Cogsworth began to show the correct time. Moreover they need to find turn angles in degrees for each mustache hands. The initial time showed by Cogsworth is 12:00.

You can only rotate the hands forward, that is, as is shown in the picture:

As since there are many ways too select such angles because of full rotations, choose the smallest angles in the right (non-negative) direction.

Note that Cogsworth's hour and minute mustache hands move evenly and continuously. Hands are moving independently, so when turning one hand the other hand remains standing still.

Input format:
The only line of input contains current time according to the digital clock, formatted as HH:MM (00 ≤ HH ≤ 23, 00 ≤ MM ≤ 59). The mantel clock initially shows 12:00.

Pretests contain times of the beginning of some morning TV programs of the Channel One Russia.

Output format:
Print two numbers x and y — the angles of turning the hour and minute hands, respectively (0 ≤ x, y < 360). The absolute or relative error in the answer should not exceed 10 - 9.

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

Note:
A note to the second example: the hour hand will be positioned exactly in the middle, between 4 and 5.

Example input:
12:00

Example output:
0 0

Example input:
04:30

Example output:
135 180

Editorial:
Multiplication Table
Contest: Codeforces Round 319 (Div. 2)
Difficulty rating: 1000
Tags: implementation, number theory

Let's consider a table consisting of n rows and n columns. The cell located at the intersection of i-th row and j-th column contains number i × j. The rows and columns are numbered starting from 1.

You are given a positive integer x. Your task is to count the number of cells in a table that contain number x.

Input format:
The single line contains numbers n and x (1 ≤ n ≤ 105, 1 ≤ x ≤ 109) — the size of the table and the number that we are looking for in the table.

Output format:
Print a single number: the number of times x occurs in the table.

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

Note:
A table for the second sample test is given below. The occurrences of number 12 are marked bold.

Example input:
10 5

Example output:
2

Example input:
6 12

Example output:
4

Editorial:
Modulo Sum
Contest: Codeforces Round 319 (Div. 2)
Difficulty rating: 1900
Tags: combinatorics, data structures, dp, two pointers

You are given a sequence of numbers a1, a2, ..., an, and a number m.

Check if it is possible to choose a non-empty subsequence aij such that the sum of numbers in this subsequence is divisible by m.

Input format:
The first line contains two numbers, n and m (1 ≤ n ≤ 106, 2 ≤ m ≤ 103) — the size of the original sequence and the number such that sum should be divisible by it.

The second line contains n integers a1, a2, ..., an (0 ≤ ai ≤ 109).

Output format:
In the single line print either "YES" (without the quotes) if there exists the sought subsequence, or "NO" (without the quotes), if such subsequence doesn't exist.

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

Note:
In the first sample test you can choose numbers 2 and 3, the sum of which is divisible by 5.

In the second sample test the single non-empty subsequence of numbers is a single number 5. Number 5 is not divisible by 6, that is, the sought subsequence doesn't exist.

In the third sample test you need to choose two numbers 3 on the ends.

In the fourth sample test you can take the whole subsequence.

Example input:
3 5
1 2 3

Example output:
YES

Example input:
1 6
5

Example output:
NO

Editorial:
Changing Volume
Contest: Codeforces Round 601 (Div. 2)
Difficulty rating: 800
Tags: math

Bob watches TV every day. He always sets the volume of his TV to $$$b$$$. However, today he is angry to find out someone has changed the volume to $$$a$$$. Of course, Bob has a remote control that can change the volume.

There are six buttons ($$$-5, -2, -1, +1, +2, +5$$$) on the control, which in one press can either increase or decrease the current volume by $$$1$$$, $$$2$$$, or $$$5$$$. The volume can be arbitrarily large, but can never be negative. In other words, Bob cannot press the button if it causes the volume to be lower than $$$0$$$.

As Bob is so angry, he wants to change the volume to $$$b$$$ using as few button presses as possible. However, he forgets how to do such simple calculations, so he asks you for help. Write a program that given $$$a$$$ and $$$b$$$, finds the minimum number of presses to change the TV volume from $$$a$$$ to $$$b$$$.

Input format:
Each test contains multiple test cases. The first line contains the number of test cases $$$T$$$ ($$$1 \le T \le 1\,000$$$). Then the descriptions of the test cases follow.

Each test case consists of one line containing two integers $$$a$$$ and $$$b$$$ ($$$0 \le a, b \le 10^{9}$$$) — the current volume and Bob's desired volume, respectively.

Output format:
For each test case, output a single integer — the minimum number of presses to change the TV volume from $$$a$$$ to $$$b$$$. If Bob does not need to change the volume (i.e. $$$a=b$$$), then print $$$0$$$.

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

Note:
In the first example, Bob can press the $$$-2$$$ button twice to reach $$$0$$$. Note that Bob can not press $$$-5$$$ when the volume is $$$4$$$ since it will make the volume negative.

In the second example, one of the optimal ways for Bob is to press the $$$+5$$$ twice, then press $$$-1$$$ once.

In the last example, Bob can press the $$$+5$$$ once, then press $$$+1$$$.

Example input:
3
4 0
5 14
3 9

Example output:
2
3
2

Editorial:
Notice that if at some moment we increase the volume and at some moment we decrease the volume, we can remove those two actions and replace them with at most two new actions that are both increasing or decreasing (for instance, $$$+5$$$ $$$-1$$$ can be replaced with $$$+2$$$ $$$+2$$$; $$$+2$$$ and $$$-2$$$ can be replaced with nothing and $$$+2$$$ and $$$-1$$$ can be replaced with $$$+1$$$). We can see that replacing like this will not make the volume goes below zero at any moment. So, we will increase the volume all the time, or decrease all the time.
Assume that we only increase the volume. It can be proved that for any set consists of only $$$1$$$s and $$$2$$$s and the sum of its elements is greater than or equal to $$$5$$$, it has a subset which its elements sums to $$$5$$$. This means that if we use $$$+1$$$ and $$$+2$$$ to increase the volume by at least $$$5$$$, we can replace some of those actions with a $$$+5$$$. Hence, it is optimal to increase the volume by $$$5$$$ until the gap between $$$a$$$ and $$$b$$$ is less than $$$5$$$, then the remaining job is trivial.