1337xyz1337xyz/codeforces-editorial-full-2026-07-16 huggingface dataset:
"Is the number of ones divisible by 3?" oracle
Contest: Microsoft Q# Coding Contest - Winter 2019
Tags: *special

Implement a quantum oracle on $$$N$$$ qubits which checks whether the number of bits equal to 1 in the input vector $$$\vec{x}$$$ is divisible by 3 (i.e., implements the function $$$f(\vec{x}) = 1$$$ if the number of $$$x_i = 1$$$ in $$$\vec{x}$$$ is divisible by 3, and 0 otherwise).

You have to implement an operation which takes the following inputs:

- an array of $$$N$$$ ($$$1 \le N \le 9$$$) qubits $$$x$$$ in an arbitrary state (input register),
- a qubit $$$y$$$ in an arbitrary state (output qubit),

and performs a transformation $$$|x\rangle|y\rangle \rightarrow |x\rangle|y \oplus f(x)\rangle$$$. The operation doesn't have an output; its "output" is the state in which it leaves the qubits. Note that the input register $$$x$$$ has to remain unchanged after applying the operation.

Your code should have the following signature:

Note: the operation has to have an adjoint specified for it; adjoint auto means that the adjoint will be generated automatically. For details on adjoint, see Operation Declarations.

You are not allowed to use measurements in your operation.

Constraints:
Time limit: 7.0 s
Memory limit: 1024.0 MB

Editorial:
Block diagonal matrix
Contest: Microsoft Q# Coding Contest - Winter 2019
Tags: *special

Implement a unitary operation on $$$N$$$ qubits which is represented by a square matrix of size $$$2^N$$$ which has 2x2 blocks of non-zero elements on the main diagonal and zero elements everywhere else.

For example, for $$$N = 3$$$ the matrix of the operation should have the following shape:

Here X denotes a "non-zero" element of the matrix (a complex number which has the square of the absolute value greater than or equal to $$$10^{-5}$$$), and . denotes a "zero" element of the matrix (a complex number which has the square of the absolute value less than $$$10^{-5}$$$).

The row and column indices of the matrix follow little endian format: the least significant bit of the index is stored first in the qubit array. Thus, the first column of the matrix gives you the coefficients of the basis states you'll get if you apply the unitary to the $$$|00..0\rangle$$$ basis state, the second column - to the $$$|10..0\rangle$$$ basis state etc. You can use the DumpUnitary tool to get the coefficients of the matrix your unitary implements (up to relative phases between columns) and the corresponding pattern of Xs and .s.

You have to implement an operation which takes an array of $$$N$$$ ($$$2 \le N \le 5$$$) qubits as an input and applies the unitary transformation with the matrix of the described shape to it. If there are multiple unitaries which satisfy the requirements, you can implement any of them. The "output" of your operation is the pattern of the matrix coefficients implemented by it; you can see the testing harness in the UnitaryPatterns kata.

Your code should have the following signature:

You are not allowed to use measurements in your operation.

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

Editorial:
Pattern of increasing blocks
Contest: Microsoft Q# Coding Contest - Winter 2019
Tags: *special

Implement a unitary operation on $$$N$$$ qubits which is represented by a square matrix of size $$$2^N$$$ defined as follows:

- top right and bottom left quarters are filled with zero elements,
- the top left quarter is the same pattern of size $$$2^{N-1}$$$ (for $$$N = 1$$$, the top left quarter is a non-zero element),
- the bottom right quarter is filled with non-zero elements.

For example, for $$$N = 3$$$ the matrix of the operation should have the following shape:

Here X denotes a "non-zero" element of the matrix (a complex number which has the square of the absolute value greater than or equal to $$$10^{-5}$$$), and . denotes a "zero" element of the matrix (a complex number which has the square of the absolute value less than $$$10^{-5}$$$).

The row and column indices of the matrix follow little endian format: the least significant bit of the index is stored first in the qubit array. Thus, the first column of the matrix gives you the coefficients of the basis states you'll get if you apply the unitary to the $$$|00..0\rangle$$$ basis state, the second column - to the $$$|10..0\rangle$$$ basis state etc. You can use the DumpUnitary tool to get the coefficients of the matrix your unitary implements (up to relative phases between columns) and the corresponding pattern of Xs and .s.

You have to implement an operation which takes an array of $$$N$$$ ($$$2 \le N \le 5$$$) qubits as an input and applies the unitary transformation with the matrix of the described shape to it. If there are multiple unitaries which satisfy the requirements, you can implement any of them. The "output" of your operation is the pattern of the matrix coefficients implemented by it; you can see the testing harness in the UnitaryPatterns kata.

Your code should have the following signature:

You are not allowed to use measurements in your operation.

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

Editorial:
X-wing fighter
Contest: Microsoft Q# Coding Contest - Winter 2019
Tags: *special

Implement a unitary operation on $$$N$$$ qubits which is represented by a square matrix of size $$$2^N$$$ which has non-zero elements on both main diagonal and anti-diagonal and zero elements everywhere else.

For example, for $$$N = 3$$$ the matrix of the operation should have the following shape:

Here X denotes a "non-zero" element of the matrix (a complex number which has the square of the absolute value greater than or equal to $$$10^{-5}$$$), and . denotes a "zero" element of the matrix (a complex number which has the square of the absolute value less than $$$10^{-5}$$$).

The row and column indices of the matrix follow little endian format: the least significant bit of the index is stored first in the qubit array. Thus, the first column of the matrix gives you the coefficients of the basis states you'll get if you apply the unitary to the $$$|00..0\rangle$$$ basis state, the second column - to the $$$|10..0\rangle$$$ basis state etc. You can use the DumpUnitary tool to get the coefficients of the matrix your unitary implements (up to relative phases between columns) and the corresponding pattern of Xs and .s.

You have to implement an operation which takes an array of $$$N$$$ ($$$2 \le N \le 5$$$) qubits as an input and applies the unitary transformation with the matrix of the described shape to it. If there are multiple unitaries which satisfy the requirements, you can implement any of them. The "output" of your operation is the pattern of the matrix coefficients implemented by it; you can see the testing harness in the UnitaryPatterns kata.

Your code should have the following signature:

You are not allowed to use measurements in your operation.

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

Editorial:
TIE fighter
Contest: Microsoft Q# Coding Contest - Winter 2019
Tags: *special

Implement a unitary operation on $$$N$$$ qubits which is represented by a square matrix of size $$$2^N$$$ which has non-zero elements in the following positions:

- the central 2x2 sub-matrix,
- the diagonals of the top right and bottom left square sub-matrices of size $$$2^{N-1}-1$$$ that do not overlap with the central 2x2 sub-matrix,
- the anti-diagonals of the top left and bottom right square sub-matrices of size $$$2^{N-1}-1$$$ that do not overlap with the central 2x2 sub-matrix.

For example, for $$$N = 3$$$ the matrix of the operation should have the following shape:

Here X denotes a "non-zero" element of the matrix (a complex number which has the square of the absolute value greater than or equal to $$$10^{-5}$$$), and . denotes a "zero" element of the matrix (a complex number which has the square of the absolute value less than $$$10^{-5}$$$).

The row and column indices of the matrix follow little endian format: the least significant bit of the index is stored first in the qubit array. Thus, the first column of the matrix gives you the coefficients of the basis states you'll get if you apply the unitary to the $$$|00..0\rangle$$$ basis state, the second column - to the $$$|10..0\rangle$$$ basis state etc. You can use the DumpUnitary tool to get the coefficients of the matrix your unitary implements (up to relative phases between columns) and the corresponding pattern of Xs and .s.

You have to implement an operation which takes an array of $$$N$$$ ($$$2 \le N \le 5$$$) qubits as an input and applies the unitary transformation with the matrix of the described shape to it. If there are multiple unitaries which satisfy the requirements, you can implement any of them. The "output" of your operation is the pattern of the matrix coefficients implemented by it; you can see the testing harness in the UnitaryPatterns kata.

Your code should have the following signature:

You are not allowed to use measurements in your operation.

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

Editorial:
Creeper
Contest: Microsoft Q# Coding Contest - Winter 2019
Tags: *special

Implement a unitary operation on 3 qubits which is represented by a square matrix of size 8 with the following pattern:

Here X denotes a "non-zero" element of the matrix (a complex number which has the square of the absolute value greater than or equal to $$$10^{-5}$$$), and . denotes a "zero" element of the matrix (a complex number which has the square of the absolute value less than $$$10^{-5}$$$).

The row and column indices of the matrix follow little endian format: the least significant bit of the index is stored first in the qubit array. Thus, the first column of the matrix gives you the coefficients of the basis states you'll get if you apply the unitary to the $$$|00..0\rangle$$$ basis state, the second column - to the $$$|10..0\rangle$$$ basis state etc. You can use the DumpUnitary tool to get the coefficients of the matrix your unitary implements (up to relative phases between columns) and the corresponding pattern of Xs and .s.

You have to implement an operation which takes an array of 3 qubits as an input and applies the unitary transformation with the matrix of the described shape to it. If there are multiple unitaries which satisfy the requirements, you can implement any of them. The "output" of your operation is the pattern of the matrix coefficients implemented by it; you can see the testing harness in the UnitaryPatterns kata.

Your code should have the following signature:

You are not allowed to use measurements in your operation.

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

Editorial:
Hessenberg matrix
Contest: Microsoft Q# Coding Contest - Winter 2019
Tags: *special

Implement a unitary operation on $$$N$$$ qubits which is represented by an upper Hessenberg matrix (a square matrix of size $$$2^N$$$ which has all zero elements below the first subdiagonal and all non-zero elements on the first subdiagonal and above it).

For example, for $$$N = 2$$$ the matrix of the operation should have the following shape:

Here X denotes a "non-zero" element of the matrix (a complex number which has the square of the absolute value greater than or equal to $$$10^{-5}$$$), and . denotes a "zero" element of the matrix (a complex number which has the square of the absolute value less than $$$10^{-5}$$$).

The row and column indices of the matrix follow little endian format: the least significant bit of the index is stored first in the qubit array. Thus, the first column of the matrix gives you the coefficients of the basis states you'll get if you apply the unitary to the $$$|00..0\rangle$$$ basis state, the second column - to the $$$|10..0\rangle$$$ basis state etc. You can use the DumpUnitary tool to get the coefficients of the matrix your unitary implements (up to relative phases between columns) and the corresponding pattern of Xs and .s.

You have to implement an operation which takes an array of $$$N$$$ ($$$2 \le N \le 4$$$) qubits as an input and applies the unitary transformation with the matrix of the described shape to it. If there are multiple unitaries which satisfy the requirements, you can implement any of them. The "output" of your operation is the pattern of the matrix coefficients implemented by it; you can see the testing harness in the UnitaryPatterns kata.

Your code should have the following signature:

You are not allowed to use measurements in your operation.

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

Editorial:
Tricky Sum
Contest: Educational Codeforces Round 1
Difficulty rating: 900
Tags: math

In this problem you are to calculate the sum of all integers from 1 to n, but you should take all powers of two with minus in the sum.

For example, for n = 4 the sum is equal to  - 1 - 2 + 3 - 4 =  - 4, because 1, 2 and 4 are 20, 21 and 22 respectively.

Calculate the answer for t values of n.

Input format:
The first line of the input contains a single integer t (1 ≤ t ≤ 100) — the number of values of n to be processed.

Each of next t lines contains a single integer n (1 ≤ n ≤ 109).

Output format:
Print the requested sum for each of t integers n given in the input.

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

Note:
The answer for the first sample is explained in the statement.

Example input:
2
4
1000000000

Example output:
-4
499999998352516354

Editorial:
Queries on a String
Contest: Educational Codeforces Round 1
Difficulty rating: 1300
Tags: implementation, strings

You are given a string s and should process m queries. Each query is described by two 1-based indices li, ri and integer ki. It means that you should cyclically shift the substring s[li... ri] ki times. The queries should be processed one after another in the order they are given.

One operation of a cyclic shift (rotation) is equivalent to moving the last character to the position of the first character and shifting all other characters one position to the right.

For example, if the string s is abacaba and the query is l1 = 3, r1 = 6, k1 = 1 then the answer is abbacaa. If after that we would process the query l2 = 1, r2 = 4, k2 = 2 then we would get the string baabcaa.

Input format:
The first line of the input contains the string s (1 ≤ |s| ≤ 10 000) in its initial state, where |s| stands for the length of s. It contains only lowercase English letters.

Second line contains a single integer m (1 ≤ m ≤ 300) — the number of queries.

The i-th of the next m lines contains three integers li, ri and ki (1 ≤ li ≤ ri ≤ |s|, 1 ≤ ki ≤ 1 000 000) — the description of the i-th query.

Output format:
Print the resulting string s after processing all m queries.

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

Note:
The sample is described in problem statement.

Example input:
abacaba
2
3 6 1
1 4 2

Example output:
baabcaa

Editorial:
Nearest vectors
Contest: Educational Codeforces Round 1
Difficulty rating: 2300
Tags: geometry, sortings

You are given the set of vectors on the plane, each of them starting at the origin. Your task is to find a pair of vectors with the minimal non-oriented angle between them.

Non-oriented angle is non-negative value, minimal between clockwise and counterclockwise direction angles. Non-oriented angle is always between 0 and π. For example, opposite directions vectors have angle equals to π.

Input format:
First line of the input contains a single integer n (2 ≤ n ≤ 100 000) — the number of vectors.

The i-th of the following n lines contains two integers xi and yi (|x|, |y| ≤ 10 000, x2 + y2 > 0) — the coordinates of the i-th vector. Vectors are numbered from 1 to n in order of appearing in the input. It is guaranteed that no two vectors in the input share the same direction (but they still can have opposite directions).

Output format:
Print two integer numbers a and b (a ≠ b) — a pair of indices of vectors with the minimal non-oriented angle. You can print the numbers in any order. If there are many possible answers, print any.

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

Example input:
4
-1 0
0 -1
1 0
1 1

Example output:
3 4

Example input:
6
-1 0
0 -1
1 0
1 1
-4 -5
-4 -6

Example output:
6 5

Editorial:
Igor In the Museum
Contest: Educational Codeforces Round 1
Difficulty rating: 1700
Tags: dfs and similar, graphs, shortest paths

Igor is in the museum and he wants to see as many pictures as possible.

Museum can be represented as a rectangular field of n × m cells. Each cell is either empty or impassable. Empty cells are marked with '.', impassable cells are marked with '*'. Every two adjacent cells of different types (one empty and one impassable) are divided by a wall containing one picture.

At the beginning Igor is in some empty cell. At every moment he can move to any empty cell that share a side with the current one.

For several starting positions you should calculate the maximum number of pictures that Igor can see. Igor is able to see the picture only if he is in the cell adjacent to the wall with this picture. Igor have a lot of time, so he will examine every picture he can see.

Input format:
First line of the input contains three integers n, m and k (3 ≤ n, m ≤ 1000, 1 ≤ k ≤ min(n·m, 100 000)) — the museum dimensions and the number of starting positions to process.

Each of the next n lines contains m symbols '.', '*' — the description of the museum. It is guaranteed that all border cells are impassable, so Igor can't go out from the museum.

Each of the last k lines contains two integers x and y (1 ≤ x ≤ n, 1 ≤ y ≤ m) — the row and the column of one of Igor's starting positions respectively. Rows are numbered from top to bottom, columns — from left to right. It is guaranteed that all starting positions are empty cells.

Output format:
Print k integers — the maximum number of pictures, that Igor can see if he starts in corresponding position.

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

Example input:
5 6 3
******
*..*.*
******
*....*
******
2 2
2 5
4 3

Example output:
6
4
10

Example input:
4 4 1
****
*..*
*.**
****
3 2

Example output:
8

Editorial:
Chocolate Bar
Contest: Educational Codeforces Round 1
Difficulty rating: 2000
Tags: brute force, dp

You have a rectangular chocolate bar consisting of n × m single squares. You want to eat exactly k squares, so you may need to break the chocolate bar.

In one move you can break any single rectangular piece of chocolate in two rectangular pieces. You can break only by lines between squares: horizontally or vertically. The cost of breaking is equal to square of the break length.

For example, if you have a chocolate bar consisting of 2 × 3 unit squares then you can break it horizontally and get two 1 × 3 pieces (the cost of such breaking is 32 = 9), or you can break it vertically in two ways and get two pieces: 2 × 1 and 2 × 2 (the cost of such breaking is 22 = 4).

For several given values n, m and k find the minimum total cost of breaking. You can eat exactly k squares of chocolate if after all operations of breaking there is a set of rectangular pieces of chocolate with the total size equal to k squares. The remaining n·m - k squares are not necessarily form a single rectangular piece.

Input format:
The first line of the input contains a single integer t (1 ≤ t ≤ 40910) — the number of values n, m and k to process.

Each of the next t lines contains three integers n, m and k (1 ≤ n, m ≤ 30, 1 ≤ k ≤ min(n·m, 50)) — the dimensions of the chocolate bar and the number of squares you want to eat respectively.

Output format:
For each n, m and k print the minimum total cost needed to break the chocolate bar, in order to make it possible to eat exactly k squares.

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

Note:
In the first query of the sample one needs to perform two breaks:

- to split 2 × 2 bar into two pieces of 2 × 1 (cost is 22 = 4),
- to split the resulting 2 × 1 into two 1 × 1 pieces (cost is 12 = 1).

In the second query of the sample one wants to eat 3 unit squares. One can use exactly the same strategy as in the first query of the sample.

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

Example output:
5
5
4
0

Editorial:
Cut Length
Contest: Educational Codeforces Round 1
Difficulty rating: 2900
Tags: geometry

Given simple (without self-intersections) n-gon. It is not necessary convex. Also you are given m lines. For each line find the length of common part of the line and the n-gon.

The boundary of n-gon belongs to polygon. It is possible that n-gon contains 180-degree angles.

Input format:
The first line contains integers n and m (3 ≤ n ≤ 1000;1 ≤ m ≤ 100). The following n lines contain coordinates of polygon vertices (in clockwise or counterclockwise direction). All vertices are distinct.

The following m lines contain line descriptions. Each of them contains two distict points of a line by their coordinates.

All given in the input coordinates are real numbers, given with at most two digits after decimal point. They do not exceed 105 by absolute values.

Output format:
Print m lines, the i-th line should contain the length of common part of the given n-gon and the i-th line. The answer will be considered correct if the absolute or relative error doesn't exceed 10 - 6.

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

Example input:
4 3
0 0
1 0
1 1
0 1
0 0 1 1
0 0 0 1
0 0 1 -1

Example output:
1.41421356237309514547
1.00000000000000000000
0.00000000000000000000

Editorial:
The Elder Trolls IV: Oblivon
Contest: Codeforces Beta Round 66
Difficulty rating: 1600
Tags: greedy, math

Vasya plays The Elder Trolls IV: Oblivon. Oh, those creators of computer games! What they do not come up with! Absolutely unique monsters have been added to the The Elder Trolls IV: Oblivon. One of these monsters is Unkillable Slug. Why it is "Unkillable"? Firstly, because it can be killed with cutting weapon only, so lovers of two-handed amber hammers should find suitable knife themselves. Secondly, it is necessary to make so many cutting strokes to Unkillable Slug. Extremely many. Too many!

Vasya has already promoted his character to 80-th level and in order to gain level 81 he was asked to kill Unkillable Slug. The monster has a very interesting shape. It looks like a rectangular parallelepiped with size x × y × z, consisting of undestructable cells 1 × 1 × 1. At one stroke Vasya can cut the Slug along an imaginary grid, i.e. cut with a plane parallel to one of the parallelepiped side. Monster dies when amount of parts it is divided reaches some critical value.

All parts of monster do not fall after each cut, they remains exactly on its places. I. e. Vasya can cut several parts with one cut.

Vasya wants to know what the maximum number of pieces he can cut the Unkillable Slug into striking him at most k times.

Vasya's character uses absolutely thin sword with infinite length.

Input format:
The first line of input contains four integer numbers x, y, z, k (1 ≤ x, y, z ≤ 106, 0 ≤ k ≤ 109).

Output format:
Output the only number — the answer for the problem.

Please, do not use %lld specificator to read or write 64-bit integers in C++. It is preffered to use cout (also you may use %I64d).

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

Note:
In the first sample Vasya make 3 pairwise perpendicular cuts. He cuts monster on two parts with the first cut, then he divides each part on two with the second cut, and finally he divides each of the 4 parts on two.

Example input:
2 2 2 3

Example output:
8

Example input:
2 2 2 1

Example output:
2

Editorial: