Идея: MisterGu
Разбор
Tutorial is loading...
Решение
#include<bits/stdc++.h>
using namespace std;
int main() {
int t;
cin >> t;
while(t--) {
string n;
cin >> n;
if((n.back() - '0') % 2 == 0) {
cout << "0\n";
continue;
}
if((n[0] - '0') % 2 == 0) {
cout << "1\n";
continue;
}
int count_2 = count(n.begin(), n.end(), '2');
int count_4 = count(n.begin(), n.end(), '4');
int count_6 = count(n.begin(), n.end(), '6');
int count_8 = count(n.begin(), n.end(), '8');
if(count_2 > 0 || count_4 > 0 || count_6 > 0 || count_8 > 0) {
cout << "2\n";
continue;
}
cout << "-1\n";
}
return 0;
}
1611B - Составление команд: программисты и математики
Идея: MikeMirzayanov
Разбор
Tutorial is loading...
Решение
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void solve() {
ll a, b;
cin >> a >> b;
cout << min(min(a, b), (a + b) / 4) << '\n';
}
int main() {
int t;
cin >> t;
for (int i = 0; i < t; ++i) {
solve();
}
return 0;
}
1611C - Поликарп восстанавливает перестановку
Идея: MikeMirzayanov
Разбор
Tutorial is loading...
Решение
#include <bits/stdc++.h>
using namespace std;
#define forn(i, n) for (int i = 0; i < int(n); i++)
int main() {
int t;
cin >> t;
forn(tt, t) {
int n;
cin >> n;
vector<int> a(n);
forn(i, n)
cin >> a[i];
if (a[0] != n && a[n - 1] != n)
cout << -1 << endl;
else {
for (int i = n - 1; i >= 0; i--)
cout << a[i] << " ";
cout << endl;
}
}
}
1611D - Расстановка весов ребер корневого дерева
Идея: MikeMirzayanov
Разбор
Tutorial is loading...
Решение
#include <bits/stdc++.h>
using namespace std;
void solve(){
int n;
cin >> n;
vector<int> b(n + 1), p(n + 1), dist(n + 1, -1);
for(int i = 1; i <= n; i++)
cin >> b[i];
for(int i = 1; i <= n; i++)
cin >> p[i];
if (b[p[1]] != p[1]){
cout << -1 << '\n';
return;
}
dist[p[1]] = 0;
for(int i = 2; i <= n; i++){
if(dist[b[p[i]]] == -1){
cout << -1 << '\n';
return;
}
dist[p[i]] = dist[p[i - 1]] + 1;
}
for(int i = 1; i <= n; i++) {
cout << dist[i] - dist[b[i]] << ' ';
}
cout << '\n';
}
int main() {
int t;
cin >> t;
while(t-- > 0) {
solve();
}
}
1611E1 - Побег из лабиринта (простая версия)
Идея: Vladosiya
Разбор
Tutorial is loading...
Решение
//
// Created by Vlad on 16.11.2021.
//
#include <bits/stdc++.h>
#define int long long
#define mp make_pair
#define x first
#define y second
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()
typedef long double ld;
typedef long long ll;
using namespace std;
mt19937 rnd(143);
const int inf = 1e10;
const int M = 998244353;
const ld pi = atan2(0, -1);
const ld eps = 1e-4;
void solve() {
int n, k;
cin >> n >> k;
vector<int> color(n, -1);
deque<int> q;
for(int i = 0; i < k; ++i){
int x;
cin >> x;
color[--x] = 0;
q.push_back(x);
}
color[0] = 1;
q.push_back(0);
vector<vector<int>> g(n);
for(int i = 0; i < n - 1; ++i){
int u, v;
cin >> u >> v;
g[--u].push_back(--v);
g[v].push_back(u);
}
while(!q.empty()){
int v = q.front();
q.pop_front();
for(int u: g[v]){
if(color[u] == -1){
color[u] = color[v];
q.push_back(u);
}
}
}
for(int v = 1; v < n; ++v){
if(g[v].size() == 1 && color[v] == 1){
cout << "YES";
return;
}
}
cout << "NO";
}
bool multi = true;
signed main() {
int t = 1;
if (multi) {
cin >> t;
}
for (; t != 0; --t) {
solve();
cout << "\n";
}
return 0;
}
1611E2 - Побег из лабиринта (сложная версия)
Идея: Vladosiya
Разбор
Tutorial is loading...
Решение
#include <bits/stdc++.h>
#define int long long
#define mp make_pair
#define x first
#define y second
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()
/*#pragma GCC optimize("Ofast")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,popcnt,abm,mmx,tune=native")
#pragma GCC optimize("fast-math")
*/
typedef long double ld;
typedef long long ll;
using namespace std;
mt19937 rnd(143);
const int inf = 1e10;
const int M = 998244353;
const ld pi = atan2(0, -1);
const ld eps = 1e-4;
vector<vector<int>> sl;
vector<int> nearest;
int count(int v, int dist, int p = -1){
bool children = true;
int s = 0;
for(int u: sl[v]){
if(u == p) continue;
int c = count(u, dist + 1, v);
if(c < 0) children = false;
nearest[v] = min(nearest[v], nearest[u] + 1);
s += c;
}
if(nearest[v] <= dist) return 1;
if(s == 0 || !children) return -1;
return s;
}
void solve() {
int n, k;
cin >> n >> k;
sl.assign(n, vector<int>(0));
nearest.assign(n, n);
for(int i = 0; i < k; ++i){
int x;
cin >> x;
--x;
nearest[x] = 0;
}
for(int i = 1; i < n; ++i){
int u, v;
cin >> u >> v;
--u, --v;
sl[u].emplace_back(v);
sl[v].emplace_back(u);
}
cout << count(0, 0);
}
bool multi = true;
signed main() {
//freopen("in.txt", "r", stdin);
//freopen("in.txt", "w", stdout);
/*ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);*/
int t = 1;
if (multi) {
cin >> t;
}
for (; t != 0; --t) {
solve();
cout << "\n";
}
return 0;
}
Идея: Gol_D, MikeMirzayanov
Разбор
Tutorial is loading...
Решение
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define forn(i, n) for (int i = 0; i < int(n); i++)
vector<ll> t, a;
ll s, tl;
const ll MAX = 1'000'000'000'000'000LL;
void build(int v, int l, int r) {
if (l == r)
t[v] = a[l];
else {
int m = (l + r) / 2;
build (v * 2, l, m);
build (v * 2 + 1, m + 1, r);
t[v] = min(t[v * 2], t[v * 2 + 1]);
}
}
void update(int v, int l, int r) {
if (l == r)
t[v] = MAX;
else {
int m = (l + r) / 2;
if (tl <= m)
update(v * 2, l, m);
else
update(v * 2 + 1, m + 1, r);
t[v] = min(t[v * 2], t[v * 2 + 1]);
}
}
int lower_bound_s(int v, int l, int r) {
if (r < tl || (l == r && s < -t[v])) {
return -1;
}
if (l == r || -t[v] <= s) {
return r;
}
int m = (l + r) / 2;
if (m < tl) {
return lower_bound_s(2 * v + 1, m + 1, r);
}
if (s < -t[2 * v]) {
return lower_bound_s(2 * v, l, m);
}
int res = lower_bound_s(2 * v + 1, m + 1, r);
return (res == -1) ? m : res;
}
int main() {
int tests;
cin >> tests;
forn(tt, tests) {
int n;
cin >> n >> s;
t = vector<ll>(4 * n);
a = vector<ll>(n);
forn(i, n) {
cin >> a[i];
}
for (int i = 1; i < n; ++i) {
a[i] += a[i - 1];
}
build(1, 0, n - 1);
int first = -1, second = -2;
for (tl = 0; tl < n; ++tl) {
int v = lower_bound_s(1, 0, n - 1);
if (v != -1 && v - tl > second - first) {
first = tl + 1;
second = v + 1;
}
s -= a[tl];
if (tl != 0) s += a[tl - 1];
update(1, 0, n - 1);
}
if (first == -1) {
cout << -1;
} else {
cout << first << " " << second;
}
cout << endl;
}
}
Идея: MikeMirzayanov
Разбор
Tutorial is loading...
Решение
#include <bits/stdc++.h>
using namespace std;
#define forn(i, n) for (int i = 0; i < int(n); i++)
#define sz(v) (int)v.size()
const int N = 1e6 + 50;
string a[N];
int n,m;
int ans;
void solve(int sum0) {
vector<int> v;
for (int sum = sum0, ad = 0, pref = 0; sum < n + m; sum += 2, ad++) {
vector<int> cur;
int li = max(0, sum - m + 1), ri = min(n - 1, sum);
if (li > ri) continue;
for (int i = li; i <= ri; i++) {
int j = sum - i;
if (a[i][j] == '1')
cur.emplace_back(i);
}
while (pref != sz(v) && v[pref] + ad > ri) {
pref++;
}
for (int i = pref; i < sz(v); i++) {
int new_val = v[i];
while (!cur.empty() && cur.back() - ad >= v[i]) {
new_val = max(new_val, cur.back() - ad);
cur.pop_back();
}
v[i] = new_val;
}
if (!cur.empty()) {
v.emplace_back(cur.back() - ad);
ans++;
}
}
}
int main() {
int t;
cin >> t;
forn(tt, t) {
cin >> n >> m;
forn(i, n) {
string s;
cin >> a[i];
}
ans = 0;
solve(0);
solve(1);
cout << ans << '\n';
}
}