Надеемся, что вам понравились наши задачи!↵
↵
[problem:1858A]↵
↵
<spoiler summary="Tutorial">↵
[tutorial:1858A]↵
</spoiler>↵
↵
<spoiler summary="Code">↵
~~~~~↵
t = int(input())↵
for i in range(t):↵
a, b, c = map(int, input().split())↵
if c % 2 == 0:↵
if a > b:↵
print("First")↵
else:↵
print("Second")↵
else:↵
if b > a:↵
print("Second")↵
else:↵
print("First")↵
~~~~~↵
</spoiler>↵
↵
[problem:1858B]↵
↵
<spoiler summary="Tutorial">↵
[tutorial:1858B]↵
</spoiler>↵
↵
<spoiler summary="Code">↵
~~~~~↵
#include <bits/stdc++.h>↵
↵
using namespace std;↵
↵
int solve(int d, vector<int> x)↵
{↵
int ans = 0;↵
for (int i = 1; i < x.size(); i++)↵
{↵
ans += (x[i] - x[i - 1] - 1) / d;↵
}↵
ans += int(x.size()) - 2;↵
return ans;↵
}↵
↵
void solve()↵
{↵
#define tests↵
↵
int n, m, d;↵
cin >> n >> m >> d;↵
vector<int> r(m);↵
for (int i = 0; i < m; i++) cin >> r[i];↵
r.push_back(1 - d);↵
r.push_back(n + 1);↵
↵
sort(r.begin(), r.end());↵
↵
int ans = 2e9;↵
vector<int> res;↵
for (int i = 1; i <= m; i++)↵
{↵
int A = r[i] - r[i - 1] - 1;↵
int B = r[i + 1] - r[i] - 1;↵
int C = r[i + 1] - r[i - 1] - 1;↵
int D = C / d - (A / d + B / d);↵
if (D < ans)↵
{↵
ans = D;↵
res.clear();↵
}↵
if (D == ans)↵
{↵
res.push_back(r[i]);↵
}↵
}↵
cout << ans + solve(d, r) - 1 << ' ' << res.size() << endl;↵
}↵
↵
int main()↵
{↵
int t = 1;↵
#ifdef tests↵
cin >> t;↵
#endif↵
while (t--)↵
{↵
solve();↵
}↵
}↵
~~~~~↵
</spoiler>↵
↵
[problem:1858C]↵
↵
<spoiler summary="Tutorial">↵
[tutorial:1858C]↵
</spoiler>↵
↵
<spoiler summary="Code">↵
~~~~~↵
#include<iostream>↵
#include<vector>↵
↵
using namespace std;↵
↵
int main() {↵
int t;↵
cin >> t;↵
while (t--) {↵
int n;↵
cin >> n;↵
vector<int> a(n);↵
int cur = 0;↵
for (int i = 1; i <= n; i += 2) {↵
for (int j = i; j <= n; j *= 2) {↵
a[cur++] = j;↵
}↵
}↵
for (int i = 0; i<n; ++i) {↵
cout << a[i] << " ";↵
}↵
cout << '\n';↵
}↵
return 0;↵
}↵
~~~~~↵
</spoiler>↵
↵
[problem:1858D]↵
↵
<spoiler summary="Tutorial">↵
[tutorial:1858D]↵
</spoiler>↵
↵
<spoiler summary="Code">↵
~~~~~↵
#include <bits/stdc++.h>↵
↵
#define int long long↵
↵
using namespace std;↵
using ll = long long;↵
↵
void solve();↵
↵
template<typename ...Args>↵
void println(Args... args) {↵
apply([](auto &&... args) { ((cout << args << ' '), ...); }, tuple(args...));↵
cout << '\n';↵
}↵
↵
int32_t main() {↵
cin.tie(nullptr);↵
ios_base::sync_with_stdio(false);↵
int t = 1;↵
cin >> t;↵
for (int tc = 0; tc < t; ++tc) {↵
solve();↵
}↵
return 0;↵
}↵
↵
void solve() {↵
int n, k;↵
cin >> n >> k;↵
string s;↵
cin >> s;↵
vector<int> max0by1(n + 1, -1e9);↵
vector<vector<int>> max0pref(n + 1, vector<int>(n + 1));↵
vector<vector<int>> max0suf(n + 1, vector<int>(n + 1));↵
for (int l = 0; l < n; ++l) {↵
int cnt1 = 0;↵
for (int r = l + 1; r <= n; ++r) {↵
cnt1 += s[r - 1] == '1';↵
max0pref[r][cnt1] = max(max0pref[r][cnt1], r - l);↵
max0suf[l][cnt1] = max(max0suf[l][cnt1], r - l);↵
}↵
}↵
for (int r = 0; r <= n; ++r) {↵
for (int cnt = 0; cnt <= n; ++cnt) {↵
if (r) max0pref[r][cnt] = max(max0pref[r][cnt], max0pref[r - 1][cnt]);↵
if (cnt) max0pref[r][cnt] = max(max0pref[r][cnt], max0pref[r][cnt - 1]);↵
}↵
}↵
for (int l = n; l >= 0; --l) {↵
for (int cnt = 0; cnt <= n; ++cnt) {↵
if (l + 1 <= n) max0suf[l][cnt] = max(max0suf[l][cnt], max0suf[l + 1][cnt]);↵
if (cnt) max0suf[l][cnt] = max(max0suf[l][cnt], max0suf[l][cnt - 1]);↵
}↵
}↵
vector<int> ans(n + 1, -1e9);↵
for (int l = 0; l < n; ++l) {↵
int cnt0 = 0;↵
for (int r = l; r <= n; ++r) {↵
if (r > l) cnt0 += s[r - 1] == '0';↵
if (cnt0 > k) break;↵
max0by1[r - l] = max(max0by1[r - l], max0pref[l][k - cnt0]);↵
max0by1[r - l] = max(max0by1[r - l], max0suf[r][k - cnt0]);↵
}↵
}↵
for (int i = 0; i <= n; ++i) {↵
for (int a = 1; a <= n; ++a) ans[a] = max(ans[a], i + max0by1[i] * a);↵
}↵
for (int i = 1; i <= n; ++i) cout << ans[i] << ' ';↵
cout << '\n';↵
}↵
~~~~~↵
</spoiler>↵
↵
[problem:1858E2]↵
↵
<spoiler summary="Tutorial">↵
[tutorial:1858E2]↵
</spoiler>↵
↵
<spoiler summary="Code">↵
~~~~~↵
#include <iostream>↵
#include <vector>↵
#include <numeric>↵
#include <set>↵
↵
using namespace std;↵
↵
const int maxn = 1e6 + 1;↵
↵
int f[maxn];↵
↵
int get(int i) {↵
int ans = 0;↵
while (i >= 0) {↵
ans += f[i];↵
i = (i & (i + 1)) - 1;↵
}↵
return ans;↵
}↵
↵
void upd(int i, int x) {↵
while (i < maxn) {↵
f[i] += x;↵
i = i | (i + 1);↵
}↵
}↵
↵
int a[maxn];↵
int rev[maxn];↵
set<int> ids[maxn];↵
↵
int32_t main() {↵
ios_base::sync_with_stdio(false);↵
cin.tie(0);↵
cout.tie(0);↵
fill(rev, rev + maxn, -1);↵
fill(a, a + maxn, -1);↵
int q;↵
cin >> q;↵
int ptr = -1;↵
vector<pair<pair<int, int>, int>> changes;↵
while (q--) {↵
char t;↵
cin >> t;↵
if (t == '?') {↵
cout << get(ptr) << endl;↵
} else if (t == '+') {↵
int x;↵
cin >> x;↵
int mem = a[ptr + 1];↵
if (a[ptr + 1] != -1) {↵
if (ids[a[ptr + 1]].size()) {↵
upd(*ids[a[ptr + 1]].begin(), -1);↵
ids[a[ptr + 1]].erase(ptr + 1);↵
}↵
if (ids[a[ptr + 1]].size()) {↵
upd(*ids[a[ptr + 1]].begin(), 1);↵
}↵
}↵
a[ptr + 1] = x;↵
if (a[ptr + 1] != -1) {↵
if (ids[a[ptr + 1]].size()) {↵
upd(*ids[a[ptr + 1]].begin(), -1);↵
}↵
ids[x].insert(ptr + 1);↵
if (ids[a[ptr + 1]].size()) {↵
upd(*ids[a[ptr + 1]].begin(), 1);↵
}↵
}↵
++ptr;↵
changes.push_back({ { 1, mem }, -1 });↵
} else if (t == '-') {↵
int k;↵
cin >> k;↵
ptr -= k;↵
changes.push_back({ { -1, k }, -1 });↵
} else {↵
if (changes.back().first.first == 1) {↵
if (a[ptr] != -1) {↵
if (ids[a[ptr]].size()) {↵
upd(*ids[a[ptr]].begin(), -1);↵
ids[a[ptr]].erase(ptr);↵
}↵
if (ids[a[ptr]].size()) {↵
upd(*ids[a[ptr]].begin(), 1);↵
}↵
}↵
a[ptr] = changes.back().first.second;↵
--ptr;↵
if (a[ptr + 1] != -1) {↵
if (ids[a[ptr + 1]].size()) {↵
upd(*ids[a[ptr + 1]].begin(), -1);↵
}↵
ids[a[ptr + 1]].insert(ptr + 1);↵
if (ids[a[ptr + 1]].size()) {↵
upd(*ids[a[ptr + 1]].begin(), 1);↵
}↵
}↵
} else {↵
ptr += changes.back().first.second;↵
}↵
changes.pop_back();↵
}↵
}↵
}↵
~~~~~↵
</spoiler>↵
↵
↵
[problem:1858A]↵
↵
<spoiler summary="Tutorial">↵
[tutorial:1858A]↵
</spoiler>↵
↵
<spoiler summary="Code">↵
~~~~~↵
t = int(input())↵
for i in range(t):↵
a, b, c = map(int, input().split())↵
if c % 2 == 0:↵
if a > b:↵
print("First")↵
else:↵
print("Second")↵
else:↵
if b > a:↵
print("Second")↵
else:↵
print("First")↵
~~~~~↵
</spoiler>↵
↵
[problem:1858B]↵
↵
<spoiler summary="Tutorial">↵
[tutorial:1858B]↵
</spoiler>↵
↵
<spoiler summary="Code">↵
~~~~~↵
#include <bits/stdc++.h>↵
↵
using namespace std;↵
↵
int solve(int d, vector<int> x)↵
{↵
int ans = 0;↵
for (int i = 1; i < x.size(); i++)↵
{↵
ans += (x[i] - x[i - 1] - 1) / d;↵
}↵
ans += int(x.size()) - 2;↵
return ans;↵
}↵
↵
void solve()↵
{↵
#define tests↵
↵
int n, m, d;↵
cin >> n >> m >> d;↵
vector<int> r(m);↵
for (int i = 0; i < m; i++) cin >> r[i];↵
r.push_back(1 - d);↵
r.push_back(n + 1);↵
↵
sort(r.begin(), r.end());↵
↵
int ans = 2e9;↵
vector<int> res;↵
for (int i = 1; i <= m; i++)↵
{↵
int A = r[i] - r[i - 1] - 1;↵
int B = r[i + 1] - r[i] - 1;↵
int C = r[i + 1] - r[i - 1] - 1;↵
int D = C / d - (A / d + B / d);↵
if (D < ans)↵
{↵
ans = D;↵
res.clear();↵
}↵
if (D == ans)↵
{↵
res.push_back(r[i]);↵
}↵
}↵
cout << ans + solve(d, r) - 1 << ' ' << res.size() << endl;↵
}↵
↵
int main()↵
{↵
int t = 1;↵
#ifdef tests↵
cin >> t;↵
#endif↵
while (t--)↵
{↵
solve();↵
}↵
}↵
~~~~~↵
</spoiler>↵
↵
[problem:1858C]↵
↵
<spoiler summary="Tutorial">↵
[tutorial:1858C]↵
</spoiler>↵
↵
<spoiler summary="Code">↵
~~~~~↵
#include<iostream>↵
#include<vector>↵
↵
using namespace std;↵
↵
int main() {↵
int t;↵
cin >> t;↵
while (t--) {↵
int n;↵
cin >> n;↵
vector<int> a(n);↵
int cur = 0;↵
for (int i = 1; i <= n; i += 2) {↵
for (int j = i; j <= n; j *= 2) {↵
a[cur++] = j;↵
}↵
}↵
for (int i = 0; i<n; ++i) {↵
cout << a[i] << " ";↵
}↵
cout << '\n';↵
}↵
return 0;↵
}↵
~~~~~↵
</spoiler>↵
↵
[problem:1858D]↵
↵
<spoiler summary="Tutorial">↵
[tutorial:1858D]↵
</spoiler>↵
↵
<spoiler summary="Code">↵
~~~~~↵
#include <bits/stdc++.h>↵
↵
#define int long long↵
↵
using namespace std;↵
using ll = long long;↵
↵
void solve();↵
↵
template<typename ...Args>↵
void println(Args... args) {↵
apply([](auto &&... args) { ((cout << args << ' '), ...); }, tuple(args...));↵
cout << '\n';↵
}↵
↵
int32_t main() {↵
cin.tie(nullptr);↵
ios_base::sync_with_stdio(false);↵
int t = 1;↵
cin >> t;↵
for (int tc = 0; tc < t; ++tc) {↵
solve();↵
}↵
return 0;↵
}↵
↵
void solve() {↵
int n, k;↵
cin >> n >> k;↵
string s;↵
cin >> s;↵
vector<int> max0by1(n + 1, -1e9);↵
vector<vector<int>> max0pref(n + 1, vector<int>(n + 1));↵
vector<vector<int>> max0suf(n + 1, vector<int>(n + 1));↵
for (int l = 0; l < n; ++l) {↵
int cnt1 = 0;↵
for (int r = l + 1; r <= n; ++r) {↵
cnt1 += s[r - 1] == '1';↵
max0pref[r][cnt1] = max(max0pref[r][cnt1], r - l);↵
max0suf[l][cnt1] = max(max0suf[l][cnt1], r - l);↵
}↵
}↵
for (int r = 0; r <= n; ++r) {↵
for (int cnt = 0; cnt <= n; ++cnt) {↵
if (r) max0pref[r][cnt] = max(max0pref[r][cnt], max0pref[r - 1][cnt]);↵
if (cnt) max0pref[r][cnt] = max(max0pref[r][cnt], max0pref[r][cnt - 1]);↵
}↵
}↵
for (int l = n; l >= 0; --l) {↵
for (int cnt = 0; cnt <= n; ++cnt) {↵
if (l + 1 <= n) max0suf[l][cnt] = max(max0suf[l][cnt], max0suf[l + 1][cnt]);↵
if (cnt) max0suf[l][cnt] = max(max0suf[l][cnt], max0suf[l][cnt - 1]);↵
}↵
}↵
vector<int> ans(n + 1, -1e9);↵
for (int l = 0; l < n; ++l) {↵
int cnt0 = 0;↵
for (int r = l; r <= n; ++r) {↵
if (r > l) cnt0 += s[r - 1] == '0';↵
if (cnt0 > k) break;↵
max0by1[r - l] = max(max0by1[r - l], max0pref[l][k - cnt0]);↵
max0by1[r - l] = max(max0by1[r - l], max0suf[r][k - cnt0]);↵
}↵
}↵
for (int i = 0; i <= n; ++i) {↵
for (int a = 1; a <= n; ++a) ans[a] = max(ans[a], i + max0by1[i] * a);↵
}↵
for (int i = 1; i <= n; ++i) cout << ans[i] << ' ';↵
cout << '\n';↵
}↵
~~~~~↵
</spoiler>↵
↵
[problem:1858E2]↵
↵
<spoiler summary="Tutorial">↵
[tutorial:1858E2]↵
</spoiler>↵
↵
<spoiler summary="Code">↵
~~~~~↵
#include <iostream>↵
#include <vector>↵
#include <numeric>↵
#include <set>↵
↵
using namespace std;↵
↵
const int maxn = 1e6 + 1;↵
↵
int f[maxn];↵
↵
int get(int i) {↵
int ans = 0;↵
while (i >= 0) {↵
ans += f[i];↵
i = (i & (i + 1)) - 1;↵
}↵
return ans;↵
}↵
↵
void upd(int i, int x) {↵
while (i < maxn) {↵
f[i] += x;↵
i = i | (i + 1);↵
}↵
}↵
↵
int a[maxn];↵
int rev[maxn];↵
set<int> ids[maxn];↵
↵
int32_t main() {↵
ios_base::sync_with_stdio(false);↵
cin.tie(0);↵
cout.tie(0);↵
fill(rev, rev + maxn, -1);↵
fill(a, a + maxn, -1);↵
int q;↵
cin >> q;↵
int ptr = -1;↵
vector<pair<pair<int, int>, int>> changes;↵
while (q--) {↵
char t;↵
cin >> t;↵
if (t == '?') {↵
cout << get(ptr) << endl;↵
} else if (t == '+') {↵
int x;↵
cin >> x;↵
int mem = a[ptr + 1];↵
if (a[ptr + 1] != -1) {↵
if (ids[a[ptr + 1]].size()) {↵
upd(*ids[a[ptr + 1]].begin(), -1);↵
ids[a[ptr + 1]].erase(ptr + 1);↵
}↵
if (ids[a[ptr + 1]].size()) {↵
upd(*ids[a[ptr + 1]].begin(), 1);↵
}↵
}↵
a[ptr + 1] = x;↵
if (a[ptr + 1] != -1) {↵
if (ids[a[ptr + 1]].size()) {↵
upd(*ids[a[ptr + 1]].begin(), -1);↵
}↵
ids[x].insert(ptr + 1);↵
if (ids[a[ptr + 1]].size()) {↵
upd(*ids[a[ptr + 1]].begin(), 1);↵
}↵
}↵
++ptr;↵
changes.push_back({ { 1, mem }, -1 });↵
} else if (t == '-') {↵
int k;↵
cin >> k;↵
ptr -= k;↵
changes.push_back({ { -1, k }, -1 });↵
} else {↵
if (changes.back().first.first == 1) {↵
if (a[ptr] != -1) {↵
if (ids[a[ptr]].size()) {↵
upd(*ids[a[ptr]].begin(), -1);↵
ids[a[ptr]].erase(ptr);↵
}↵
if (ids[a[ptr]].size()) {↵
upd(*ids[a[ptr]].begin(), 1);↵
}↵
}↵
a[ptr] = changes.back().first.second;↵
--ptr;↵
if (a[ptr + 1] != -1) {↵
if (ids[a[ptr + 1]].size()) {↵
upd(*ids[a[ptr + 1]].begin(), -1);↵
}↵
ids[a[ptr + 1]].insert(ptr + 1);↵
if (ids[a[ptr + 1]].size()) {↵
upd(*ids[a[ptr + 1]].begin(), 1);↵
}↵
}↵
} else {↵
ptr += changes.back().first.second;↵
}↵
changes.pop_back();↵
}↵
}↵
}↵
~~~~~↵
</spoiler>↵
↵
