1931A - Recovering a Small String
Разбор
Tutorial is loading...
Решение
#include<bits/stdc++.h>
using namespace std;
void solve(){
int n, sz = 26;
cin >> n;
string mins = "zzz", cur;
for(int i = 0; i < sz; i++){
for(int j = 0; j < sz; j++){
for(int k = 0; k < sz; k++){
if(i + j + k + 3 == n){
cur += char(i + 'a');
cur += char(j + 'a');
cur += char(k + 'a');
mins = min(cur, mins);
}
}
}
}
cout << mins << "\n";
}
int main(){
int t;
cin >> t;
while(t--) {
solve();
}
}
Идея: MikeMirzayanov Разработка: Vladosiya
Разбор
Tutorial is loading...
Решение
def solve():
n = int(input())
a = [int(x) for x in input().split()]
k = sum(a) // n
for i in range(n - 1):
if a[i] < k:
print('NO')
return
a[i + 1] += a[i] - k
a[i] = k
print('YES')
for _ in range(int(input())):
solve()
Идея: senjougaharin Разработка: senjougaharin
Разбор
Tutorial is loading...
Решение
def solve():
n = int(input())
a = list(map(int, input().split()))
i1 = 0
i2 = 0
while i1 < n and a[i1] == a[0]:
i1 += 1
while i2 < n and a[n - i2 - 1] == a[n - 1]:
i2 += 1
res = n
if a[0] == a[n - 1]:
res -= i1
res -= i2
else:
res -= max(i1, i2)
print(max(0, res))
t = int(input())
for i in range(t):
solve()
Идея: MikeMirzayanov Разработка: Vladosiya
Разбор
Tutorial is loading...
Решение
def solve():
n, x, y = map(int, input().split())
a = [int(x) for x in input().split()]
cnt = dict()
ans = 0
for e in a:
xx, yy = e % x, e % y
ans += cnt.get(((x - xx) % x, yy), 0)
cnt[(xx, yy)] = cnt.get((xx, yy), 0) + 1
print(ans)
for _ in range(int(input())):
solve()
1931E - Anna and the Valentine's Day Gift
Идея: Gornak40 Разработка: Gornak40
Разбор
Tutorial is loading...
Решение
#include <bits/stdc++.h>
#define all(arr) arr.begin(), arr.end()
using namespace std;
const int MAXN = 200200;
int n, m;
string arr[MAXN];
int len[MAXN], zrr[MAXN];
void build() {
memset(zrr, 0, sizeof(*zrr) * n);
for (int i = 0; i < n; ++i) {
len[i] = arr[i].size();
for (auto it = arr[i].rbegin(); it != arr[i].rend() && *it == '0'; ++it) {
++zrr[i];
}
}
}
string solve() {
int ans = 0;
for (int i = 0; i < n; ++i) {
ans += len[i] - zrr[i];
}
sort(zrr, zrr + n);
reverse(zrr, zrr + n);
for (int i = 0; i < n; ++i) {
if (i & 1) ans += zrr[i];
}
return (ans - 1 >= m ? "Sasha" : "Anna");
}
int main() {
int t; cin >> t;
while (t--) {
cin >> n >> m;
for (int i = 0; i < n; ++i)
cin >> arr[i];
build();
cout << solve() << '\n';
}
}
Идея: senjougaharin Разработка: senjougaharin
Разбор
Tutorial is loading...
Решение
#include <iostream>
#include <vector>
#include <set>
#include <queue>
#include <algorithm>
using namespace std;
typedef long long ll;
int timer = 0;
void dfs(int v, vector<vector<int>> &g, vector<bool> &vis, vector<int> &tout) {
vis[v] = true;
for (int u: g[v]) {
if (!vis[u]) {
dfs(u, g, vis, tout);
}
}
tout[v] = timer++;
}
void solve() {
timer = 0;
int n, k;
cin >> n >> k;
vector<vector<int>> a(k, vector<int>(n));
vector<int> authors(k);
for (int i = 0; i < k; ++i) {
for (int j = 0; j < n; ++j) {
cin >> a[i][j];
a[i][j]--;
}
authors[i] = a[i][0];
}
vector<vector<int>> g(n);
for (int i = 0; i < k; ++i) {
for (int j = 1; j + 1 < n; ++j) {
int i1 = a[i][j], i2 = a[i][j + 1];
g[i1].push_back(i2);
}
}
vector<int> tout(n, -1);
vector<bool> vis(n);
for (int i = 0; i < n; ++i) {
if (tout[i] == -1) {
dfs(i, g, vis, tout);
}
}
for (int i = 0; i < k; ++i) {
for (int j = 1; j + 1 < n; ++j) {
int i1 = a[i][j], i2 = a[i][j + 1];
if (tout[i1] < tout[i2]) {
cout << "NO";
return;
}
}
}
cout << "YES";
}
int main() {
int t;
cin >> t;
for (int _ = 0; _ < t; ++_) {
solve();
cout << "\n";
}
}
1931G - One-Dimensional Puzzle
Идея: senjougaharin Разработка: senjougaharin
Разбор
Tutorial is loading...
Решение
#include <iostream>
#include <vector>
#include <set>
#include <queue>
#include <algorithm>
using namespace std;
typedef long long ll;
const int mod = 998244353;
ll pow_mod(ll x, ll p) {
if (p == 0) {
return 1;
}
if (p % 2 == 0) {
ll y = pow_mod(x, p / 2);
return (y * y) % mod;
}
return (x * pow_mod(x, p - 1)) % mod;
}
ll inv(ll x) {
return pow_mod(x, mod - 2);
}
vector<ll> fact = {1};
ll cnk(ll n, ll k) {
ll res = fact[n];
res = (res * inv(fact[k])) % mod;
res = (res * inv(fact[n - k])) % mod;
return res;
}
ll calc(int n1, int n2, int n3, int n4) {
return (cnk(n1 + n3 - 1, n3) * cnk(n2 + n4 - 1, n4)) % mod;
}
void solve() {
int n1, n2, n3, n4;
cin >> n1 >> n2 >> n3 >> n4;
if (n1 + n2 == 0) {
cout << (n3 == 0 || n4 == 0 ? 1 : 0) << '\n';
return;
}
if (abs(n1 - n2) > 1) {
cout << "0\n";
return;
}
ll res = 0;
if (n1 <= n2) {
res += calc(n1 + 1, n2, n3, n4);
}
if (n2 <= n1) {
res += calc(n1, n2 + 1, n3, n4);
}
cout << res % mod << '\n';
}
int main() {
for (ll i = 1; i <= 4e6; ++i) {
fact.push_back((fact.back() * i) % mod);
}
int t;
cin >> t;
for (int _ = 0; _ < t; ++_) {
solve();
}
}