Codeforces

A. Strange Table

Polycarp found a rectangular table consisting of $𝑛$ rows and $𝑚$ columns. He noticed that each cell of the table has its number, obtained by the following algorithm “by columns”:

• cells are numbered starting from one;
• cells are numbered from left to right by columns, and inside each column from top to bottom;
• number of each cell is an integer one greater than in the previous cell.

For example, if $𝑛=3$ and $𝑚=5$, the table will be numbered as follows:

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

However, Polycarp considers such numbering inconvenient. He likes the numbering “by rows”:

• cells are numbered starting from one;
• cells are numbered from top to bottom by rows, and inside each row from left to right;
• number of each cell is an integer one greater than the number of the previous cell.

For example, if $𝑛=3$ and $𝑚=5$, then Polycarp likes the following table numbering:

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

Polycarp doesn’t have much time, so he asks you to find out what would be the cell number in the numbering “by rows”, if in the numbering “by columns” the cell has the number $𝑥$?

Input

The first line contains a single integer $𝑡$ $(1≤𝑡≤10^4)$. Then $𝑡$ test cases follow.

Each test case consists of a single line containing three integers $𝑛, 𝑚, 𝑥$ $(1≤𝑛,𝑚≤10^6, 1≤𝑥≤𝑛⋅𝑚)$, where $𝑛$ and $𝑚$ are the number of rows and columns in the table, and $𝑥$ is the cell number.

Note that the numbers in some test cases do not fit into the $32$-bit integer type, so you must use at least the $64$-bit integer type of your programming language.

Output

For each test case, output the cell number in the numbering $”by rows”$.

풀이

코드

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

void solve() {
    ll n, m, x; cin >> n >> m >> x;
    ll div = (x - 1) / n, mod = (x - 1) % n;
    cout << m * mod + div + 1 << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t; cin >> t;
    while(t--) solve();
    return 0;
}

B. Partial Replacement

You are given a number $𝑘$ and a string $𝑠$ of length $𝑛$, consisting of the characters '.' and '*'. You want to replace some of the '*' characters with 'x' characters so that the following conditions are met:

• The first character '*' in the original string should be replaced with 'x';
• The last character '*' in the original string should be replaced with 'x';
• The distance between two neighboring replaced characters 'x' must not exceed $𝑘$ (more formally, if you replaced characters at positions $𝑖$ and $𝑗$ $(𝑖<𝑗)$ and at positions $[𝑖+1,𝑗−1]$ there is no "x" symbol, then $𝑗−𝑖$ must be no more than $𝑘$).

For example, if $𝑛=7$, $𝑠=$.**.*** and $𝑘=3$, then the following strings will satisfy the conditions above:

• .xx.*xx;
• .x*.x*x;
• .xx.xxx.

But, for example, the following strings will not meet the conditions:

• .**.*xx (the first character '*' should be replaced with 'x');
• .x*.xx* (the last character '*' should be replaced with 'x');
• .x*.*xx (the distance between characters at positions $2$ and $6$ is greater than $𝑘=3$).

Given $𝑛$, $𝑘$, and $𝑠$, find the minimum number of '*' characters that must be replaced with 'x' in order to meet the above conditions.

Input

The first line contains one integer $𝑡$ $(1≤𝑡≤500)$. Then $𝑡$ test cases follow.

The first line of each test case contains two integers $𝑛$ and $𝑘$ $(1≤𝑘≤𝑛≤50)$.

The second line of each test case contains a string $𝑠$ of length$𝑛$, consisting of the characters '.' and '*'.

It is guaranteed that there is at least one '*' in the string $𝑠$.

It is guaranteed that the distance between any two neighboring '*' characters does not exceed $𝑘$.

Output

For each test case output the minimum number of '*' characters that must be replaced with 'x' characters in order to satisfy the conditions above.

풀이

코드

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

void solve() {
    int n, k; cin >> n >> k;
    string s; cin >> s;
    int begin = 0, end = 0;
    for (int i = 0; i < (int) s.size(); i++) {
        if (s[i] == '*') { begin = i; break; }
    }
    for (int i = (int) s.size(); i >= 0; i--) {
        if (s[i] == '*') { end = i; break; }
    }
    if (begin == end) { cout << "1\n"; return; }
    int cnt = 1;
    s[begin] = 'x';
    for (int i = 0; i < (int) s.size(); i++) {
        if (s[i] == 'x') {
            for (int j = k; j >= 1; j--) {
                if (i + j < (int) s.size() && s[i + j] == '*') {
                    s[i + j] = 'x';
                    cnt++;
                    i += j - 1;
                    break;
                }
            }
        }
    }
    if (s[end] == '*') cnt++;
    cout << cnt << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t; cin >> t;
    while(t--) solve();
    return 0;
}

C. Double-ended Strings

You are given the strings $𝑎$ and $𝑏$, consisting of lowercase Latin letters. You can do any number of the following operations in any order:

• if $|𝑎|>0$ (the length of the string $𝑎$ is greater than zero), delete the first character of the string $𝑎$, that is, replace $𝑎$ with $𝑎_2𝑎_3…𝑎_𝑛$;
• if $|𝑎|>0$, delete the last character of the string $𝑎$, that is, replace $𝑎$ with $𝑎_1𝑎_2…𝑎_{𝑛−1}$;
• if $|𝑏|>0$ (the length of the string $𝑏$ is greater than zero), delete the first character of the string $𝑏$, that is, replace $𝑏$ with $𝑏_2𝑏_3…𝑏_𝑛$;
• if $|𝑏|>0$, delete the last character of the string $𝑏$, that is, replace $𝑏$ with $𝑏_1𝑏_2…𝑏_{𝑛−1}$.

Note that after each of the operations, the string $𝑎$ or $𝑏$ may become empty.

For example, if $𝑎=$"hello" and $𝑏=$"icpc", then you can apply the following sequence of operations:

• delete the first character of the string $𝑎$ ⇒ $𝑎=$"ello" and $𝑏=$"icpc";
• delete the first character of the string $𝑏$ ⇒ $𝑎=$"ello" and $𝑏=$"cpc";
• delete the first character of the string $𝑏$ ⇒ $𝑎=$"ello" and $𝑏=$"pc";
• delete the last character of the string $𝑎$ ⇒ $𝑎=$"ell" and $𝑏=$"pc";
• delete the last character of the string $𝑏$ ⇒ $𝑎=$"ell" and $𝑏=$"p".

For the given strings $𝑎$ and $𝑏$, find the minimum number of operations for which you can make the strings $𝑎$ and $𝑏$ equal. Note that empty strings are also equal.

Input

The first line contains a single integer $𝑡$ $(1≤𝑡≤100)$. Then $𝑡$ test cases follow.

The first line of each test case contains the string $𝑎$ $(1≤|𝑎|≤20)$, consisting of lowercase Latin letters.

The second line of each test case contains the string $𝑏$ $(1≤|𝑏|≤20)$, consisting of lowercase Latin letters.

Output

For each test case, output the minimum number of operations that can make the strings $𝑎$ and $𝑏$ equal.

풀이

코드

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

void solve() {
    string a; cin >> a;
    string b; cin >> b;
    int mx = 0;
    int aSize = (int) a.size();
    int bSize = (int) b.size();
    for (int i = 0; i < aSize; i++) {
        for (int j = 0; j < bSize; j++) {
            if (a[i] == b[j]) {
                int temp = 1;
                for (int k = j + 1; k < bSize; k++) {
                    if (a[i + k - j] == b[k]) temp++;
                    else break;
                }
                mx = max(mx, temp);
            }
        }
    }
    int ans = aSize + bSize - mx - mx;
    cout << ans << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t; cin >> t;
    while(t--) solve();
    return 0;
}

D. Epic Transformation

You are given an array $𝑎$ of length $𝑛$ consisting of integers. You can apply the following operation, consisting of several steps, on the array $𝑎$ zero or more times:

• you select two different numbers in the array $𝑎_𝑖$ and $𝑎_𝑗$;
• you remove $𝑖$-th and $𝑗$-th elements from the array.

For example, if $𝑛=6$ and $𝑎=[1,6,1,1,4,4]$, then you can perform the following sequence of operations:

• select $𝑖=1,𝑗=5$. The array $𝑎$ becomes equal to $[6,1,1,4]$;
• select $𝑖=1,𝑗=2$. The array $𝑎$ becomes equal to $[1,4]$.

What can be the minimum size of the array after applying some sequence of operations to it?

Input

The first line contains a single integer $𝑡$ $(1≤𝑡≤10^4)$. Then $𝑡$ test cases follow.

The first line of each test case contains a single integer $𝑛$ $(1≤𝑛≤2⋅10^5)$ is length of the array $𝑎$.

The second line of each test case contains $𝑛$ integers $𝑎_1,𝑎_2,…,𝑎_𝑛$ ($1≤𝑎_𝑖≤10^9)$.

It is guaranteed that the sum of $𝑛$ over all test cases does not exceed $2⋅10^5$.

Output

For each test case, output the minimum possible size of the array after applying some sequence of operations to it.

풀이 1

코드

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

void solve() {
    int n; cin >> n;
    map<int, int> mp;
    for (int i = 0; i < n; i++) {
        int a; cin >> a;
        mp[a]++;
    }
    vector<pair<int, int> > vp;
    for (auto iter = mp.begin(); iter != mp.end(); iter++) {
        vp.emplace_back(iter->second, iter->first);
    }
    sort(vp.begin(), vp.end(), greater<>());
    vector<int> v;
    for (int i = 0; i < (int) vp.size(); i++) {
        for (int j = 0; j < vp[i].first; j++) {
            v.push_back(vp[i].second);
        }
    }
    vector<int> ans(n + 1);
    int temp = 0;
    for (int i = 1; i <= n; i += 2) ans[i] = v[temp++];
    for (int i = 2; i <= n; i += 2) ans[i] = v[temp++];
    int res = 0;
    for (int i = 1; i < n; i += 2) {
        if (ans[i] == ans[i + 1]) res += 2;
    }
    if (n % 2 != 0) res++;
    cout << res << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t; cin >> t;
    while(t--) solve();
    return 0;
}

풀이 2

코드

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

void solve() {
    int n; cin >> n;
    map<int, int> mp;
    for (int i = 0; i < n; i++) {
        int a; cin >> a; mp[a]++;
    }
    int mx = 0;
    for(auto& iter : mp) mx = max(mx, iter.second);
    cout << max(n % 2, mx - (n - mx)) << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t; cin >> t;
    while(t--) solve();
    return 0;
}

https://codeforces.com/contest/1506