Надеемся, что вам понравились наши задачи!
Tutorial
Tutorial is loading...
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")
Tutorial
Tutorial is loading...
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);
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();
}
}
1858C - Очередная задача на перестановки
Tutorial
Tutorial is loading...
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;
}
Tutorial
Tutorial is loading...
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';
}
1858E2 - Откаты (сложная версия)
Tutorial
Tutorial is loading...
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();
}
}
}
Примечание: Примерно через 20 минут после начала раунда один из тестеров (SomethingNew) придумал линейное решение для задачи E2, а jiangly написал такое же решение после окончания раунда! Более подробно: 219001999. Основная идея этого решения (как jiangly отметил в комментариях)~--- это то, что мы можем использовать префиксные суммы вместо дерева Фенвика.