There is also a [Chinese version](https://cp-wiki.vercel.app/editorial/codeforces/1396).↵
↵
## [problem:1397A]↵
↵
Just count the number of every letter, and check whether every number can be divided by $N$.↵
↵
<spoiler summary="Code (Python 3)">↵
↵
~~~~~↵
from sys import stdin, stdout↵
↵
↵
def read_int():↵
return int(stdin.readline().strip())↵
↵
↵
t = read_int()↵
for case_num in range(t):↵
n = read_int()↵
counter = [0 for _ in range(26)]↵
↵
for i in range(n):↵
s = stdin.readline().strip()↵
for c in s:↵
counter[ord(c) - ord('a')] += 1↵
ok = True↵
for count in counter:↵
if count % n != 0:↵
ok = False↵
break↵
stdout.write('YES\n' if ok else 'NO\n')↵
↵
~~~~~↵
↵
</spoiler>↵
↵
## [problem:1397B]↵
↵
First sort the array in ascending order, then enumerate $c$. We can constrain the range of $c$ by $c^{n-1}<=2\sum a_i$, otherwise, we can simply change all $a_i$ to $1$ and that will cost less.↵
↵
<spoiler summary="Code (Python 3)">↵
↵
~~~~~↵
from sys import stdin, stdout↵
↵
↵
def read_int():↵
return int(stdin.readline().strip())↵
↵
↵
def read_ints():↵
return map(int, stdin.readline().strip().split(' '))↵
↵
↵
n = read_int()↵
a = list(read_ints())↵
a.sort()↵
s = sum(a)↵
cost = s - n↵
j = 2↵
while pow(j, n - 1) <= s * 2:↵
b = [1]↵
for k in range(n - 1):↵
b.append(b[-1] * j)↵
tot = sum([abs(a[i] - b[i]) for i in range(n)])↵
cost = min(cost, tot)↵
j += 1↵
print(cost)↵
~~~~~↵
↵
</spoiler>↵
↵
## [problem:1396A]↵
↵
We can make use of the fact that $N-1$ and $N$ are coprime. First we operate on $[1,N-1]$ whose length is $N-1$, then we operate on $[2,N]$ whose length is also $N-1$. After two operations, we can make all numbers divided by $N$. Finally, we operate on $[1,N]$ whose length is $N$, and we can just add $-a_i$ to each $a_i$ ($a_i$ may have changed after the previous operations).↵
↵
Note that $N=1$ is an edge case.↵
↵
<spoiler summary="Code (C++)">↵
↵
~~~~~↵
#include <cstdio>↵
#include <iostream>↵
#include <vector>↵
↵
using namespace std;↵
typedef long long ll;↵
↵
template <typename T> void read(T &x) {↵
x = 0;↵
char c = getchar();↵
T sig = 1;↵
for (; !isdigit(c); c = getchar())↵
if (c == '-')↵
sig = -1;↵
for (; isdigit(c); c = getchar())↵
x = (x << 3) + (x << 1) + c - '0';↵
x *= sig;↵
}↵
↵
class Solution {↵
public:↵
void solve() {↵
int n;↵
read(n);↵
vector<ll> a(n);↵
for (int i = 0; i < n; ++i)↵
read(a[i]);↵
if (n == 1) {↵
printf("1 1\n%lld\n1 1\n1\n1 1\n-1\n", -a[0]);↵
return;↵
}↵
printf("1 %d\n", n - 1);↵
for (int i = 0; i < n - 1; ++i) {↵
ll r = (a[i] % n + n) % n;↵
a[i] += r * (n - 1);↵
printf("%lld ", r * (n - 1));↵
}↵
printf("\n2 %d\n", n);↵
for (int i = 1; i < n; ++i) {↵
ll r = (a[i] % n + n) % n;↵
a[i] += r * (n - 1);↵
printf("%lld ", r * (n - 1));↵
}↵
printf("\n1 %d\n", n);↵
for (ll num : a)↵
printf("%lld ", -num);↵
}↵
};↵
↵
int main() {↵
ios::sync_with_stdio(false);↵
cin.tie(0);↵
Solution solution = Solution();↵
solution.solve();↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
## [problem:1396B]↵
↵
If $\max a_i>\sum a_i - \max a_i$, then T can always win. He can just take stones from the largest pile, while HL can only take from the rest piles. Since $\max a_i>\sum a_i - \max a_i$, there is definitely a time when HL has no stone to take after T takes a stone.↵
↵
Otherwise, $\max a_i\leq\sum a_i - \max a_i$, then both players can avoid $\max a_i>\sum a_i - \max a_i$ with the following strategy:↵
↵
- If the maximum pile is currently available, just take from it↵
- Otherwise, it means that the maximum pile has just been taken, so we have $\max a_i\leq\sum a_i - \max a_i - 1$. No matter which pile we take a stone from, we will have $\max a_i\leq\sum a_i - \max a_i$ afterwards.↵
↵
So the winner depends on the parity of stones. If the total number of stones is odd, then T wins, otherwise HL wins.↵
↵
<spoiler summary="Code (C++)">↵
↵
~~~~~↵
#include <cstdio>↵
#include <iostream>↵
#include <vector>↵
↵
using namespace std;↵
↵
template <typename T> void read(T &x) {↵
x = 0;↵
char c = getchar();↵
T sig = 1;↵
for (; !isdigit(c); c = getchar())↵
if (c == '-')↵
sig = -1;↵
for (; isdigit(c); c = getchar())↵
x = (x << 3) + (x << 1) + c - '0';↵
x *= sig;↵
}↵
↵
class Solution {↵
public:↵
void solve() {↵
int n;↵
read(n);↵
vector<int> a(n);↵
int sum = 0, hi = 0;↵
for (int i = 0; i < n; ++i) {↵
read(a[i]);↵
sum += a[i];↵
hi = max(hi, a[i]);↵
}↵
if (hi > sum - hi) {↵
printf("T\n");↵
return;↵
}↵
printf(sum % 2 == 0 ? "HL\n" : "T\n");↵
}↵
};↵
↵
int main() {↵
ios::sync_with_stdio(false);↵
cin.tie(0);↵
int t;↵
read(t);↵
while (t--) {↵
Solution solution = Solution();↵
solution.solve();↵
}↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
## [problem:1396C]↵
↵
First, let's consider one level. We have two ways to clear all monsters:↵
↵
- Kill the boss with one shot. We use pistol to kill all normal monsters, then use AWP to kill the boss. The total time cost is $p[i]=a[i]\cdot r_1+r_3$.↵
- Kill the boss with two shots. We can use pistol to kill all normal monsters, and then attack the boss once. Or we can use the laser gun to kill all normal monsters while damaging the boss at the same time. Then we are forced to leave. The next time we reach this level, we use pistol again to kill the boss. If we only consider the time spent on reloading, the total time cost is $q[i]=\min((a[i]+1)\cdot r_1, r_2)+r_1$.↵
↵
Now we can consider the general route. Let's reflect on where we shall end.↵
↵
↵
↵
Supposing we end at $3$, our best choice should be like the figure above. That is to say, we first come to $3$, then we go to the other end and go back to $3$. Otherwise we will spend extra time on teleportation.↵
↵
So we can divide the total time cost into three parts. The time cost of $[1,2]$, the time cost of $[3,8]$ and the time cost of moving from $2$ to $3$ which is $d$.↵
↵
Let $L[i]$ be the minimal time to clear $[1,i]$ and stop at level $i$, $R[i]$ be the minimal time to clear $[i,N]$ and stop at level $i$, our final answer would be↵
↵
$$↵
\min_{i=1}^NL[i]+R[i+1]+d↵
$$↵
↵
In order to avoid edge cases, we can let $L[0]=R[N+1]=-d$.↵
↵
Then we need to solve $L[i]$ and $R[i]$.↵
↵
$R[n]$ is special because there are no further levels. We can choose to kill all monsters in $p[n]$, or use the teleportation twice and spend $q[n]+2d$. For rest $R[i]$, since we need to go from $i$ to $i+1$ and then go back to $i$, so we must have passed level $i$ twice. So the total time cost is ↵
↵
$$↵
R[i]=R[i+1]+2d+\min(p[i],q[i])↵
$$↵
↵
Then we will consider $L[i]$. For $L[i]$, we have two strategies.↵
↵
1. Not going back. We go from level $i-1$ to level $i$ then kill all monsters, using $L[i-1]+d+p[i]$.↵
2. Going back. We take the route $i-2\rightarrow i-1\rightarrow i\rightarrow i-1\rightarrow i$. Since we have passed level $i-1$ and $i$ twice, we can use both $p[i-1]$ and $q[i-1]$, and $p[i]$ and $q[i]$.↵
↵
Comparing the two strategies, we will have↵
↵
$$↵
L[i]=\min(L[i-1]+d+p[i],L[i-2]+4d+\min(p[i-1],q[i-1])+\min(p[i],q[i]))↵
$$↵
↵
<spoiler summary="Why don't we consider going back further?">↵
↵
Consider route $i-3\rightarrow i-2\rightarrow i-1\rightarrow i\rightarrow i-1\rightarrow i-2\rightarrow i-1\rightarrow i$.↵
↵
It can be rearranged to $i-3\rightarrow i-2\rightarrow i-1\rightarrow i-2\rightarrow i-1\rightarrow i\rightarrow i-1\rightarrow i$, and the length does not change. Moreover, both routes pass level $i-2$, $i-1$ and $i$ at least twice. So these two routes come to the same optimal value. The second part of the rearranged route is just what we have considered ($i-2\rightarrow i-1\rightarrow i\rightarrow i-1\rightarrow i$), yet the first part of the rearranged route ($i-3\rightarrow i-2\rightarrow i-1\rightarrow i-2$) is no better than $L[i-2]$ so we do not need to consider it.↵
↵
</spoiler>↵
↵
We can then use the formula we come to earlier to calculate the final answer.↵
↵
<spoiler summary="Code (C++)">↵
~~~~~↵
#include <cstdio>↵
#include <iostream>↵
#include <vector>↵
↵
using namespace std;↵
typedef long long ll;↵
↵
template <typename T> void read(T &x) {↵
x = 0;↵
char c = getchar();↵
T sig = 1;↵
for (; !isdigit(c); c = getchar())↵
if (c == '-')↵
sig = -1;↵
for (; isdigit(c); c = getchar())↵
x = (x << 3) + (x << 1) + c — '0';↵
x *= sig;↵
}↵
↵
class Solution {↵
struct Node {↵
ll time = 0;↵
int idx = 0, left = 0;↵
bool operator<(const Node &other) const { return time > other.time; }↵
};↵
↵
public:↵
void solve() {↵
ll n, r1, r2, r3, d;↵
read(n), read(r1), read(r2), read(r3), read(d);↵
vector<ll> a(n + 1), kill_all(n + 1), leave_one(n + 1);↵
for (int i = 1; i <= n; ++i) {↵
read(a[i]);↵
kill_all[i] = r1 * a[i] + r3;↵
leave_one[i] = min(r2, r1 * (a[i] + 1)) + r1;↵
}↵
vector<ll> L(n + 2), R(n + 2);↵
R[n] = min(kill_all[n], leave_one[n] + d * 2);↵
for (int i = n — 1; i >= 1; --i)↵
R[i] = R[i + 1] + d * 2 + min(kill_all[i], leave_one[i]);↵
ll cost = R[1];↵
L[0] = R[n + 1] = -d;↵
for (int i = 1; i <= n; ++i) {↵
L[i] = L[i — 1] + d + min(kill_all[i], leave_one[i] + d * 2);↵
if (i >= 2)↵
L[i] = min(L[i], L[i — 2] + d * 4 +↵
min(kill_all[i — 1], leave_one[i — 1]) +↵
min(kill_all[i], leave_one[i]));↵
cost = min(cost, L[i] + R[i + 1] + d);↵
}↵
cout << cost;↵
}↵
};↵
↵
int main() {↵
ios::sync_with_stdio(false);↵
cin.tie(0);↵
Solution solution = Solution();↵
solution.solve();↵
}↵
~~~~~↵
↵
</spoiler>↵
↵
## [problem:1396D]↵
↵
Not yet.↵
↵
## [problem:1396E]↵
↵
Not yet.
↵
## [problem:1397A]↵
↵
Just count the number of every letter, and check whether every number can be divided by $N$.↵
↵
<spoiler summary="Code (Python 3)">↵
↵
~~~~~↵
from sys import stdin, stdout↵
↵
↵
def read_int():↵
return int(stdin.readline().strip())↵
↵
↵
t = read_int()↵
for case_num in range(t):↵
n = read_int()↵
counter = [0 for _ in range(26)]↵
↵
for i in range(n):↵
s = stdin.readline().strip()↵
for c in s:↵
counter[ord(c) - ord('a')] += 1↵
ok = True↵
for count in counter:↵
if count % n != 0:↵
ok = False↵
break↵
stdout.write('YES\n' if ok else 'NO\n')↵
↵
~~~~~↵
↵
</spoiler>↵
↵
## [problem:1397B]↵
↵
First sort the array in ascending order, then enumerate $c$. We can constrain the range of $c$ by $c^{n-1}<=2\sum a_i$, otherwise, we can simply change all $a_i$ to $1$ and that will cost less.↵
↵
<spoiler summary="Code (Python 3)">↵
↵
~~~~~↵
from sys import stdin, stdout↵
↵
↵
def read_int():↵
return int(stdin.readline().strip())↵
↵
↵
def read_ints():↵
return map(int, stdin.readline().strip().split(' '))↵
↵
↵
n = read_int()↵
a = list(read_ints())↵
a.sort()↵
s = sum(a)↵
cost = s - n↵
j = 2↵
while pow(j, n - 1) <= s * 2:↵
b = [1]↵
for k in range(n - 1):↵
b.append(b[-1] * j)↵
tot = sum([abs(a[i] - b[i]) for i in range(n)])↵
cost = min(cost, tot)↵
j += 1↵
print(cost)↵
~~~~~↵
↵
</spoiler>↵
↵
## [problem:1396A]↵
↵
We can make use of the fact that $N-1$ and $N$ are coprime. First we operate on $[1,N-1]$ whose length is $N-1$, then we operate on $[2,N]$ whose length is also $N-1$. After two operations, we can make all numbers divided by $N$. Finally, we operate on $[1,N]$ whose length is $N$, and we can just add $-a_i$ to each $a_i$ ($a_i$ may have changed after the previous operations).↵
↵
Note that $N=1$ is an edge case.↵
↵
<spoiler summary="Code (C++)">↵
↵
~~~~~↵
#include <cstdio>↵
#include <iostream>↵
#include <vector>↵
↵
using namespace std;↵
typedef long long ll;↵
↵
template <typename T> void read(T &x) {↵
x = 0;↵
char c = getchar();↵
T sig = 1;↵
for (; !isdigit(c); c = getchar())↵
if (c == '-')↵
sig = -1;↵
for (; isdigit(c); c = getchar())↵
x = (x << 3) + (x << 1) + c - '0';↵
x *= sig;↵
}↵
↵
class Solution {↵
public:↵
void solve() {↵
int n;↵
read(n);↵
vector<ll> a(n);↵
for (int i = 0; i < n; ++i)↵
read(a[i]);↵
if (n == 1) {↵
printf("1 1\n%lld\n1 1\n1\n1 1\n-1\n", -a[0]);↵
return;↵
}↵
printf("1 %d\n", n - 1);↵
for (int i = 0; i < n - 1; ++i) {↵
ll r = (a[i] % n + n) % n;↵
a[i] += r * (n - 1);↵
printf("%lld ", r * (n - 1));↵
}↵
printf("\n2 %d\n", n);↵
for (int i = 1; i < n; ++i) {↵
ll r = (a[i] % n + n) % n;↵
a[i] += r * (n - 1);↵
printf("%lld ", r * (n - 1));↵
}↵
printf("\n1 %d\n", n);↵
for (ll num : a)↵
printf("%lld ", -num);↵
}↵
};↵
↵
int main() {↵
ios::sync_with_stdio(false);↵
cin.tie(0);↵
Solution solution = Solution();↵
solution.solve();↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
## [problem:1396B]↵
↵
If $\max a_i>\sum a_i - \max a_i$, then T can always win. He can just take stones from the largest pile, while HL can only take from the rest piles. Since $\max a_i>\sum a_i - \max a_i$, there is definitely a time when HL has no stone to take after T takes a stone.↵
↵
Otherwise, $\max a_i\leq\sum a_i - \max a_i$, then both players can avoid $\max a_i>\sum a_i - \max a_i$ with the following strategy:↵
↵
- If the maximum pile is currently available, just take from it↵
- Otherwise, it means that the maximum pile has just been taken, so we have $\max a_i\leq\sum a_i - \max a_i - 1$. No matter which pile we take a stone from, we will have $\max a_i\leq\sum a_i - \max a_i$ afterwards.↵
↵
So the winner depends on the parity of stones. If the total number of stones is odd, then T wins, otherwise HL wins.↵
↵
<spoiler summary="Code (C++)">↵
↵
~~~~~↵
#include <cstdio>↵
#include <iostream>↵
#include <vector>↵
↵
using namespace std;↵
↵
template <typename T> void read(T &x) {↵
x = 0;↵
char c = getchar();↵
T sig = 1;↵
for (; !isdigit(c); c = getchar())↵
if (c == '-')↵
sig = -1;↵
for (; isdigit(c); c = getchar())↵
x = (x << 3) + (x << 1) + c - '0';↵
x *= sig;↵
}↵
↵
class Solution {↵
public:↵
void solve() {↵
int n;↵
read(n);↵
vector<int> a(n);↵
int sum = 0, hi = 0;↵
for (int i = 0; i < n; ++i) {↵
read(a[i]);↵
sum += a[i];↵
hi = max(hi, a[i]);↵
}↵
if (hi > sum - hi) {↵
printf("T\n");↵
return;↵
}↵
printf(sum % 2 == 0 ? "HL\n" : "T\n");↵
}↵
};↵
↵
int main() {↵
ios::sync_with_stdio(false);↵
cin.tie(0);↵
int t;↵
read(t);↵
while (t--) {↵
Solution solution = Solution();↵
solution.solve();↵
}↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
## [problem:1396C]↵
↵
First, let's consider one level. We have two ways to clear all monsters:↵
↵
- Kill the boss with one shot. We use pistol to kill all normal monsters, then use AWP to kill the boss. The total time cost is $p[i]=a[i]\cdot r_1+r_3$.↵
- Kill the boss with two shots. We can use pistol to kill all normal monsters, and then attack the boss once. Or we can use the laser gun to kill all normal monsters while damaging the boss at the same time. Then we are forced to leave. The next time we reach this level, we use pistol again to kill the boss. If we only consider the time spent on reloading, the total time cost is $q[i]=\min((a[i]+1)\cdot r_1, r_2)+r_1$.↵
↵
Now we can consider the general route. Let's reflect on where we shall end.↵
↵
↵
↵
Supposing we end at $3$, our best choice should be like the figure above. That is to say, we first come to $3$, then we go to the other end and go back to $3$. Otherwise we will spend extra time on teleportation.↵
↵
So we can divide the total time cost into three parts. The time cost of $[1,2]$, the time cost of $[3,8]$ and the time cost of moving from $2$ to $3$ which is $d$.↵
↵
Let $L[i]$ be the minimal time to clear $[1,i]$ and stop at level $i$, $R[i]$ be the minimal time to clear $[i,N]$ and stop at level $i$, our final answer would be↵
↵
$$↵
\min_{i=1}^NL[i]+R[i+1]+d↵
$$↵
↵
In order to avoid edge cases, we can let $L[0]=R[N+1]=-d$.↵
↵
Then we need to solve $L[i]$ and $R[i]$.↵
↵
$R[n]$ is special because there are no further levels. We can choose to kill all monsters in $p[n]$, or use the teleportation twice and spend $q[n]+2d$. For rest $R[i]$, since we need to go from $i$ to $i+1$ and then go back to $i$, so we must have passed level $i$ twice. So the total time cost is ↵
↵
$$↵
R[i]=R[i+1]+2d+\min(p[i],q[i])↵
$$↵
↵
Then we will consider $L[i]$. For $L[i]$, we have two strategies.↵
↵
1. Not going back. We go from level $i-1$ to level $i$ then kill all monsters, using $L[i-1]+d+p[i]$.↵
2. Going back. We take the route $i-2\rightarrow i-1\rightarrow i\rightarrow i-1\rightarrow i$. Since we have passed level $i-1$ and $i$ twice, we can use both $p[i-1]$ and $q[i-1]$, and $p[i]$ and $q[i]$.↵
↵
Comparing the two strategies, we will have↵
↵
$$↵
L[i]=\min(L[i-1]+d+p[i],L[i-2]+4d+\min(p[i-1],q[i-1])+\min(p[i],q[i]))↵
$$↵
↵
<spoiler summary="Why don't we consider going back further?">↵
↵
Consider route $i-3\rightarrow i-2\rightarrow i-1\rightarrow i\rightarrow i-1\rightarrow i-2\rightarrow i-1\rightarrow i$.↵
↵
It can be rearranged to $i-3\rightarrow i-2\rightarrow i-1\rightarrow i-2\rightarrow i-1\rightarrow i\rightarrow i-1\rightarrow i$, and the length does not change. Moreover, both routes pass level $i-2$, $i-1$ and $i$ at least twice. So these two routes come to the same optimal value. The second part of the rearranged route is just what we have considered ($i-2\rightarrow i-1\rightarrow i\rightarrow i-1\rightarrow i$), yet the first part of the rearranged route ($i-3\rightarrow i-2\rightarrow i-1\rightarrow i-2$) is no better than $L[i-2]$ so we do not need to consider it.↵
↵
</spoiler>↵
↵
We can then use the formula we come to earlier to calculate the final answer.↵
↵
<spoiler summary="Code (C++)">↵
~~~~~↵
#include <cstdio>↵
#include <iostream>↵
#include <vector>↵
↵
using namespace std;↵
typedef long long ll;↵
↵
template <typename T> void read(T &x) {↵
x = 0;↵
char c = getchar();↵
T sig = 1;↵
for (; !isdigit(c); c = getchar())↵
if (c == '-')↵
sig = -1;↵
for (; isdigit(c); c = getchar())↵
x = (x << 3) + (x << 1) + c — '0';↵
x *= sig;↵
}↵
↵
class Solution {↵
struct Node {↵
ll time = 0;↵
int idx = 0, left = 0;↵
bool operator<(const Node &other) const { return time > other.time; }↵
};↵
↵
public:↵
void solve() {↵
ll n, r1, r2, r3, d;↵
read(n), read(r1), read(r2), read(r3), read(d);↵
vector<ll> a(n + 1), kill_all(n + 1), leave_one(n + 1);↵
for (int i = 1; i <= n; ++i) {↵
read(a[i]);↵
kill_all[i] = r1 * a[i] + r3;↵
leave_one[i] = min(r2, r1 * (a[i] + 1)) + r1;↵
}↵
vector<ll> L(n + 2), R(n + 2);↵
R[n] = min(kill_all[n], leave_one[n] + d * 2);↵
for (int i = n — 1; i >= 1; --i)↵
R[i] = R[i + 1] + d * 2 + min(kill_all[i], leave_one[i]);↵
ll cost = R[1];↵
L[0] = R[n + 1] = -d;↵
for (int i = 1; i <= n; ++i) {↵
L[i] = L[i — 1] + d + min(kill_all[i], leave_one[i] + d * 2);↵
if (i >= 2)↵
L[i] = min(L[i], L[i — 2] + d * 4 +↵
min(kill_all[i — 1], leave_one[i — 1]) +↵
min(kill_all[i], leave_one[i]));↵
cost = min(cost, L[i] + R[i + 1] + d);↵
}↵
cout << cost;↵
}↵
};↵
↵
int main() {↵
ios::sync_with_stdio(false);↵
cin.tie(0);↵
Solution solution = Solution();↵
solution.solve();↵
}↵
~~~~~↵
↵
</spoiler>↵
↵
## [problem:1396D]↵
↵
Not yet.↵
↵
## [problem:1396E]↵
↵
Not yet.
