If you have a solution other than the author's, write it in the comments. There is a feedback window under each solution, please rate all the tasks. Contest: Contest.
Автор: sdyakonov
Let's note that ai>0, so MEX(a1,a2,...,an)=0. So if k=ai for some i, it means that the new MEX will be greater than 0. So you need to output any number that is not in the array.
#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();
}
}
Task B: Andrey and the monsters
Author: onlytrall
Firstly, healers do not cause any damage, so their presence does not affect the task in any way.
Let's write out all the damage received by Andrey: damage=0+k+2⋅k+⋯+x⋅k, where x is the maximum at which x⋅k≤n is executed. Let's try to find him. This condition is equivalent to x≤nk, so x=⌊nk⌋. Now it remains to find the sum of k+2⋅k+⋯+x⋅k, while x is already known. It can be noticed that all terms are multiples of k, it can be taken out: damage=k⋅(1+2+3+⋯+x). The sum of x∑i=1i is equal to x⋅(x+1)2, so the answer is k⋅⌊nk⌋⋅(⌊nk⌋+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();
}
}
Task C: Sergey and four numbers
Author: sdyakonov
As is known, for x≥y, gcd(x,y)=gcd(x−y,y) is executed.
Therefore gcd(a+2b,a+b)=gcd(a+b,b)=gcd(a,b), and gcd(b+4c,b+3c)=gcd(b+3c,c)=gcd(b,c)
It remains only to find such different a,b,c such that gcd(a,b)=gcd(b,c)=d. There are many ways to choose them, but the easiest option is 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
Square 2×2 we can color 14 in ways: 24−2 (24 this is the number of ways to color a square, 2 ways are incorrect when we turn the whole square either white or black). There are total of such squares n24. So the answer is 14n24. For a quick exponentiation, we use binary exponentiation.
#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';
}
}
Author: sdyakonov
In the task, we are required to implement a stack with support for gcd
Let's learn how to answer each query for O(1) To do this, we will store a pair of numbers in the stack — the element itself, as well as gcd elements lying in the stack no higher than this. In other words:
stacki.first=ai
stacki.second=gcd(a1,a2,...,ai)
Then gcd of the entire stack will be in stack.top().second
To make a deletion request, it is enough to delete the top element of the stack, since it does not affect the previous elements.
To add an element to the stack, we need to add a pair of element,gcd(stack.top().second,element) (we must not forget to consider the case when the stack is empty)
#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 Problem: Sergey and prime numbers (simple version)
Author: sdyakonov
First consider x≤11. It's easy to make sure that only 8 and 10 are good ones. Next, x>11 are considered.
Next, we note that one of the numbers x−4, x−6, x−8 will be composite, because it will be divisible by 3 (but not equal to three). Consequently, one of the pairs (4,x−4), (6,x−6), (8,x−8) will fit, so the answer is always 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();
}
}
Task F2: Sergey and prime numbers (complex version)
Author: sdyakonov
Solution 1:
Let's apply Goldbach's binary theorem (any even number starting from 4 can be represented as the sum of two primes). Then if 2 then the answer is NO. Otherwise, YES. Now note that an odd number is always the sum of an even number + an odd number. Since the only prime number is 2, it means we need to check that x−2 is prime.
Solution 2:
Let's use the Eratosthenes sieve to calculate all the primes up to 106. It turns out that if there is such a y that y and x−y are prime numbers, then min(y,x−y)≤600. So you can iterate over the number y up to 600 and check with a sieve whether x−y is simple.
#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();
}
}
Task G: Kirill and the vaccine
Author: Kirill020708
To begin with, we note that such a greedy algorithm is possible: while there are infected residents in the first city, we will fly on a segment of cities from 1 to k (otherwise we will not cure the first city in any way). After that, you can simply not fly over this city (since if we fly over it, we will not cure anyone in it, and it is better to start flying from the second city so that it is possible to treat residents in the k+1 city. That is, we will remove the first city and solve the problem on the remaining cities (if we have k cities, then there will be only one way to cure all residents: let x − be the maximum number of infected residents in the city. Then add ⌈xk⌉ to the answer.
It remains only to quickly update the number of infected residents in cities from l to l+k−1 (when we fly over these cities). This can be done either through a tree of segments (then the asymptotics is O(n⋅log(n)), or you can store for each city how many segments begin in it and how many segments end in it, in the variable store how many segments contain the current city, then when switching to we add to this variable the number of segments starting in this city, and when considering it, we subtract from this variable the number of segments ending in the current city. When we count how many times we need to start flights in the
Unable to parse markup [type=CF_MATHJAX]
\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;
}
Author: Kirill020708
To begin with, note that if gcd(x,y)>1, then gcd(x⋅k,y)>1 for any natural k. It follows from this that if we build a graph of n vertices, where two vertices are connected by an edge if gcd of the corresponding numbers in the multiset >1, then during the game these vertices (and the edges of these vertices) will simply merge and will not change. Then the answer will simply be a set of multiplications of all the numbers in each component of the graph.
We need to learn how to build a graph quickly. In fact, we don't need a graph, we just need a partition into components in the graph. To do this, you can use the fast factorization of n numbers (you can read about it on the Internet, but the bottom line is that for each number in the sieve of Eratosthenes, we will not store the simplicity of this number, but any prime number not equal to it, by which our number is divided. Then factorize the number x in this way: let fx− be any prime number by which x is divisible, while fx<x. Then we add the number fx to our set of easy-to-decompose x and we will continue to solve the problem for xfx). Then we will profactorize all n numbers and combine them for each divisor (I did it through the SNM, but you can just store the graph, then the asymptotics will be reduced by log(n) times). Next, for each set, we calculate the multiplication of the numbers in it by the desired modulus and output these numbers. The asymptotics of the author's solution O(107⋅log(107)+n⋅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 << ' ';
}
Author: sdyakonov
We will search for the number of r for each l separately.
Let's forget about the condition gcd(al,ar)>1 for now. Then now the task is to find for each l the minimum r at which gcd(al,al+1,...,ar)=1 is executed. This can be done using bin-search, having previously written a tree of segments or sparse table to quickly find gcd on a segment.
We have learned to find a suffix for each l on which we can choose r. Now we need to quickly count on this suffix the number of r such that gcd(al,ar)>1. Note that 2≤ai≤1000, so we can calculate the number of r on all suffixes for all possible ai.
Let dp[x][i] be the number of numbers on the suffix ai,ai+1,...,an−1 that are not mutually prime with x. As a base of dynamics, we will make dp[x][n]=0. The dynamics is recalculated simply — dp[x][i]=dp[x][i+1]+(gcd(x,ai)>1). By calculating such dynamics for all x from 2 to 1000, we will be able to quickly get the number of numbers we need on the suffix.
#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();
}
}//
Author: Kirill020708
1 solution:
We will look for the answer from the end, assuming that upon arrival at the vertex n there will be exactly t coins left. Then for 1 step before arrival we will have x coins such that x−xw1≥t, and x is minimal, for 2 steps y−yw2≥x, etc., where w1 and w2 are the weights of the roads from the optimal path. Let di be the minimum number of coins that will be when we get from n to i, then we can easily restore all the edge weights from i in accordance with the inequality above. Now the task has been reduced to finding the shortest path from n to 1. To do this, you can use Dijkstra's algorithm (it works because the edges do not change randomly, and there are no negative edges).
2 solution:
We will search through the answer by bin-search: then we will make a regular Dijkstra for each possible answer (just the weights will change depending on the shortest path to the vertex). We check that the distance of the vertex n is greater than or equal to t.
In both solutions, the asymptotics of O(n⋅log(n)⋅log(109)).
The first solution is written in the code.
#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];
}