Спасибо за участие!
Разбор
Tutorial is loading...
Код
#include<bits/stdc++.h>
using namespace std;
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
int tests;
cin >> tests;
while (tests--) {
int n, m;
cin >> n >> m;
vector<vector<int>> a(n, vector<int>(m));
for (auto &i: a) {
for (auto &j: i) cin >> j;
}
if (n * m == 1) cout << "-1\n";
else {
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
cout << a[(i + 1) % n][(j + 1) % m] << ' ';
}
cout << '\n';
}
}
}
}
Разбор
Tutorial is loading...
Код
#include<bits/stdc++.h>
using namespace std;
void solve() {
int n;
cin >> n;
string s, t;
cin >> s >> t;
for (int i = 0; i < s.size() && s[i] == '0'; ++i) {
if (t[i] != '0') {
cout << "NO\n";
return;
}
}
cout << "YES\n";
}
int main() {
int t;
cin >> t;
while (t--) solve();
}
Разбор
Tutorial is loading...
Код
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
int tests;
cin >> tests;
while (tests--) {
int n;
ll x;
cin >> n >> x;
vector<ll> a(n + 1);
for (int i = 1; i <= n; ++i) cin >> a[i];
partial_sum(a.begin() + 1, a.end(), a.begin() + 1);
vector<int> dp(n + 2);
for (int i = n - 1; i >= 0; --i) {
int q = upper_bound(a.begin(), a.end(), a[i] + x) - a.begin();
dp[i] = dp[q] + q - i - 1;
}
cout << accumulate(dp.begin(), dp.end(), 0ll) << '\n';
}
}
Подсказка
Pigeonhole principle
Разбор
Tutorial is loading...
Код
#include<bits/stdc++.h>
using namespace std;
int main() {
int tests;
cin >> tests;
while (tests--) {
int n;
cin >> n;
vector<int> a(n);
for (auto& i : a) cin >> i;
vector<int> pos(n);
iota(pos.begin(), pos.end(), 0);
vector<pair<int, int>> ans;
for (int i = n - 1; i; --i) {
vector<int> occ(i, -1);
for (auto j : pos) {
if (occ[a[j] % i] != -1) {
ans.emplace_back(j, occ[a[j] % i]);
pos.erase(find(pos.begin(), pos.end(), j));
break;
}
occ[a[j] % i] = j;
}
}
reverse(ans.begin(), ans.end());
cout << "YES\n";
for (auto [x, y] : ans) cout << x + 1 << ' ' << y + 1 << '\n';
}
}
Подсказка
Solve for one tree
Подсказка.ответ
Answer is size of tree
Подсказка.доказательство
Let sizes of deleted subtrees be $$$a_1, a_2, \ldots a_m$$$. We know that $$$a_1 + a_2 + \ldots + a_m = n$$$. Then we know that $$$a_1 | a_2 \ldots a_m \leq n$$$. To proof that lets see bits separately. It will add $$$1$$$ to result, if one of bits is $$$1$$$, $$$0$$$ otherwise, but this is not more than their sum.
Разбор
Tutorial is loading...
Код
#include<bits/stdc++.h>
using namespace std;
void solve() {
int k;
cin >> k;
vector<int> a(k);
for (int i = 0; i < k; ++i) {
cin >> a[i];
for (int j = 0; j < a[i] - 1; ++j) {
int trash;
cin >> trash;
}
}
sort(a.begin(), a.end(), greater<>());
int ans = 0;
for (auto x : a) {
for (int h = 23; h >= 0; --h) {
int ca = ans >> h & 1, cx = x >> h & 1;
if (cx == 0) continue;
if (ca == 0) ans |= 1 << h;
else {
ans |= (1 << h) - 1;
break;
}
}
}
cout << ans << '\n';
}
int main() {
int t;
cin >> t;
while (t--) solve();
}
Разбор
Tutorial is loading...
Код
#include<bits/stdc++.h>
using namespace std;
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
int tests;
cin >> tests;
while (tests--) {
int n, m;
cin >> n >> m;
vector<vector<int>> black(n);
vector<int> edg(m);
vector<vector<int>> g(n);
for (int i = 0; i < m; ++i) {
int x, y, c;
cin >> x >> y >> c;
--x, --y;
edg[i] = x ^ y;
g[x].push_back(i);
g[y].push_back(i);
if (c == 0) {
black[x].push_back(i);
black[y].push_back(i);
}
}
vector<int> deg(n);
for (int i = 0; i < n; ++i) deg[i] = g[i].size() & 1;
vector<bool> del(m, false), used(n, false);
auto dfs = [&](auto dfs, int u) -> void {
used[u] = true;
for (auto id : black[u]) {
int to = edg[id] ^ u;
if (used[to]) continue;
dfs(dfs, to);
if (deg[to]) {
del[id] = true;
deg[to] ^= 1;
deg[u] ^= 1;
}
}
};
bool ok = true;
for (int i = 0; i < n; ++i) {
if (used[i]) continue;
dfs(dfs, i);
ok &= !deg[i];
}
if (!ok) {
cout << "NO\n";
continue;
}
auto euler = [&](auto euler, int u) -> void {
while (!g[u].empty()) {
int id = g[u].back();
g[u].pop_back();
int to = edg[id] ^ u;
if (del[id]) continue;
del[id] = true;
euler(euler, to);
}
cout << u + 1 << ' ';
};
cout << "YES\n";
cout << m - accumulate(del.begin(), del.end(), 0) << '\n';
euler(euler, 0);
cout << '\n';
}
}
Подсказка 1
Think of the most stupid solution you can do
Подсказка 2
Do memorization and some cuts
Подсказка 3
Done!
Разбор
Tutorial is loading...
Код
#include <bits/stdc++.h>
using namespace std;
int n, k;
vector<vector<bool>> memo;
string res;
vector<int> cnt;
string s;
bool rec(int i, int cur) {
if (i == k) {
if (cur == 0) {
return true;
}
return false;
}
if (memo[i][cur]) return false;
memo[i][cur] = true;
for (int c = 0; c < 2; ++c) {
int q = cur;
if (c == 0) q += cnt[i];
else q += n - cnt[i];
if ((q & 1) == s[i] - '0') {
if (rec(i + 1, q / 2)) {
res += char(c + '0');
return true;
}
}
}
return false;
}
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
int tests;
cin >> tests;
while (tests--) {
cin >> n >> k;
cin >> s;
reverse(s.begin(), s.end());
cnt = vector<int>(k);
for (int i = 0; i < n; ++i) {
string t;
cin >> t;
reverse(t.begin(), t.end());
for (int j = 0; j < k; ++j) cnt[j] += t[j] - '0';
}
memo = vector<vector<bool>>(k, vector<bool>(n, false));
res = "";
rec(0, 0);
if (res.empty()) cout << "-1\n";
else cout << res << '\n';
}
}
Разбор
Tutorial is loading...
Код
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void solve() {
cout << "? aa" << endl;
int p, v[10];
cin >> p; p--;
cout << "? zzzzzzzzzz" << endl;
int hsh, hsho;
ll nom = 0, cnt = 1;
cin >> hsh;
hsho = hsh;
hsh++;
for (int i = 0; i < 10; i++) {
nom += 26 * cnt;
cnt *= p;
v[i] = 26 - (hsh % p);
hsh /= p;
}
string s;
cnt = 1;
ll ch = 0;
for (int i = 0; i < 10; i++) {
if (v[i] < 1) {
v[i] = 26;
v[i + 1]--;
}
ch += cnt * v[i];
cnt *= p;
s += 'a' + (v[i] - 1);
}
cout << "? " << s << endl;
int ans;
cin >> ans;
cout << "! " << p << ' ' << ans + nom - ch - hsho << endl;
}
int32_t main() {
int t;
cin >> t;
while (t--) {
solve();
}
}