算法竞赛 Codeforces Round #650 (Div. 3)

算法竞赛 Codeforces Round #650 (Div. 3)

参加了Codeforces Round #650 (Div. 3),这次没有咕咕咕,有生之年第一次做出C题,应该是难度不一样,明天看看就知道,照常记题翻译。

A. Short Substrings

》英文原题《

Alice 在猜 Bob 给他提供的数组。
一开始, Bob 有一个长度大于等于2的数组a,然后他利用数组a建立了一个新的数组b。建立规则如下:
1. 把数组a变成若干个长度为2的数组
2. 把这些长度为2的数组相连得到数组b

举个例子:
如果数组a="abac",他组成的长度为2的数组是"ab","ba","ac",因此,数组b="abbaac"。

你现在得到数组b,帮助 Alice 猜原数组a是什么。

Input

第一行是一个int t (1≤t≤1000) — 输入test的数量,接着是t组test。

每个test包含1个string b (2≤|b|≤100) — 数组b的值。

Output

输出t个test的结果
每个结果包含1个string a — 数组a的值。

Example

input

4
abbaac
ac
bccddaaf
zzzzzzzzzz

output

abac
ac
bcdaf
zzzzzz

Note

第1组案例的情况:
在举例中已给出
结果:"abac"

第2组案例的情况:
"ac"
结果:"ac"

第3组案例的情况:
"bc", "cd", "da", "af"
结果:"bcdaf"


B. Even Array

》英文原题《

一个数组a[0 ~ n-1],包含n个自然数(0≤ai

如果这个数组中每一个ai%2都等于i%2,那么这个数组被称为good数组

举个例子:
数组[0,5,2,1]和[0,17,6,7]都是good数组,[2,4,6,7]是bad数组。

需要注意的是,你可以将数组中任意两个元素进行交换,以便将数组变成good数组。

如果这个数组可以变成good数组,找出交换次数的最小值。

Input

第一行是一个int t (1≤t≤1000) — 输入test的数量,接着是t组test。

每个test包含2行
第一行包含1个int n (1≤n≤40) — 数组的长度。

第二行包含n个int a0,a1,...,an-1(0≤ai≤1000) - 数组的元素。

Output

输出t个test的结果
将原数组通过交换变成good数组
如果可以,就输出交换次数的最小值;
如果不行就输出-1。

Example

input

4
4
3 2 7 6
3
3 2 6
1
7
7
4 9 2 1 18 3 0

output

2
1
-1
0

Note

第1组案例的情况:
1. a0和a1交换
2. a2和a3交换
结果:2

第1组案例的情况:
1. a0和a1交换
结果:1

第1组案例的情况:
无法变成good数组
结果:-1


C. Social Distance

》英文原题《

Polycarp 和他的朋友来到一家新餐馆。餐馆有n张桌子,并且排成一列,序号从左往右为1到n。桌子的状态被记录为一串字符串,字符串只包含"0"(桌子是空余的)和"1"(桌子被占用)。

餐馆有个规矩,禁止人们之间的距离小于k张桌子。也就是说,如果有个人坐在第i张桌子,那么从i-k到i+k(除了i)必须是空的。换句话说,两个人之间距离的绝对值必须大于k

举个例子:
如果n=8,k=2
数组"10010001", "10000010", "00000000", "00100000"是符合餐馆规矩的;
数组 "10100100", "10011001", "11111111"是不符合餐馆规矩的。

你将得到一个字符串表示餐馆的情况,请你计算餐馆最多还能容纳多少个客户

再举个例子:
如果n=6,k=1,s="100010"
则第3张桌子还可以坐人,所以结果为1

Input

第一行是一个int t (1≤t≤104) — 输入test的数量,接着是t组test。

每个test包含2行

第1行包含2个int n,k (1≤k≤n≤2⋅105) — 桌子的数量 两个人之间距离的绝对值

第2行包含一个字符串s — 餐馆桌子的情况

特别的,在所有test中n的总和不超过2⋅105

Output

输出t个test的结果
可以容纳客人的最大值

Example

input

6
6 1
100010
6 2
000000
5 1
10101
3 1
001
2 2
00
1 1
0

output

1
2
0
1
1
1

Note

第1组案例的情况:
在举例中已给出
结果:"abac"

第2组案例的情况:
1. s1
2. s6
结果:2

第3组案例的情况:
结果:0


D. Task On The Board

》英文原题《

Polycarp wrote on the board a string s containing only lowercase Latin letters ('a'-'z'). This string is known for you and given in the input.

After that, he erased some letters from the string s, and he rewrote the remaining letters in any order. As a result, he got some new string t. You have to find it with some additional information.

Suppose that the string t has length m and the characters are numbered from left to right from 1 to m. You are given a sequence of m integers: b1,b2,…,bm, where bi is the sum of the distances |i−j| from the index i to all such indices j that tj>ti (consider that 'a'<'b'<...ti, thus b3=0;
since t4='b', only the index j=3 contains the letter, which is later in the alphabet, that is: b4=|4−3|=1.
Thus, if t = "abzb", then b=[6,1,0,1].

Given the string s and the array b, find any possible string t for which the following two requirements are fulfilled simultaneously:

t is obtained from s by erasing some letters (possibly zero) and then writing the rest in any order;
the array, constructed from the string t according to the rules above, equals to the array b specified in the input data.
Input
The first line contains an integer q (1≤q≤100) — the number of test cases in the test. Then q test cases follow.

Each test case consists of three lines:

the first line contains string s, which has a length from 1 to 50 and consists of lowercase English letters;
the second line contains positive integer m (1≤m≤|s|), where |s| is the length of the string s, and m is the length of the array b;
the third line contains the integers b1,b2,…,bm (0≤bi≤1225).
It is guaranteed that in each test case an answer exists.

Output

Output q lines: the k-th of them should contain the answer (string t) to the k-th test case. It is guaranteed that an answer to each test case exists. If there are several answers, output any.

Example

input

4
abac
3
2 1 0
abc
1
0
abba
3
1 0 1
ecoosdcefr
10
38 13 24 14 11 5 3 24 17 0

output

aac
b
aba
codeforces

Note

In the first test case, such strings t are suitable: "aac', "aab".

In the second test case, such trings t are suitable: "a", "b", "c".

In the third test case, only the string t equals to "aba" is suitable, but the character 'b' can be from the second or third position.


E. Necklace Assembly

》英文原题《

The store sells n beads. The color of each bead is described by a lowercase letter of the English alphabet ("a"–"z"). You want to buy some beads to assemble a necklace from them.

A necklace is a set of beads connected in a circle.

For example, if the store sells beads "a", "b", "c", "a", "c", "c", then you can assemble the following necklaces (these are not all possible options):

And the following necklaces cannot be assembled from beads sold in the store:

The first necklace cannot be assembled because it has three beads "a" (of the two available). The second necklace cannot be assembled because it contains a bead "d", which is not sold in the store.
We call a necklace k-beautiful if, when it is turned clockwise by k beads, the necklace remains unchanged. For example, here is a sequence of three turns of a necklace.

As you can see, this necklace is, for example, 3-beautiful, 6-beautiful, 9-beautiful, and so on, but it is not 1-beautiful or 2-beautiful.
In particular, a necklace of length 1 is k-beautiful for any integer k. A necklace that consists of beads of the same color is also beautiful for any k.

You are given the integers n and k, and also the string s containing n lowercase letters of the English alphabet — each letter defines a bead in the store. You can buy any subset of beads and connect them in any order. Find the maximum length of a k-beautiful necklace you can assemble.

Input

The first line contains a single integer t (1≤t≤100) — the number of test cases in the test. Then t test cases follow.

The first line of each test case contains two integers n and k (1≤n,k≤2000).

The second line of each test case contains the string s containing n lowercase English letters — the beads in the store.

It is guaranteed that the sum of n for all test cases does not exceed 2000.

Output

Output t answers to the test cases. Each answer is a positive integer — the maximum length of the k-beautiful necklace you can assemble.

Example

input

6
6 3
abcbac
3 6
aaa
7 1000
abczgyo
5 4
ababa
20 10
aaebdbabdbbddaadaadc
20 5
ecbedececacbcbccbdec

output

6
3
5
4
15
10

Note

The first test case is explained in the statement.

In the second test case, a 6-beautiful necklace can be assembled from all the letters.

In the third test case, a 1000-beautiful necklace can be assembled, for example, from beads "abzyo".

版权声明:本文为 溪月阁 | MoBrook 博主「 皓月 」的原创文章遵循用 CC BY-NC-SA 4.0 版权协议进行许可,转载请附上原文出处链接及本声明。

本文链接https://mobrook.cn/index.php/codeforces-1367/

上一篇:

下一篇: