Codeforces Round #798 (Div. 2)A~D

Problem - A - Codeforces

Kuznecov likes art, poetry, and music. And strings consisting of lowercase English letters.

Recently, Kuznecov has found two strings, a and b, of lengths n and m respectively. They consist of lowercase English letters and no character is contained in both strings.

Let another string c be initially empty. Kuznecov can do the following two types of operations:

Choose any character from the string a, remove it from a, and add it to the end of c.
Choose any character from the string b, remove it from b, and add it to the end of c.
But, he can not do more than k operations of the same type in a row. He must perform operations until either a or b becomes empty. What is the lexicographically smallest possible value of c after he finishes?

A string x is lexicographically smaller than a string y if and only if one of the following holds:

x is a prefix of y, but x≠y;
in the first position where x and y differ, the string x has a letter that appears earlier in the alphabet than the corresponding letter in y.

Input

There are several test cases in the input data. The first line contains a single integer t (1≤t≤100) — the number of test cases. This is followed by the test cases description.

The first line of each test case contains three integers n, m, and k (1≤n,m,k≤100) — parameters from the statement.

The second line of each test case contains the string a of length n.

The third line of each test case contains the string b of length m.

The strings contain only lowercase English letters. It is guaranteed that no symbol appears in a and b simultaneously.

Output

In each test case, output a single string c — the answer to the problem.

Example

input

3
6 4 2
aaaaaa
bbbb
5 9 3
caaca
bedededeb
7 7 1
noskill
wxhtzdy

output

aabaabaa
aaabbcc
dihktlwlxnyoz

Problem analysis

The title is , Here are two strings , You can select some characters from a string to delete , And then put these characters into a string , You can only select characters from a different string from the previous one at a time （ Last time I chose a, This time I can only choose b）, And you can only choose k Characters , End the operation until a string is empty , Ask the result of the smallest lexicographic order of the composed string .

First sort the two strings , Put small characters in front , Double pointers traverse the strings on both sides , As for which string to start with , It depends on who is small in the first character , Start with the small side , If the two sides are the same, there is no priority . When selecting a character in one string, compare it with the character in the other string , If it is small or equal, continue to choose , If it is large or the number of selected characters is greater than k It's over . If the first selected character is larger than the other string , Then let's just choose one （ At least choose one ）.

AC Code

#include<iostream>
using namespace std;
#include<vector>
#include<algorithm>
#include<math.h>
#include<set>
#include<numeric>
#include<string>
#include<string.h>
#include<iterator>
#include<map>
#include<unordered_map>
#include<stack>
#include<list>
#include<queue>
#include<iomanip>

#define endl '\n'
#define int ll
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll>PII;
const int N = 2e5 + 50;
int n, m;

bool cmp(PII a, PII b)
{
    return a.first > b.first;
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int t;
    cin >> t;
    while (t--)
    {
        int n, m, k;
        string a, b, c, d;
        cin >> n >> m >> k;
        cin >> a >> b;
        sort(a.begin(), a.end());
        sort(b.begin(), b.end());
        int l = 0, r = 0, st = -1;
        if (a[l] < b[r])st = 1;
        else st = 2;
        while (l < n && r < m)
        {
            if (st == 1)
            {
                st = 2;
                int ans = 0;
                while (l<n&&ans < k && a[l] < b[r])c += a[l++], ans++;
                if (ans == 0)c += a[l++];
            }
            else if (st == 2)
            {
                st = 1;
                int ans = 0;
                while (r<m&&ans < k && b[r] < a[l])c += b[r++], ans++;
                if (ans == 0)c += b[r++];
            }
        }
        
        cout << c << endl;
    }
    return 0;
}

Problem - B - Codeforces

Monocarp is a little boy who lives in Byteland and he loves programming.

Recently, he found a permutation of length n. He has to come up with a mystic permutation. It has to be a new permutation such that it differs from the old one in each position.

More formally, if the old permutation is p1,p2,…,pn and the new one is q1,q2,…,qn it must hold that
p1≠q1,p2≠q2,…,pn≠qn.
Monocarp is afraid of lexicographically large permutations. Can you please help him to find the lexicographically minimal mystic permutation?

Input

There are several test cases in the input data. The first line contains a single integer t (1≤t≤200) — the number of test cases. This is followed by the test cases description.

The first line of each test case contains a positive integer n (1≤n≤1000) — the length of the permutation.

The second line of each test case contains n distinct positive integers p1,p2,…,pn (1≤pi≤n). It’s guaranteed that p is a permutation, i. e. pi≠pj for all i≠j.

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

Output

For each test case, output n positive integers — the lexicographically minimal mystic permutations. If such a permutation does not exist, output −1 instead.

Example

input

4
3
1 2 3
5
2 3 4 5 1
4
2 3 1 4
1
1

output

2 3 1
1 2 3 4 5
1 2 4 3
-1

Problem analysis

The title is to give you an array , Let you reorder this array , The number in each position cannot be the same as before , What is the lowest result of such a typesetting sequence .

Sort the array first , Just put the small numbers in front . Then compare it in turn to see if it is the same as before , Decide if it's different , Just find the number that is not equal to the previous position in the following number and Exchange . If none of the following numbers meet the conditions , We will exchange different numbers from the set numbers （ The exchange of past numbers cannot be the same as before ）, If you still can't find it, it means you can't be satisfied , Output -1.

AC Code

#include<iostream>
using namespace std;
#include<vector>
#include<algorithm>
#include<math.h>
#include<set>
#include<numeric>
#include<string>
#include<string.h>
#include<iterator>
#include<map>
#include<unordered_map>
#include<stack>
#include<list>
#include<queue>
#include<iomanip>

#define endl '\n'
#define int ll
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll>PII;
const int N = 2e5 + 50;
int n, m;

bool cmp(PII a, PII b)
{
    return a.first > b.first;
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int t;
    cin >> t;
    while (t--)
    {
        int n, res = 0;
        cin >> n;
        vector<int>a(n), b(n), mymap(n);
        for (int i = 0; i < n; i++)cin >> a[i];
        bool flag = true;
        for (int i = 0; i < n; i++)
        {
            int ans = 1e9, pos = -1;
            for (int j = 0; j < n; j++)
            {
                if (mymap[j] == 0 && a[i] != a[j])
                {
                    if (ans > a[j])
                    {
                        ans = a[j];
                        pos = j;
                    }
                }
            }
            if (ans == 1e9)
            {
                bool st = false;
                for (int j = res - 1; j >= 0; j--)
                {
                    if (a[i] != b[j] && a[j] != a[i])
                    {
                        b[i] = b[j];
                        b[j] = a[i];
                        mymap[i] = 1;
                        st = true;
                        break;
                    }
                }
                if (!st)
                {
                    flag = false;
                    break;
                }
            }
            else
            {
                b[i] = ans, res++;
                mymap[pos] = 1;
            }
        }
        if (flag)
        {
            for (auto i : b)cout << i << " ";
            cout << endl;
        }
        else cout << -1 << endl;
    }
    return 0;
}

Problem - C - Codeforces

Byteland is a beautiful land known because of its beautiful trees.

Misha has found a binary tree with n vertices, numbered from 1 to n. A binary tree is an acyclic connected bidirectional graph containing n vertices and n−1 edges. Each vertex has a degree at most 3, whereas the root is the vertex with the number 1 and it has a degree at most 2.

Unfortunately, the root got infected.

The following process happens n times:

Misha either chooses a non-infected (and not deleted) vertex and deletes it with all edges which have an end in this vertex or just does nothing.
Then, the infection spreads to each vertex that is connected by an edge to an already infected vertex (all already infected vertices remain infected).
As Misha does not have much time to think, please tell him what is the maximum number of vertices he can save from the infection (note that deleted vertices are not counted as saved).

Input

There are several test cases in the input data. The first line contains a single integer t (1≤t≤5000) — the number of test cases. This is followed by the test cases description.

The first line of each test case contains one integer n (2≤n≤3⋅10^ 5) — the number of vertices of the tree.

The i-th of the following n−1 lines in the test case contains two positive integers ui and vi (1≤ui,vi≤n), meaning that there exists an edge between them in the graph.

It is guaranteed that the graph is a binary tree rooted at 1. It is also guaranteed that the sum of n over all test cases won’t exceed 3⋅10^ 5.

Output

For each test case, output the maximum number of vertices Misha can save.

Example

input

4
2
1 2
4
1 2
2 3
2 4
7
1 2
1 5
2 3
2 4
5 6
5 7
15
1 2
2 3
3 4
4 5
4 6
3 7
2 8
1 9
9 10
9 11
10 12
10 13
11 14
11 15

output

0
2
2
10

Problem analysis

The title is that there is a binary tree , Its root node is polluted , Each time a contaminated node pollutes the node directly connected to it , You can kill one uncontaminated node at a time , In this way, the child nodes of this node will not be polluted , Ask how many nodes you can save in the end .

You can go through it first dfs How many nodes does the subtree of each node have at one time （ It is equivalent to cutting down the number of nodes that can be saved ）, By the way, classify the left and right child nodes of each node （ At the beginning, the link will not be divided into left and right subtrees , Let's divide by ourselves ）.

Then there is the node saved by calculation , Each time we can choose to cut off the left node or the right node , If you cut off the left node , Then we can save all the nodes on the left , Then the subtree on the right will be polluted , Let's look at the two subtrees of the right subtree to decide which side of the node to cut , namely ：

max(dfs(root->left)+size[root->right],dfs(root->right)+size[root->left]);

AC Code

#include<iostream>
using namespace std;
#include<vector>
#include<algorithm>
#include<math.h>
#include<set>
#include<numeric>
#include<string>
#include<string.h>
#include<iterator>
#include<map>
#include<unordered_map>
#include<stack>
#include<list>
#include<queue>
#include<iomanip>

#define endl '\n'
#define int ll
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll>PII;
const int N = 2e5 + 50;
unordered_map<int, PII>ans;
unordered_map<int, int>mysize;
unordered_map<int, vector<int>>mymap;

int dfs(int x,int y)
{
    if (x == 0)return 0;
    int res = 0, st = 1;
    for (auto i : mymap[x])
    {
        if (i != y)
        {
            if (st == 1)
            {
                st = 2;
                ans[x].first = i;
                res += dfs(i, x);
            }
            else
            {
                ans[x].second = i;
                res += dfs(i, x);
            }
        }
    }
    mysize[x] = res;
    return res + 1;
}

int dfs2(int x)
{
    if (x == 0)return 0;
    int res = 0;
    res = max(res, mysize[ans[x].second] + dfs2(ans[x].first));
    
    res = max(res, mysize[ans[x].first] + dfs2(ans[x].second));
    
    return res;
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int t;
    cin >> t;
    while (t--)
    {
        ans.clear();
        mysize.clear();
        mymap.clear();

        int n, a, b;
        cin >> n;
        vector<int>v(n);  
        for (int i = 0; i < n-1; i++)
        {
            cin >> a >> b;
            mymap[a].push_back(b);
            mymap[b].push_back(a);
        }
        int res = 0;
        dfs(1, 0);
        res=dfs2(1);
        
        cout << res << endl;
    }
    return 0;
}

Problem - D - Codeforces

Lena is a beautiful girl who likes logical puzzles.

As a gift for her birthday, Lena got a matrix puzzle!

The matrix consists of n rows and m columns, and each cell is either black or white. The coordinates (i,j) denote the cell which belongs to the i-th row and j-th column for every 1≤i≤n and 1≤j≤m. To solve the puzzle, Lena has to choose a cell that minimizes the Manhattan distance to the farthest black cell from the chosen cell.

More formally, let there be k≥1 black cells in the matrix with coordinates (xi,yi) for every 1≤i≤k. Lena should choose a cell (a,b) that minimizes
$$max=(|a-xi|+|b-yi|).$$
As Lena has no skill, she asked you for help. Will you tell her the optimal cell to choose?

Input

There are several test cases in the input data. The first line contains a single integer t (1≤t≤10000) — the number of test cases. This is followed by the test cases description.

The first line of each test case contains two integers n and m (2≤n,m≤1000) — the dimensions of the matrix.

The following n lines contain m characters each, each character is either ‘W’ or ‘B’. The j-th character in the i-th of these lines is ‘W’ if the cell (i,j) is white, and ‘B’ if the cell (i,j) is black.

It is guaranteed that at least one black cell exists.

It is guaranteed that the sum of n⋅m does not exceed 106.

Output

For each test case, output the optimal cell (a,b) to choose. If multiple answers exist, output any.

Example

input

5
3 2
BW
WW
WB
3 3
WWB
WBW
BWW
2 3
BBB
BBB
5 5
BWBWB
WBWBW
BWBWB
WBWBW
BWBWB
9 9
WWWWWWWWW
WWWWWWWWW
BWWWWWWWW
WWWWWWWWW
WWWWBWWWW
WWWWWWWWW
WWWWWWWWW
WWWWWWWWW
WWWWWWWWB

output

2 1
2 2
1 2
3 3
6 5

Problem analysis

The problem is that , There is a matrix consisting of white dots （W） And black spots （B） form , Let you find a point , Minimize the distance from this point to the farthest black spot .

In fact, we can directly find the farthest black spot , There are only four farthest black spots , It's the top left 、 Sit down 、 The upper right 、 Points in the four directions at the bottom right , We just need to find out these four points , Then enumerate the farthest distance from all points to these four points , Choose the point with the longest distance and the smallest .

AC Code

#include<iostream>
using namespace std;
#include<vector>
#include<algorithm>
#include<math.h>
#include<set>
#include<numeric>
#include<string>
#include<string.h>
#include<iterator>
#include<map>
#include<unordered_map>
#include<stack>
#include<list>
#include<queue>
#include<iomanip>

#define endl '\n'
#define int ll
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll>PII;
const int N = 2e5 + 50;

bool cmp(PII a, PII b)
{
    if (a.first != b.first)return a.first < b.first;
    return a.second > b.second;
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int t;
    cin >> t;
    while (t--)
    {
        int n, m;
        cin >> n >> m;
        vector<string>v(n);
        PII a = { 1e9,1e9 }, b = { -1,-1 }, c = { 0,1e9 }, d = { 1e9,0 };
        for (int i = 0; i < n; i++)
        {
            cin >> v[i];
            for (int j = 0; j < m; j++)
            {
                if (v[i][j] == 'B')
                {
                    if (i + j <= a.first + a.second)a = { i,j };
                    if (i + j >= b.first + b.second)b = { i,j };
                    if (i - j >= c.first - c.second)c = { i,j };
                    if (i - j <= d.first - d.second)d = { i,j };
                }
            }
        }
        
        int dis = 1e9, x = -1, y = -1;
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < m; j++)
            {
                int res = 0;
                res = max(res, abs(i - a.first) + abs(j - a.second));
                res = max(res, abs(i - b.first) + abs(j - b.second));
                res = max(res, abs(i - c.first) + abs(j - c.second));
                res = max(res, abs(i - d.first) + abs(j - d.second));
                if (res < dis)
                {
                    dis = res;
                    x = i;
                    y = j;
                }
            }
        }
        cout << x + 1 << " " << y + 1 << endl;
    }
    return 0;
}