# Codeforces Round #690 (Div. 3) [Personal Summary]

A B C D E1 E2 F
O O O O O O O

## A. Favorite Sequence (800)

### Description

Time Limit: 2 seconds
Memory Limit: 256 megabytes

Polycarp has a favorite sequence $a[1 \dots n]$ consisting of $n$ integers. He wrote it out on the whiteboard as follows:

• he wrote the number $a_1$ to the left side (at the beginning of the whiteboard);
• he wrote the number $a_2$ to the right side (at the end of the whiteboard);
• then as far to the left as possible (but to the right from $a_1$), he wrote the number $a_3$;
• then as far to the right as possible (but to the left from $a_2$), he wrote the number $a_4$;
• Polycarp continued to act as well, until he wrote out the entire sequence on the whiteboard.
The beginning of the result looks like this (of course, if $n \ge 4$).

For example, if $n=7$ and $a=[3, 1, 4, 1, 5, 9, 2]$, then Polycarp will write a sequence on the whiteboard $[3, 4, 5, 2, 9, 1, 1]$.

You saw the sequence written on the whiteboard and now you want to restore Polycarp’s favorite sequence.

#### Input

The first line contains a single positive integer $t$ ($1 \le t \le 300$) — the number of test cases in the test. Then $t$ test cases follow.

The first line of each test case contains an integer $n$ ($1 \le n \le 300$) — the length of the sequence written on the whiteboard.

The next line contains $n$ integers $b_1, b_2,\ldots, b_n$ ($1 \le b_i \le 10^9$) — the sequence written on the whiteboard.

#### Output

Output $t$ answers to the test cases. Each answer — is a sequence $a$ that Polycarp wrote out on the whiteboard.

#### Note

In the first test case, the sequence $a$ matches the sequence from the statement. The whiteboard states after each step look like this:

$[3] \Rightarrow [3, 1] \Rightarrow [3, 4, 1] \Rightarrow [3, 4, 1, 1] \Rightarrow [3, 4, 5, 1, 1] \Rightarrow [3, 4, 5, 9, 1, 1] \Rightarrow [3, 4, 5, 2, 9, 1, 1]$.

## B. Last Year’s Substring (800)

### Description

Time Limit: 2 seconds
Memory Limit: 256 megabytes

Polycarp has a string $s[1 \dots n]$ of length $n$ consisting of decimal digits. Polycarp performs the following operation with the string $s$ no more than once (i.e. he can perform operation $0$ or $1$ time):

• Polycarp selects two numbers $i$ and $j$ ($1 \leq i \leq j \leq n$) and removes characters from the $s$ string at the positions $i, i+1, i+2, \ldots, j$ (i.e. removes substring $s[i \dots j]$). More formally, Polycarp turns the string $s$ into the string $s_1 s_2 \ldots s_{i-1} s_{j+1} s_{j+2} \ldots s_{n}$.

For example, the string $s=$"${\tt 20192020}$"​ Polycarp can turn into strings:

• $\tt 2020$” (in this case $(i,j)=(3,6)$ or $(i,j)=(1,4)$);
• $\tt 2019220$” (in this case $(i,j)=(6,6)$);
• $\tt 020$” (in this case $(i,j)=(1,5)$);
• other operations are also possible, only a few of them are listed above.

Polycarp likes the string “$\tt 2020$” very much, so he is wondering if it is possible to turn the string s into a string “$\tt 2020$” in no more than one operation? Note that you can perform zero operations.

#### Input

The first line contains a positive integer $t$ ($1 \leq t \leq 1000$) — number of test cases in the test. Then $t$ test cases follow.

The first line of each test case contains an integer $n$ ($4 \leq n \leq 200$) — length of the string $s$. The next line contains a string $s$ of length $n$ consisting of decimal digits. It is allowed that the string $s$ starts with digit $\tt 0$.

#### Output

For each test case, output on a separate line:

• $\tt YES$” if Polycarp can turn the string $s$ into a string “$\tt 2020$” in no more than one operation (i.e. he can perform $0$ or $1$ operation);
• $\tt NO$” otherwise.

You may print every letter of “$\tt YES$” and “$\tt NO$” in any case you want (so, for example, the strings $\tt yEs$, $\tt yes$, $\tt Yes$ and $\tt YES$ will all be recognized as positive answer).

#### Note

In the first test case, Polycarp could choose $i=3$ and $j=6$.

In the second test case, Polycarp could choose $i=2$ and $j=5$.

In the third test case, Polycarp did not perform any operations with the string.

## C. Unique Number (900)

### Description

Time Limit: 2 seconds
Memory Limit: 256 megabytes

You are given a positive number $x$. Find the smallest positive integer number that has the sum of digits equal to $x$ and all digits are distinct (unique).

#### Input

The first line contains a single positive integer $t$ ($1 \le t \le 50$) — the number of test cases in the test. Then $t$ test cases follow.

Each test case consists of a single integer number $x$ ($1 \le x \le 50$).

#### Output

Output $t$ answers to the test cases:

• if a positive integer number with the sum of digits equal to $x$ and all digits are different exists, print the smallest such number;
• otherwise print $\tt -1$.

## D. Add to Neighbour and Remove (1400)

### Description

Time Limit: 3 seconds
Memory Limit: 256 megabytes

Polycarp was given an array of $a[1 \dots n]$ of $n$ integers. He can perform the following operation with the array $a$ no more than $n$ times:

• Polycarp selects the index $i$ and adds the value $a_i$ to one of his choice of its neighbors. More formally, Polycarp adds the value of $a_i$ to $a_{i−1}$ or to $a_{i+1}$ (if such a neighbor does not exist, then it is impossible to add to it).
• After adding it, Polycarp removes the $i$-th element from the $a$ array. During this step the length of $a$ is decreased by $1$.

The two items above together denote one single operation.

For example, if Polycarp has an array $a = [3, 1, 6, 6, 2]$, then it can perform the following sequence of operations with it:

• Polycarp selects $i = 2$ and adds the value $a_i$ to $(i-1)$-th element: $a = [4, 6, 6, 2]$.
• Polycarp selects $i = 1$ and adds the value $a_i$ to $(i+1)$-th element: $a = [10, 6, 2]$.
• Polycarp selects $i = 3$ and adds the value $a_i$ to $(i-1)$-th element: $a = [10, 8]$.
• Polycarp selects $i = 2$ and adds the value $a_i$ to $(i-1)$-th element: $a = [18]$.

Note that Polycarp could stop performing operations at any time.

Polycarp wondered how many minimum operations he would need to perform to make all the elements of $a$ equal (i.e., he wants all $a_i$ are equal to each other).

#### Input

The first line contains a single integer $t$ ($1 \leq t \leq 3000$) — the number of test cases in the test. Then $t$ test cases follow.

The first line of each test case contains a single integer $n$ ($1 \leq n \leq 3000$) — the length of the array. The next line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \leq a_i \leq 10^5$) — array $a$.

It is guaranteed that the sum of $n$ over all test cases does not exceed $3000$.

#### Output

For each test case, output a single number — the minimum number of operations that Polycarp needs to perform so that all elements of the $a$ array are the same (equal).

#### Note

In the first test case of the example, the answer can be constructed like this (just one way among many other ways):

$[3, 1, 6, 6, 2]$ $\xrightarrow[]{i=4,~add~to~left}$ $[3, 1, 12, 2]$ $\xrightarrow[]{i=2,~add~to~right}$ $[3, 13, 2]$ $\xrightarrow[]{i=1,~add~to~right}$ $[16, 2]$ $\xrightarrow[]{i=2,~add~to~left}$ $[18]$. All elements of the array $[18]$ are the same.

In the second test case of the example, the answer can be constructed like this (just one way among other ways):

$[1, 2, 2, 1]$ $\xrightarrow[]{i=1,~add~to~right}$ $[3, 2, 1]$ $\xrightarrow[]{i=3,~add~to~left}$ $[3, 3]$. All elements of the array $[3, 3]$ are the same.

In the third test case of the example, Polycarp doesn’t need to perform any operations since $[2, 2, 2]$ contains equal (same) elements only.

In the fourth test case of the example, the answer can be constructed like this (just one way among other ways):

$[6, 3, 2, 1]$ $\xrightarrow[]{i=3,~add~to~right}$ $[6, 3, 3]$ $\xrightarrow[]{i=3,~add~to~left}$ $[6, 6]$. All elements of the array $[6, 6]$ are the same.

## E1. Close Tuples (easy version)

You need to set install_url to use ShareThis. Please set it in _config.yml.

### 评论

You forgot to set the shortname for Disqus. Please set it in _config.yml.