Codeforces Edu. Round #102 (Div. 2) [Personal Summary]

A B C D E F G
O O O O Ø Ø Ø

A. Replacing Elements

Description

Time Limit: 2 seconds
Memory Limit: 256 megabytes

You have an array $a_1, a_2, \dots, a_n$. All $a_i$ are positive integers.

In one step you can choose three distinct indices $i$, $j$, and $k$ ($i \neq j$; $i \neq k$; $j \neq k$) and assign the sum of $a_j$ and $a_k$ to $a_i$, i. e. make $a_i = a_j + a_k$.

Can you make all $a_i$ lower or equal to $d$ using the operation above any number of times (possibly, zero)?

Input

The first line contains a single integer $t$ ($1 \le t \le 2000$) — the number of test cases.

The first line of each test case contains two integers $n$ and $d$ ($3 \le n \le 100$; $1 \le d \le 100$) — the number of elements in the array $a$ and the value $d$.

The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 100$) — the array $a$.

Output

For each test case, print $\texttt{YES}$, if it’s possible to make all elements $a_i$ less or equal than $d$ using the operation above. Otherwise, print $\texttt{NO}$.

You may print each letter in any case (for example, $\texttt{YES}$, $\texttt{Yes}$, $\texttt{yes}$, $\texttt{yEs}$ will all be recognized as positive answer).

Note

In the first test case, we can prove that we can’t make all $a_i \le 3$.

In the second test case, all $a_i$ are already less or equal than $d = 4$.

In the third test case, we can, for example, choose $i = 5$, $j = 1$, $k = 2$ and make $a_5 = a_1 + a_2 = 2 + 1 = 3$. Array $a$ will become $[2, 1, 5, 3, 3]$.

After that we can make $a_3 = a_5 + a_2 = 3 + 1 = 4$. Array will become $[2, 1, 4, 3, 3]$ and all elements are less or equal than $d = 4$.

B. String LCM

Description

Time Limit: 2 seconds
Memory Limit: 256 megabytes

Let’s define a multiplication operation between a string $a$ and a positive integer $x$: $a \cdot x$ is the string that is a result of writing $x$ copies of $a$ one after another. For example, “$\texttt{abc}$$\cdot~2~=$$\texttt{abcabc}$”, “$\texttt{a}$$\cdot~5~=$$\texttt{aaaaa}$”.

A string $a$ is divisible by another string $b$ if there exists an integer $x$ such that $b \cdot x = a$. For example, “$\texttt{abababab}$” is divisible by “$\texttt{ab}$”, but is not divisible by “$\texttt{ababab}$” or “$\texttt{aa}$”.

LCM of two strings $s$ and $t$ (defined as $LCM(s, t)$) is the shortest non-empty string that is divisible by both $s$ and $t$.

You are given two strings $s$ and $t$. Find $LCM(s, t)$ or report that it does not exist. It can be shown that if $LCM(s, t)$ exists, it is unique.

Input

The first line contains one integer $q$ ($1 \le q \le 2000$) — the number of test cases.

Each test case consists of two lines, containing strings $s$ and $t$ ($1 \le |s|, |t| \le 20$). Each character in each of these strings is either ‘$\texttt{a}$’ or ‘$\texttt{b}$’.

Output

For each test case, print $LCM(s, t)$ if it exists; otherwise, print $\texttt{-1}$ . It can be shown that if $LCM(s, t)$ exists, it is unique.

Note

In the first test case, “$\texttt{baba}$” = “$\texttt{baba}$$\cdot~1~=$$\texttt{ba}$$\cdot~2$.

In the second test case, “$\texttt{aaaaaa}$” = “$\texttt{aa}$$\cdot~3~=$$\texttt{aaa}$$\cdot~2$.

C. No More Inversions

Description

Time Limit: 2 seconds
Memory Limit: 256 megabytes

You have a sequence $a$ with $n$ elements $1, 2, 3, \dots, k - 1, k, k - 1, k - 2, \dots, k - (n - k)$ ($k \le n < 2k$).

Let’s call as inversion in $a$ a pair of indices $i < j$ such that $a[i] > a[j]$.

Suppose, you have some permutation $p$ of size $k$ and you build a sequence $b$ of size $n$ in the following manner: $b[i] = p[a[i]]$.

Your goal is to find such permutation $p$ that the total number of inversions in $b$ doesn’t exceed the total number of inversions in $a$, and $b$ is lexicographically maximum .

Small reminder: the sequence of $k$ integers is called a permutation if it contains all integers from $1$ to $k$ exactly once.

Another small reminder: a sequence $s$ is lexicographically smaller than another sequence $t$, if either $s$ is a prefix of $t$, or for the first $i$ such that $s_i \ne t_i$, $s_i < t_i$ holds (in the first position that these sequences are different, $s$ has smaller number than $t$).

Input

The first line contains a single integer $t$ ($1 \le t \le 1000$) — the number of test cases.

The first and only line of each test case contains two integers $n$ and $k$ ($k \le n < 2k$; $1 \le k \le 10^5$) — the length of the sequence $a$ and its maximum.

It’s guaranteed that the total sum of $k$ over test cases doesn’t exceed $10^5$.

Output

For each test case, print $k$ integers — the permutation $p$ which maximizes $b$ lexicographically without increasing the total number of inversions.

It can be proven that $p$ exists and is unique.

Note

In the first test case, the sequence $a = [1]$, there is only one permutation $p = [1]$.

In the second test case, the sequence $a = [1, 2]$. There is no inversion in $a$, so there is only one permutation $p = [1, 2]$ which doesn’t increase the number of inversions.

In the third test case, $a = [1, 2, 1]$ and has $1$ inversion. If we use $p = [2, 1]$, then $b = [p[a[1]], p[a[2]], p[a[3]]] = [2, 1, 2]$ and also has $1$ inversion.

In the fourth test case, $a = [1, 2, 3, 2]$, and since $p = [1, 3, 2]$ then $b = [1, 3, 2, 3]$. Both $a$ and $b$ have $1$ inversion and $b$ is the lexicographically maximum.

D. Program

Description

Time Limit: 2 seconds
Memory Limit: 256 megabytes

You are given a program that consists of $n$ instructions. Initially a single variable $x$ is assigned to $0$. Afterwards, the instructions are of two types:

• increase $x$ by $1$;
• decrease $x$ by $1$.

You are given $m$ queries of the following format:

• query $l$ $r$ — how many distinct values is $x$ assigned to if all the instructions between the $l$-th one and the $r$-th one inclusive are ignored and the rest are executed without changing the order?

Input

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

Then the description of $t$ testcases follows.

The first line of each testcase contains two integers $n$ and $m$ ($1 \le n, m \le 2 \cdot 10^5$) — the number of instructions in the program and the number of queries.

The second line of each testcase contains a program — a string of $n$ characters: each character is either ‘$\texttt{+}$’ or ‘$\texttt{-}$’ — increment and decrement instruction, respectively.

Each of the next $m$ lines contains two integers $l$ and $r$ ($1 \le l \le r \le n$) — the description of the query.

The sum of $n$ over all testcases doesn’t exceed $2 \cdot 10^5$. The sum of $m$ over all testcases doesn’t exceed $2 \cdot 10^5$.

Output

For each testcase print $m$ integers — for each query $l$, $r$ print the number of distinct values variable $x$ is assigned to if all the instructions between the $l$-th one and the $r$-th one inclusive are ignored and the rest are executed without changing the order.

Note

The instructions that remain for each query of the first testcase are:

1. empty program — $x$ was only equal to $0$;
2. $\texttt{-}$” — $x$ had values $0$ and $-1$;
3. $\texttt{---+}$” — $x$ had values $0$, $-1$, $-2$, $-3$, $-2$ — there are $4$ distinct values among them;
4. $\texttt{+--+--+}$” — the distinct values are $1$, $0$, $-1$, $-2$.

Solution

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.