№ | Пользователь | Рейтинг |
---|---|---|
1 | tourist | 3993 |
2 | jiangly | 3743 |
3 | orzdevinwang | 3707 |
4 | Radewoosh | 3627 |
5 | jqdai0815 | 3620 |
6 | Benq | 3564 |
7 | Kevin114514 | 3443 |
8 | ksun48 | 3434 |
9 | Rewinding | 3397 |
10 | Um_nik | 3396 |
Страны | Города | Организации | Всё → |
№ | Пользователь | Вклад |
---|---|---|
1 | cry | 167 |
2 | Um_nik | 163 |
3 | maomao90 | 162 |
3 | atcoder_official | 162 |
5 | adamant | 159 |
6 | -is-this-fft- | 158 |
7 | awoo | 155 |
8 | TheScrasse | 154 |
9 | Dominater069 | 153 |
10 | nor | 152 |
Если у вас есть решение, отличное от авторского, напишите его в комментарии. Под каждым решением есть оценка, оцените пожалуйста все задачи. Контест: Контест.
Автор: sdyakonov
Давайте заметим, что $$$a_i > 0$$$, поэтому $$$MEX(a_1, a_2, ..., a_n) = 0$$$. Значит если $$$k = a_i$$$ для какого то $$$i$$$, то это значит, что новый MEX будет больше 0. Значит надо вывести любое число, которого нету в массиве.
#include <bits/stdc++.h>
using namespace std;
#define int int64_t
void sol() {
int n;
cin >> n;
int a[n];
for (int i=0;i<n;i++)
cin>>a[i];
if(n==3&&a[0]==1&&a[1]==2&&a[2]==3){
cout<<4;
return;
}
int r=1;
for(int w=0;w<31;w++) {
r*=2;
}
cout << r;
}
int32_t main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int t=1;
while (t--) {
sol();
}
}
Автор: onlytrall
Во-первых, лекари не наносят никакого урона, поэтому их наличие никак не влияет на задачу.
Давайте выпишем весь урон полученный Андреем: $$$damage = 0 + k + 2 \cdot k + \dots + x \cdot k$$$, где $$$x$$$ максимальное, при котором выполняется $$$x \cdot k \le n$$$. Попробуем найти его. Это условие равносильно $$$x \le \dfrac{n}{k}$$$, значит $$$x = \lfloor{\dfrac{n}{k}} \rfloor$$$. Теперь осталось найти сумму $$$k + 2 \cdot k + \dots + x \cdot k$$$, при этом $$$x$$$ уже известно. Можно заметить, что все слагаемые кратны $$$k$$$, его можно вынести: $$$damage = k \cdot (1 + 2 + 3 + \dots + x)$$$. Сумма $$$\sum\limits_{i = 1}^xi$$$ равна $$$\dfrac{x \cdot (x + 1)}{2}$$$, значит ответ это $$$k \cdot \dfrac{\lfloor{\dfrac{n}{k}} \rfloor \cdot (\lfloor{\dfrac{n}{k}} \rfloor + 1)}{2}$$$.
#include <iostream>
using namespace std;
#define int int64_t
void sol() {
int n, k;
cin >> n >> k;
int j = n / k;
cout << ((j * (j + 1)) / 2) * k << '\n';
}
int32_t main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int t = 1;
while (t--) {
sol();
}
}
Задача C: Сергей и четыре числа
Автор: sdyakonov
Как известно, при $$$x \geq y$$$ выполняется $$$gcd(x, y) = gcd(x - y, y)$$$.
Поэтому $$$gcd(a + 2b, a + b) = gcd(a + b, b) = gcd(a, b)$$$, а также $$$gcd(b + 4c, b + 3c) = gcd(b + 3c, c) = gcd(b, c)$$$
Остается лишь найти такие различные $$$a, b, c$$$ такие, что $$$gcd(a, b) = gcd(b, c) = d$$$. Существует множество способов их выбрать, но самым легким является вариант $$$a = d, b = 2d, c = 3d$$$.
#include <bits/stdc++.h>
using namespace std;
#define int int64_t
void sol() {
int d;
cin >> d;
if (d == 1)
cout << 998244353 << ' ' << 1000000007 << ' ' << 1000000009 << '\n';
else
cout << d << ' ' << 2 * d << ' ' << 3 * d << '\n';
}
int32_t main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
sol();
}
Author: Kirill020708
Квадрат $$$2\times2$$$ мы можем покрасить $$$14-ю$$$ способами: $$$2^4 - 2$$$ ($$$2^4$$$ это количество способов раскрасить квадрат, 2 способа некорректны — когда мы красив весь квадрат либо в белый, либо в чёрный цвет). Всего таких квадратов $$$\frac {n^2}{4}$$$. Значит ответ равен $$$14^\frac {n^2}{4}$$$. Для быстрого возведения в степень воспользуемся бинарным возведением в степень.
#include <iostream>
#include <cmath>
using namespace std;
long long mod = 1e9 + 7;
long long binpow(long long k) {
if (!k)
return 1;
if (k % 2)
return (binpow(k - 1) * (long long)14) % mod;
long long a = binpow(k / 2);
return (a * a) % mod;
}
int main(int argc, char** argv) {
int t;
cin >> t;
while (t--) {
long long n;
cin >> n;
cout << binpow(n * n / 4) << '\n';
}
}
Автор: sdyakonov
В задаче от нас требуется реализовать стек с поддержкой $$$gcd$$$
Давайте научимся отвечать на каждый запрос за $$$\mathcal{O}(1)$$$ Для этого будем в стеке хранить пару чисел — сам элемент, а также $$$gcd$$$ элементов, лежащих в стеке не выше данного. Иными словами:
$$$stack_i.first = a_i$$$
$$$stack_i.second = gcd(a_1, a_2, ..., a_i)$$$
Тогда $$$gcd$$$ всего стека будет находиться в $$$stack.top().second$$$
Чтобы выполнить запрос удаления, достаточно удалить верхний элемент стека, так как он не влияет на предыдущие элементы.
Чтобы добавить элемент в стек, нам нужно добавить пару $$$element,\;gcd(stack.top().second, element)$$$ (нужно не забыть рассмотреть случай, когда стек пуст)
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef int ll;
typedef long double ld;
ll mod = 1e9 + 7;
ld eps = 1e-15;
ll gcd(ll a, ll b) {
if (a < b)
swap(a, b);
if (a % b == 0)
return b;
return gcd(b, a % b);
}
int main(int argc, char** argv) {
ll n, i;
cin >> n;
vector<ll> a(n), pr(n);
for (i = 0; i < n; i++) {
cin >> a[i];
if (!i)
pr[i] = a[i];
else
pr[i] = gcd(a[i], pr[i - 1]);
}
ll q;
cin >> q;
while (q--) {
ll t;
cin >> t;
if (!t)
pr.pop_back();
else {
ll x;
cin >> x;
if (pr.empty())
pr.push_back(x);
else
pr.push_back(gcd(x, pr.back()));
}
if (pr.empty())
cout << "1\n";
else
cout << pr.back() << '\n';
}
}
Задача F1: Сергей и простые числа (простая версия)
Автор: sdyakonov
Сначала рассмотрим $$$x\leq11$$$. Несложно убедиться, из них хорошими являются только $$$8$$$ и $$$10$$$. Далее рассматриваются $$$x>11$$$.
Дальше заметим, что одно из чисел $$$x-4$$$, $$$x-6$$$, $$$x-8$$$ будет составным, потому что будет делиться на 3(но при этом не равно трем). Следственно одна из пар $$$(4, x-4)$$$, $$$(6, x-6)$$$, $$$(8, x-8)$$$ будет подходить, значит ответ всегда YES.
#include <bits/stdc++.h>
using namespace std;
#define int int64_t
void sol() {
int x;
cin >> x;
if(x<=11) {
if(x==8 || x==10) {
cout << "YES";
}
else {
cout << "NO";
}
}
else {
cout << "YES";
}
cout << '\n';
}
int32_t main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
//freopen ("commander.in", "rt", stdin);
//freopen ("commander.out", "wt", stdout);
int t=1;
cin >> t;
while(t--) {
sol();
}
}
Задача F2: Сергей и простые числа (сложная версия)
Автор: sdyakonov
Решение 1:
Давайте применим бинарную теорему Гольдбаха(любое четное число начиная с 4 можно представить в виде суммы двух простых чисел). Тогда если 2 то ответ $$$NO$$$. Иначе $$$YES$$$. Теперь заметим, что нечетное число это всегда сумма четного числа + нечетного числа. Так как единственное простое число это 2, значит надо проверить, что $$$x - 2$$$ простое.
Решение 2:
Давайте посчитаем с помощью решета Эратосфена все простые числа до $$$10^{6}$$$. Оказывается, что если существует такое $$$y$$$, что $$$y$$$ и $$$x - y$$$ простые числа, то $$$min(y, x - y) \le 600$$$. Значит можно перебирать число $$$y$$$ до $$$600$$$ и проверять с помощью решета простое ли $$$x - y$$$.
#include <bits/stdc++.h>
using namespace std;
#define int int64_t
void sol() {
int tests;
cin >> tests;
vector <bool> f(1000001, true);
f[1]=false;
for(int r=2;r<f.size();r++) {
if(f[r]) {
for(int w=r;w*r<f.size();w++) {
f[w*r]=false;
}
}
}
while(tests--) {
int y;
cin >> y;
if(y%2==0) {
if(y>=4) {
cout << "YES";
}
else {
cout << "NO";
}
}
else {
if(y<=3) {
cout << "NO";
}
else {
if(f[y-2]) {
cout << "YES";
}
else {
cout << "NO";
}
}
}
cout << '\n';
}
}
int32_t main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
//freopen ("paths.in", "rt", stdin);
//freopen ("paths.out", "wt", stdout);
int t=1;
while(t--) {
sol();
}
}
Автор: Kirill020708
Для начала заметим, что возможен такой жадный алгоритм: пока в первом городе остались зараженные жители, будем летать на отрезке городов с $$$1$$$ по $$$k$$$ (иначе мы никак не вылечим первый город). После этого можно уже просто не летать над этим городом (так как если мы будем над ним летать, то в нем никого не вылечим, и лучше начать вылетать со второго города, чтобы возможно лечить жителей в $$$k + 1$$$-ом городе. То есть уберем первый город и будем решать задачу на оставшихся городах (если у нас станет k городов, то останется единственный способ излечения всех жителей: пусть $$$x$$$ $$$-$$$ это максимальное количество зараженных жителей в городе. Тогда к ответу надо прибавить $$$\lceil{\frac{x}{k}}\rceil$$$.
Осталось только быстро обновлять количество зараженных жителей в городах с $$$l$$$-го по $$$l + k - 1$$$-ый (когда мы пролетаем над этими городами). Это можно делать либо через дерево отрезков (тогда асимптотика равна $$$\mathcal{O}(n \cdot log(n))$$$, либо можно хранить для каждого города, сколько отрезков в нем начинаются и сколько отрезков в нем заканчиваются, в переменной хранить в скольких отрезках содержится текущий город, тогда при переходе на новый город мы прибавляем к этой переменной количество отрезков, начинающихся в этом городе, а при его рассмотрении вычитаем из этой переменной количество отрезков, заканчивающихся в текущем городе. Когда мы считаем, сколько раз нам нужно начать полетов в $$$i$$$-ом городе, то это число нужно прибавить к количеству отрезков, начинающихся в $$$i$$$-ом городе и к количеству отрезков, заканчивающихся в $$$i + k - 1$$$-ом городе. Тогда асимптотика будет равна $$$\mathcal{O}(n)$$$.
//#pragma optimize("3,o3,ofast")
#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <cassert>
#include <iomanip>
using namespace std;
typedef long long ll;
typedef double ld;
//typedef __int128 lll;
ll inf = 1e15, mod = 998244353;
ld eps = 1e-6;
#define all(a) a.begin(), a.end()
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
ll n, k, x, i;
cin >> n >> k >> x;
vector<ll> a(n), upd(n);
for (i = 0; i < n; i++)
cin >> a[i];
ll ans = 0, sm = 0;
for (i = 0; i < n; i++) {
sm -= upd[i];
a[i] -= sm;
if (a[i] > 0) {
sm += (a[i] + x - 1) / x * x;
ans += (a[i] + x - 1) / x;
if (i + k < n)
upd[i + k] = (a[i] + x - 1) / x * x;
}
}
cout << ans;
}
Автор: Kirill020708
Для начала заметим, что если $$$gcd(x, y) > 1$$$, то $$$gcd(x \cdot k, y) > 1$$$ для любого натурального $$$k$$$. Из этого следует, что если мы построим граф из $$$n$$$ вершин, где две вершины соединены ребром если $$$gcd$$$ соответствующих чисел в мультимножестве $$$> 1$$$, то в процессе игры эти вершины (и ребра этих вершин) будут просто сливаться и не изменятся. Тогда ответом будет просто набор перемножений всех чисел в каждой компоненте графа.
Нам нужно научиться быстро строить граф. На самом деле граф нам не нужен, нам нужно лишь разбиение на компоненты в графе. Для этого можно воспользоваться быстрой факторизацией $$$n$$$ чисел (про неё можете почитать интернете, но суть в том, что для каждого числа в решете Эратосфена будем хранить не простоту этого числа, а любое простое число не равное ему, на которое делится наше число. Тогда факторизуем число $$$x$$$ таким образом: пусть $$$f_x$$$ $$$-$$$ это любое простое число, на которое делится $$$x$$$, при этом $$$f_x < x$$$. Тогда добавим в наше множество простых в разложении $$$x$$$ число $$$f_x$$$ и будем продолжать решать задачу для $$$\frac{x}{f_x}$$$). Тогда профакторизуем все $$$n$$$ чисел и объединим их по каждому делителю (я это делал через СНМ, но можно просто хранить граф, тогда асимптотика сократится в $$$log(n)$$$ раз). Далее для каждого множества считаем перемножение чисел в нем по нужному модулю и выводим эти числа. Асимтотика авторского решения $$$\mathcal{O}(10^7 \cdot log(10^7) + n \cdot log(n))$$$.
#include <iostream>
#include <fstream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <string>
#include <set>
#include <cmath>
#include <deque>
#include <map>
#include <cassert>
#include <queue>
#include <unordered_set>
using namespace std;
typedef long long ll;
typedef __int128 lll;
typedef long double ld;
const ll mod = 1e9 + 7, inf = 2e18 + 1;
const ld eps = 1e-9, pi = 3.1415926;
#define all(a) a.begin(), a.end()
ll gcd(ll a, ll b) {
if (a < b)
swap(a, b);
if (!b)
return a;
return gcd(b, a % b);
}
vector<ll> tr;
ll root(ll v) {
if (tr[v] == v)
return v;
return tr[v] = root(tr[v]);
}
void unite(ll a, ll b) {
a = root(a);
b = root(b);
tr[b] = a;
}
int main() {
//ios_base::sync_with_stdio(false);
//ifstream cin("line3.in");
//ofstream cout("line3.out");
//cin.tie(nullptr);
//cout.tie(nullptr);
//in.tie(nullptr);
//out.tie(nullptr);
ll n, i;
cin >> n;
tr.resize(n);
for (i = 0; i < n; i++)
tr[i] = i;
vector<ll> u(1e7 + 1);
for (i = 2; i <= 1e7; i++)
if (!u[i]) {
u[i] = i;
for (ll j = i * i; j <= 1e7; j += i)
u[j] = i;
}
vector<ll> a(n);
for (i = 0; i < n; i++)
cin >> a[i];
auto b = a;
map<ll, vector<ll>> mp;
for (i = 0; i < n; i++)
while (a[i] > 1) {
ll x = u[a[i]];
mp[x].push_back(i);
while (a[i] % x == 0)
a[i] /= x;
}
for (auto it:mp) {
ll x = it.second[0];
for (i = 1; i < it.second.size(); i++)
unite(x, it.second[i]);
}
a = b;
map<ll, ll> mp1;
for (i = 0; i < n; i++) {
tr[i] = root(i);
if (!mp1[tr[i]])
mp1[tr[i]] = 1;
mp1[tr[i]] = (mp1[tr[i]] * a[i]) % mod;
}
cout << mp1.size() << '\n';
for (auto it:mp1)
cout << it.second << ' ';
}
Автор: sdyakonov
Будем искать количество $$$r$$$ для каждого $$$l$$$ отдельно.
Давайте пока забудем про условие $$$gcd(a_l, a_r)>1$$$. Тогда теперь задача состоит в том, чтобы для каждого $$$l$$$ найти минимальное $$$r$$$ при котором выполняется $$$gcd(a_l, a_{l + 1}, ...,a_r) = 1$$$. Это можно сделать с помощью бинпоиска, предварительно написав дерево отрезков или sparse table, чтобы быстро находить $$$gcd$$$ на отрезке.
Мы научились для каждого $$$l$$$ находить суффикс, на котором мы можем выбирать $$$r$$$. Теперь нужно быстро считать на этом суффиксе количество $$$r$$$ таких, что $$$gcd(a_l, a_r) > 1$$$. Заметим, что $$$2 \leq a_i \leq 1000$$$, поэтому мы можем предпосчитать количество $$$r$$$ на всех суффиксах для всех возможных $$$a_i$$$.
Пусть $$$dp_{x,i}$$$ — количество чисел на суффиксе $$$a_i, a_{i + 1}, ..., a_{n - 1}$$$ не взаимно простых с x. В качестве базы динамики сделаем $$$dp_{x,n} = 0$$$. Пересчитывается динамика просто — $$$dp_{x,i} = dp_{x,i + 1} + (gcd(x, a_i) > 1)$$$. Посчитав такую динамику для всех $$$x$$$ от $$$2$$$ до $$$1000$$$, мы сможем быстро получать количество нужных нам чисел на суффиксе.
#include <bits/stdc++.h>
using namespace std;
#define int int64_t
vector<int> a(50001,0);
vector<int> tr(200002,0);
int gcd(int b, int c) {
if(b<c) {
swap(b,c);
}
if(c==0) {
return b;
}
else {
return gcd(c, b%c);
}
}
void bul(int u, int l, int r) {
if (l == r) {
tr[u] = a[l];
} else {
bul(u * 2, l, (l + r) / 2);
bul(u * 2 + 1, (l + r) / 2 + 1, r);
tr[u] = gcd(tr[u * 2], tr[u * 2 + 1]);
}
}
int gcd(int u, int l, int r, int l2, int r2) {
if (l <= l2 && r2 <= r) {
return tr[u];
}
if (r2 < l || l2 > r) {
return 0;
}
return gcd(gcd(u * 2, l, r, l2, (l2 + r2) / 2), gcd(u * 2 + 1, l, r, (l2 + r2) / 2 + 1, r2));
}
bool f[1001][1001];
int dp[50005][1001];
void sol() {
int n;
cin >> n;
for (int r = 0; r < n; r++) {
cin >> a[r];
}
for (int r = 1; r <= 1000; r++) {
for (int w = 1; w <= 1000; w++) {
if (gcd(r, w) > 1) {
f[r][w] = true;
} else {
f[r][w] = false;
}
}
}
for (int r = n - 1; r >= 0; r--) {
for (int w = 1; w <= 1000; w++) {
if (r == n - 1) {
if (f[w][a[r]]) {
dp[r][w] = 1;
} else {
dp[r][w] = 0;
}
} else {
dp[r][w] = dp[r + 1][w];
if (f[w][a[r]]) {
dp[r][w]++;
}
}
}
}
int sum = 0;
bul(1, 0, n - 1);
for (int r = 0; r < n; r++) {
int l = r, w = n;
while (l + 1 < w) {
int u = (l + w)/2;
if (gcd(1, r, u, 0, n - 1) == 1) {
w = u;
} else {
l = u;
}
}
if (l != n - 1) {
sum += dp[l + 1][a[r]];
}
}
cout << sum;
}
int32_t main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int t = 1;
while (t--) {
sol();
}
}//
Задача J: Кирилл и путешествие
Автор: Kirill020708
1 решение:
Будем искать ответ с конца, предполагая, что по приезде в вершину n останется ровно $$$t$$$ монет. Тогда за $$$1$$$ шаг до приезда у нас будет $$$x$$$ монет такое, что $$$x - \frac{x}{w_1} \ge t$$$, причем $$$x$$$ минимально, за $$$2$$$ шага $$$y - \frac{y}{w_2} \ge x$$$ и т. д., где $$$w_1$$$ и $$$w_2$$$ $$$-$$$ веса дорог из оптимального пути. Пусть $$$d_i$$$ $$$-$$$ минимальное число монет, которое будет когда мы попадем из $$$n$$$ в $$$i$$$, тогда можно легко восстановить все веса ребер из $$$i$$$ в соответствии с неравенством выше. Теперь задача свелась к тому что надо найти кратчайший путь из $$$n$$$ в $$$1$$$. Для этого можно воспользоваться алгоритмом Дейкстры (он работает, так как ребра не изменяются случайно, и отрицательных ребер нет).
2 решение:
Будем бинпоиском перебирать ответ: тогда для каждого возможного ответа сделаем обычную Дейкстру (просто веса будут изменятся в зависимости от кратчайшего пути в вершину). Проверяем что расстояние то вершины $$$n$$$ больше или равно $$$t$$$.
В обоих решениях асимптотика $$$\mathcal{O}(n \cdot log(n) \cdot log(10^9))$$$.
В коде написано первое решение.
#include <iostream>
#include <fstream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <string>
#include <set>
#include <cmath>
#include <deque>
#include <map>
#include <cassert>
#include <queue>
#include <unordered_set>
using namespace std;
typedef long long ll;
typedef __int128 lll;
typedef long double ld;
const ll mod = 1e9 + 7, inf = 2e18 + 1;
const ld eps = 1e-9, pi = 3.1415926;
#define all(a) a.begin(), (a).end()
ll f(ll d, ll w) {
if (d < w)
return d;
ll l = 0, r = 1000000001, md;
while (l + 1 < r) {
md = (l + r) / 2;
if (md - md / w >= d)
r = md;
else
l = md;
}
return r;
}
int main() {
ios_base::sync_with_stdio(false);
//ifstream cin("line3.in");
//ofstream cout("line3.out");
cin.tie(nullptr);
cout.tie(nullptr);
//in.tie(nullptr);
//out.tie(nullptr);
ll n, m, t, i;
cin >> n >> m >> t;
vector<vector<pair<ll, ll>>> g(n);
while (m--) {
ll u, v, w;
cin >> u >> v >> w;
u--;
v--;
g[u].push_back({v, w});
g[v].push_back({u, w});
}
vector<ll> d(n, inf);
d[n - 1] = t;
set<pair<ll, ll>> st;
st.insert({t, n - 1});
while (!st.empty()) {
ll v = st.begin()->second;
st.erase(st.begin());
for (auto it:g[v])
if (d[it.first] > f(d[v], it.second)) {
st.erase({d[it.first], it.first});
d[it.first] = f(d[v], it.second);
st.insert({d[it.first], it.first});
}
}
cout << d[0];
}
Привет, Codeforces! Мы с sdyakonov приглашаем вас на [contest:382218], который состоится в [contest_time:382218]. Приглашаем всех желающих. Контест будет не рейтинговый. Соревнование будет проводиться по стандартам ICPC. Всего будет 11 задач. Контест будет больше всего интересен экспертам или ниже. Но мы приглашаем поучаствовать фиолетовых и выше. Контест будет в этой группе.
Задачи были подготовлены sdyakonov, Kirill020708, onlytrall
Условия будут на английском и русском языках
Спасибо за подготовку контеста следующим людям:
Также большое спасибо MikeMirzayanov за системы Polygon и Codeforces!
Удачи!
UPD: Контест будет длиться 2 часа
Название |
---|