Educational Codeforces Round 164 (Rated for Div. 2)（A ~ E 视频讲解）

A. Painting the Ribbon

Problem Statement

Alice and Bob have bought a ribbon consisting of $n$ parts. Now they want to paint it.

First, Alice will paint every part of the ribbon into one of $m$ colors. For each part, she can choose its color arbitrarily.

Then, Bob will choose at most $k$ parts of the ribbon and repaint them into the same color (he chooses the affected parts and the color arbitrarily).

Bob would like all parts to have the same color. However, Alice thinks that this is too dull, so she wants to paint the ribbon in such a way that Bob cannot make all parts have the same color.

Is it possible to paint the ribbon in such a way?

Input

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

Each test case consists of one line containing three integers $n$, $m$ and $k$ ($1\le m,k\le n\le 50$) — the number of parts, the number of colors and the number of parts Bob can repaint, respectively.

Output

For each test case, print YES if Alice can paint the ribbon so that Bob cannot make all parts have the same color. Otherwise, print NO.

You can print every letter in any register. For example, Yes, yes, yEs will all be recognized as positive answer.

Example

Example

input
5
1 1 1
5 1 1
5 2 1
5 2 2
5 5 3

output
NO
NO
YES
NO
YES

Note

In the first test case, a ribbon consists of $1$ part. So all its parts will always have the same color.

In the second test case, there is only $1$ color.

In the third test case, Alice can paint the ribbon as follows: $[1,2,1,2,1]$. It’s impossible to change the color of at most $1$ part so that all parts have the same color.

In the fourth test case, no matter how Alice paints the ribbon, Bob will always be able to repaint $2$ parts so that all parts have the same color.

In the fifth test case, Alice can paint the ribbon as follows: $[1,2,3,4,5]$. It’s impossible to change the color of at most $3$ parts so that all parts have the same color.

Solution

具体见文后视频。

---

Code

#include <bits/stdc++.h>
#define fi first
#define se second
#define int long long

using namespace std;

typedef pair<int, int> PII;
typedef long long LL;

void solve() {
int n, m, k;
cin >> n >> m >> k;

if (k < n / m * (m - 1) + max(0ll, n % m - 1)) puts("YES");
else puts("NO");
}

signed main() {
cin.tie(0);
cout.tie(0);
ios::sync_with_stdio(0);

int dt;

cin >> dt;

while (dt --)
solve();

return 0;
}

---

B. Make It Ugly

Problem Statement

Let’s call an array $a$ beautiful if you can make all its elements the same by using the following operation an arbitrary number of times (possibly, zero):

• choose an index $i$ ($2\le i\le |a|-1$) such that $a_{i-1}=a_{i+1}$, and replace $a_i$ with $a_{i-1}$.

You are given a beautiful array $a_1,a_2,\dots ,a_n$. What is the minimum number of elements you have to remove from it in order for it to stop being beautiful? Swapping elements is prohibited. If it is impossible to do so, then output -1.

Input

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

The first line of each test case contains a single integer $n$ ($1\le n\le 3\cdot 10^5$).

The second line contains $n$ integers $a_1,a_2,\dots ,a_n$ ($1\le a_i\le n$).

Additional constraints on the input:

• in every test case, the given array $a$ is beautiful;
• the sum of $n$ over all test cases does not exceed $3\cdot 10^5$.

Output

For each test case, output a single integer — the minimum number of elements you have to remove from the array $a$ in order for it to stop being beautiful. If it is impossible, then output -1.

Example

Example

input
4
3
2 2 2
5
1 2 1 2 1
1
1
7
3 3 3 5 3 3 3

output
-1
1
-1
3

Note

In the first testcase, it is impossible to modify the array in such a way that it stops being beautiful. An array consisting of identical numbers will remain beautiful no matter how many numbers we remove from it.

In the second testcase, you can remove the number at the index $5$, for example.

The resulting array will be $[1,2,1,2]$. Let’s check if it is beautiful. Two operations are available:

• Choose $i=2$: the array becomes $[1,1,1,2]$. No more operations can be applied to it, and the numbers are not all the same.
• Choose $i=3$ instead: the array becomes $[1,2,2,2]$. No more operations can be applied to it either, and the numbers are still not all the same.

Thus, the array $[1,2,1,2]$ is not beautiful.

In the fourth testcase, you can remove the first three elements, for example. The resulting array $[5,3,3,3]$ is not beautiful.

Solution

具体见文后视频。

---

Code

#include <bits/stdc++.h>
#define fi first
#define se second
#define int long long

using namespace std;

typedef pair<int, int> PII;
typedef long long LL;

void solve() {
int n;
cin >> n;

std::vector<int> a(n + 2, 0);
unordered_map<int, int> cnt;
for (int i = 1; i <= n; i ++)
cin >> a[i], cnt[a[i]] ++;

int mx = 0, num;
for (auto v : cnt)
if (v.se > mx)
mx = v.se, num = v.fi;

for (int i = 1; i <= n; i ++)
if (a[i] != num && (a[i - 1] != num || a[i + 1] != num)) {
cout << 0 << endl;
return;
}
int res = 1e18, lst = 0;
for (int i = 1; i <= n; i ++)
if (a[i] != num) {
res = min({res, i - 1, n - i});
if (lst) res = min(res, i - lst - 1);
lst = i;
}
if (res == 1e18) cout << -1 << endl;
else cout << res << endl;
}

signed main() {
cin.tie(0);
cout.tie(0);
ios::sync_with_stdio(0);

int dt;

cin >> dt;

while (dt --)
solve();

return 0;
}

---

C. Long Multiplication

Problem Statement

You are given two integers $x$ and $y$ of the same length, consisting of digits from $1$ to $9$.

You can perform the following operation any number of times (possibly zero): swap the $i$-th digit in $x$ and the $i$-th digit in $y$.

For example, if $x=73$ and $y=31$, you can swap the $2$-nd digits and get $x=71$ and $y=33$.

Your task is to maximize the product of $x$ and $y$ using the aforementioned operation any number of times. If there are multiple answers, print any of them.

Input

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

The first line of each test case contains a single integer $x$ ($1\le x<10^{100}$).

The second line of each test case contains a single integer $y$ ($1\le y<10^{100}$).

Additional constraint on input: the integers $x$ and $y$ consist only of digits from $1$ to $9$.

Output

For each test case, print two lines — the first line should contain the number $x$ after performing the operations; similarly, the second line should contain the number $y$ after performing the operations. If there are multiple answers, print any of them.

Example

input
3
73
31
2
5
3516
3982

output
71
33
5
2
3912
3586

Solution

具体见文后视频。

---

Code

#include <bits/stdc++.h>
#define fi first
#define se second
#define int long long

using namespace std;

typedef pair<int, int> PII;
typedef long long LL;

void solve() {
string a, b;
cin >> a >> b;

int flg = 0;
string ra, rb;
for (int i = 0; i < a.size(); i ++) {
if (a[i] == b[i]) {
ra += a[i], rb += a[i];
} else if (a[i] > b[i]) {
if (flg == 1) ra += a[i], rb += b[i];
else if (flg == 2) ra += b[i], rb += a[i];
else ra += a[i], rb += b[i], flg = 2;
} else {
if (flg == 1) ra += b[i], rb += a[i];
else if (flg == 2) ra += a[i], rb += b[i];
else ra += b[i], rb += a[i], flg = 2;
}
// cout << flg << endl;
}
cout << ra << endl << rb << endl;
}

signed main() {
cin.tie(0);
cout.tie(0);
ios::sync_with_stdio(0);

int dt;

cin >> dt;

while (dt --)
solve();

return 0;
}

---

D. Colored Balls

Problem Statement

There are balls of $n$ different colors; the number of balls of the $i$-th color is $a_i$.

The balls can be combined into groups. Each group should contain at most $2$ balls, and no more than $1$ ball of each color.

Consider all $2^n$ sets of colors. For a set of colors, let’s denote its value as the minimum number of groups the balls of those colors can be distributed into. For example, if there are three colors with $3$, $1$ and $7$ balls respectively, they can be combined into $7$ groups (and not less than $7$), so the value of that set of colors is $7$.

Your task is to calculate the sum of values over all $2^n$ possible sets of colors. Since the answer may be too large, print it modulo $998244353$.

Input

The first line contains a single integer $n$ ($1\le n\le 5000$) — the number of colors.

The second line contains $n$ integers $a_1,a_2,\dots ,a_n$ ($1\le a_i\le 5000$) — the number of balls of the $i$-th color.

Additional constraint on input: the total number of balls doesn’t exceed $5000$.

Output

Print a single integer — the sum of values of all $2^n$ sets of colors, taken modulo $998244353$.

Example

Example

input
3
1 1 2

output
11

input
1
5

output
5

input
4
1 3 3 7

output
76

Note

Consider the first example. There are $8$ sets of colors:

• for the empty set, its value is $0$;
• for the set { 1 } \{1\} {1}, its value is $1$;
• for the set { 2 } \{2\} {2}, its value is $1$;
• for the set { 3 } \{3\} {3}, its value is $2$;
• for the set { 1 , 2 } \{1,2\} {1,2}, its value is $1$;
• for the set { 1 , 3 } \{1,3\} {1,3}, its value is $2$;
• for the set { 2 , 3 } \{2,3\} {2,3}, its value is $2$;
• for the set { 1 , 2 , 3 } \{1,2,3\} {1,2,3}, its value is $2$.

So, the sum of values over all $2^n$ sets of colors is $11$.

Solution

具体见文后视频。

Code

#include <bits/stdc++.h>
#define fi first
#define se second
#define int long long

using namespace std;

typedef pair<int, int> PII;
typedef long long LL;

const int MOD = 998244353;
int ksm(int a, int b) {
int res = 1;
while (b) {
if (b & 1) res = res * a % MOD;
a = a * a % MOD;
b >>= 1;
}
return res;
}
void exgcd(int a, int b, int &x, int &y) {
if (!b) {
x = 1, y = 0;
return;
}
exgcd(b, a % b, y, x);
y -= a / b * x;
}
struct Mint {
int v;
void assign(int x) {
v = x;
}
Mint operator+ (const Mint tmp)const {
Mint res;
res.v = (v + tmp.v) % MOD;
return res;
}
Mint operator+ (const int tmp)const {
Mint res;
res.v = (v + tmp) % MOD;
return res;
}
Mint operator- (const Mint tmp)const {
Mint res;
res.v = (v - tmp.v + MOD) % MOD;
return res;
}
Mint operator- (const int tmp)const {
Mint res;
res.v = (v - tmp + MOD) % MOD;
return res;
}
Mint operator* (const Mint tmp)const {
Mint res;
res.v = v * tmp.v % MOD;
return res;
}
Mint operator* (const int tmp)const {
Mint res;
res.v = v * tmp % MOD;
return res;
}
Mint operator/ (const Mint tmp)const {
int x, y;
exgcd(tmp.v, MOD, x, y), x = (x % MOD + MOD) % MOD;
Mint res;
res.v = v * x % MOD;
return res;
}
Mint operator/ (const int tmp)const {
int x, y;
exgcd(tmp, MOD, x, y), x = (x % MOD + MOD) % MOD;
Mint res;
res.v = v * x % MOD;
return res;
}
Mint operator^ (Mint b)const {
Mint ans;
ans.v = ksm(v, b.v);
return ans;
}
Mint operator^ (int b)const {
Mint ans;
ans.v = ksm(v, b);
return ans;
}
void read() {
string s;
cin >> s;
for (auto i : s)
v = (v * 10 + i - '0') % MOD;
}
};

const int N = 5e3 + 10;

int n;
int a[N];
Mint f[N][N];

signed main() {
cin.tie(0);
cout.tie(0);
ios::sync_with_stdio(0);

cin >> n;

int tot = 0;
for (int i = 1; i <= n; i ++)
cin >> a[i], tot += a[i];
sort(a + 1, a + 1 + n);

f[0][0].v = 1;
Mint res;
res.assign(0);
for (int i = 1; i <= n; i ++) {
for (int j = 0; j <= a[i]; j ++)
res = res + f[i - 1][j] * a[i];
for (int j = a[i] + 1; j <= tot; j ++)
res = res + f[i - 1][j] * ((j + a[i] + 1) / 2);
for (int j = 0; j <= tot; j ++) {
f[i][j] = f[i - 1][j];
if (j >= a[i]) f[i][j] = f[i][j] + f[i - 1][j - a[i]];
}
}

cout << res.v << endl;

return 0;
}

---

E. Chain Reaction

Problem Statement

There are $n$ monsters standing in a row. The $i$-th monster has $a_i$ health points.

Every second, you can choose one alive monster and launch a chain lightning at it. The lightning deals $k$ damage to it, and also spreads to the left (towards decreasing $i$) and to the right (towards increasing $i$) to alive monsters, dealing $k$ damage to each. When the lightning reaches a dead monster or the beginning/end of the row, it stops. A monster is considered alive if its health points are strictly greater than $0$.

For example, consider the following scenario: there are three monsters with health equal to $[5,2,7]$, and $k=3$. You can kill them all in $4$ seconds:

• launch a chain lightning at the $3$-rd monster, then their health values are $[2,-1,4]$;
• launch a chain lightning at the $1$-st monster, then their health values are $[-1,-1,4]$;
• launch a chain lightning at the $3$-rd monster, then their health values are $[-1,-1,1]$;
• launch a chain lightning at the $3$-th monster, then their health values are $[-1,-1,-2]$.

For each $k$ from $1$ to $\max (a_1,a_2,\dots ,a_n)$, calculate the minimum number of seconds it takes to kill all the monsters.

Input

The first line contains a single integer $n$ ($1\le n\le 10^5$) — the number of monsters.

The second line contains $n$ integers $a_1,a_2,\dots ,a_n$ ($1\le a_i\le 10^5$) — the health points of the $i$-th monster.

Output

For each $k$ from $1$ to $\max (a_1,a_2,\dots ,a_n)$, output the minimum number of seconds it takes to kill all the monsters.

Example

input
3
5 2 7

output
10 6 4 3 2 2 1

input
4
7 7 7 7

output
7 4 3 2 2 2 1

input
10
1 9 7 6 2 4 7 8 1 3

output
17 9 5 4 3 3 3 2 1

Solution

具体见文后视频。

---

Code

#include <bits/stdc++.h>
#define fi first
#define se second
#define int long long

using namespace std;

typedef pair<int, int> PII;
typedef long long LL;

const int N = 1e5 + 10;

int n;
int a[N], b[N];

signed main() {
cin.tie(0);
cout.tie(0);
ios::sync_with_stdio(0);

cin >> n;

int mx = 0;
for (int i = 1; i <= n; i ++) {
cin >> a[i], mx = max(mx, a[i]);
if (a[i] > a[i - 1]) b[a[i]] ++, b[a[i - 1]] --;
}
for (int i = 1; i <= mx; i ++)
b[i] += b[i - 1];
for (int k = 1; k <= mx; k ++) {
int res = 0;
for (int i = 1, j = k; i <= mx; i += k, j += k)
res += (b[min(j, mx)] - b[i - 1]) * (j / k);
cout << res << " ";
}

return 0;
}

---

视频讲解

---

最后祝大家早日

原文地址：https://blog.csdn.net/weixin_66946161/article/details/137747624

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！