Первый решивший: rob00
Давайте рассмотрим $$$2$$$ случая.
- Если $$$x \geq y$$$. В этом случае, каждую секунду блендер будет смешивать $$$min(y, c)$$$ фруктов (где $$$c$$$ — это количество не смешанных фруктов). Cледовательно, ответ будет $$$\lceil {\frac{n}{y}} \rceil$$$.
- Если $$$x < y$$$. Здесь каждую секунду блендер будет смешивать $$$min(x, c)$$$ фруктов. В этом случае ответ будет равен $$$\lceil {\frac{n}{x}} \rceil$$$ аналогично.
Таким образом, итоговый ответ — это $$$\lceil {\frac{n}{min(x, y)}} \rceil$$$.
#include <iostream>
using namespace std;
int main(){
int t = 1;
cin >> t;
while(t--){
int n, x, y;
cin >> n >> x >> y;
x = min(x, y);
cout << (n + x - 1) / x << endl;
}
}
Первый решивший: neal
Можно заметить, что значение $$$a_{n-1}$$$ всегда будет отрицательным в итоговом ответе.
Следовательно, мы можем вычесть сумму $$$a_1 + a_2 + \ldots + a_{n-2}$$$ из $$$a_{n-1}$$$, а затем вычесть $$$a_{n-1}$$$ из $$$a_n$$$.
Таким образом, итоговая сумма будет равна $$$a_1 + a_2 + \ldots + a_{n-2} - a_{n-1} + a_n$$$. Больше этого значения получить нельзя, так как $$$a_{n-1}$$$ всегда будет отрицательным.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
void solve(){
int n;
cin >> n;
ll ans = 0;
vector<int> a(n);
for(int i=0;i<n;i++){
cin >> a[i];
ans += a[i];
}
cout << ans - 2 * a[n - 2] << '\n';
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t;
cin >> t;
while(t--){
solve();
}
}
Первый решивший: Pagode_Paiva
Будем поддерживать изначально пустую строку $$$t$$$, так чтобы $$$t$$$ встречалась в $$$s$$$ как подстрока.
Будем увеличивать строку $$$t$$$ на один символ, пока её длина меньше $$$n$$$.
Проведём $$$n$$$ итераций. На каждой из них будем проверять строки $$$t + 0$$$ и $$$t + 1$$$. Если одна из них встречается в $$$s$$$ как подстрока, то добавим нужный символ в конец $$$t$$$ и перейдём к следующей итерации.
Если ни одна из этих двух строк не встречается в $$$s$$$, то это значит, что строка $$$t$$$ является суффиксом строки $$$s$$$. После этой итерации будем проверять строку $$$0 + t$$$. Если она встречается в $$$s$$$, то добавим $$$0$$$ к $$$t$$$, иначе добавим $$$1$$$.
Итого, на каждой итерации мы выполняем по 2 запроса, кроме одной итерации, на которой выполняем 3 запроса. Однако после этой итерации будем делать только по 1 запросу, поэтому суммарно потребуется не более $$$2 \cdot n$$$ запросов.
#include <iostream>
#include <vector>
#include <string>
#include <array>
using namespace std;
bool ask(string t) {
cout << "? " << t << endl;
int res;
cin >> res;
return res;
}
void result(string s) {
cout << "! " << s << endl;
}
void solve() {
int n;
cin >> n;
string cur;
while (cur.size() < n) {
if (ask(cur + "0")) {
cur += "0";
} else if (ask(cur + "1")) {
cur += "1";
} else {
break;
}
}
while ((int) cur.size() < n) {
if (ask("0" + cur)) {
cur = "0" + cur;
} else{
cur = "1" + cur;
}
}
result(cur);
}
int main() {
int t;
cin >> t;
while (t--)
solve();
}
2013D — Минимизировать разность
Первый решивший: edogawa_something
Первое утверждение: если $$$a_i > a_{i+1}$$$, то в этом случае всегда выгодно сделать операцию на позиции $$$i$$$. Следовательно, конечный массив будет неубывающим.
Второе утверждение: если массив неубывающий, то делать операции невыгодно.
Будем поддерживать стек, в котором будет храниться отсортированный массив. Каждый элемент в стеке будет представлять пару $$$x, cnt$$$, где $$$x$$$ — значение, а $$$cnt$$$ — количество его вхождений.
При добавлении $$$a_i$$$ в стек будем хранить сумму удалённых элементов $$$sum$$$ из стека и их количество $$$cnt$$$. Изначально $$$sum = a_i$$$, $$$cnt = 1$$$. Мы будем удалять последний элемент из стека, пока он меньше, чем $$$ \frac{sum}{cnt}$$$. После этого пересчитываем $$$sum$$$ и $$$cnt$$$. Затем добавим в стек пары $$$\left( \frac{sum}{cnt}, cnt - sum \mod cnt \right)$$$ и $$$\left( \frac{sum}{cnt} + 1, sum \mod cnt \right) $$$.
Временная сложность алгоритма — $$$O(n)$$$, так как на каждой итерации добавляется не более 2 элементов в стек, и каждый элемент удаляется не более одного раза.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a[200200];
int n;
void solve(){
cin >> n;
for(int i=1;i<=n;i++){
cin >> a[i];
}
stack<pair<ll, int>> s;
for(int i=1;i<=n;i++){
ll sum = a[i], cnt = 1;
while(s.size() && s.top().first >= sum / cnt){
sum += s.top().first * s.top().second;
cnt += s.top().second;
s.pop();
}
s.push({sum / cnt, cnt - sum % cnt});
if(sum % cnt != 0){
s.push({sum / cnt + 1, sum % cnt});
}
}
ll mx = s.top().first;
while(s.size() > 1){
s.pop();
}
cout << mx - s.top().first << '\n';
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t = 1;
cin >> t;
while(t--){
solve();
}
}
Первый решивший: meme
Пусть $$$g$$$ — наибольший общий делитель массива $$$a$$$. Поделим каждый элемент $$$a_i$$$ на $$$g$$$, а в конце просто умножим результат на $$$g$$$.
Рассмотрим следующий жадный алгоритм. Создадим изначально пустой массив $$$b$$$ и будем добавлять в конец массива $$$b$$$ элемент, который минимизирует НОД с уже имеющимся массивом $$$b$$$. Можно заметить, что НОД через максимум 10 итераций станет равным 1. После этого можно в любом порядке добавить оставшиеся элементы.
Пусть $$$A$$$ — это минимально возможный НОД для текущего префикса массива $$$b$$$, а $$$B$$$ — оптимальный ответ, такой что $$$A < B$$$. Тогда мы можем сначала поставить $$$A$$$, а затем записать последовательность $$$B$$$, в том же порядке. Ответ не ухудшится, так как $$$A + gcd(A, B) \leq B$$$.
Временная сложность алгоритма: $$$O(n \cdot 10)$$$.
#include <bits/stdc++.h>
using namespace std;
int a[200200];
int n;
void solve(){
cin >> n;
int g = 0, cur = 0;
long long ans = 0;
for(int i=0;i<n;i++){
cin >> a[i];
g = __gcd(g, a[i]);
}
for(int i=0;i<n;i++){
a[i] /= g;
}
for(int t=0;t<n;t++){
int nc = 1e9;
for(int i=0;i<n;i++){
nc = min(nc, __gcd(cur, a[i]));
}
cur = nc;
ans += cur;
if(cur == 1) {
ans += n - t - 1;
break;
}
}
cout << ans * g << '\n';
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t = 1;
cin >> t;
while(t--){
solve();
}
}
2013F1 — Игра на дереве (простая версия)
Первый решивший: EnofTaiPeople
Сначала разберём, как будет проходить игра. Алиса и Боб начинают двигаться друг к другу по пути от вершины $$$1$$$ к вершине $$$u$$$. В какой-то момент один из игроков может свернуть в поддерево вершины, которая не лежит на пути $$$(1, u)$$$. После этого оба игрока идут в самую дальнюю доступную вершину.
Пусть путь от вершины $$$1$$$ до вершины $$$u$$$ обозначается как $$$(p_1, p_2, \dots, p_m)$$$, где $$$p_1 = 1$$$ и $$$p_m = u$$$. Изначально Алиса стоит в вершине $$$p_1$$$, а Боб — в вершине $$$p_m$$$.
Для каждой вершины на пути $$$(p_1, p_2, \dots, p_m)$$$ введём два значения:
$$$a_i$$$ — это количество вершин, которые посетит Алиса, если она спустится в поддерево вершины $$$p_i$$$, которое не лежит на пути $$$(1, u)$$$;
$$$b_i$$$ — это количество вершин, которые посетит Боб, если он спустится в поддерево вершины $$$p_i$$$, которое также не лежит на этом пути.
Обозначим расстояние до самой дальней вершины в поддереве вершины $$$p_i$$$ как $$$d_{p_i}$$$. Тогда:
$$$a_i = d_{p_i} + i$$$ — количество вершин, которые Алиса может посетить, если она спустится в поддерево на вершине $$$p_i$$$;
$$$b_i = d_{p_i} + m - i + 1$$$ — количество вершин, которые Боб может посетить, если он спустится в поддерево на вершине $$$p_i $$$.
Теперь рассмотрим, что происходит, если Алиса стоит на вершине $$$p_i$$$, а Боб на вершине $$$p_j$$$. Если Алиса решит спуститься в поддерево вершины $$$p_i$$$, то она посетит $$$a_i$$$ вершин. В это время Боб может дойти до любой вершины на подотрезке $$$(p_i, p_{i+1}, \dots, p_j)$$$. Бобу выгодно спуститься в поддерево на вершине с максимальным значением $$$b_k$$$, где $$$k \in [i+1, j] $$$.
Следовательно, Алисе выгодно спуститься в поддерево вершины $$$p_i$$$, если выполняется условие: $$$a_i > \max(b_{i+1}, b_{i+2}, \dots, b_j)$$$ Иначе она должна перейти на вершину $$$p_{i+1}$$$.
Для Боба ситуация аналогична: он спускается в поддерево вершины $$$p_j$$$, если для него выполняется условие, аналогичное условию для Алисы.
Для того чтобы эффективно находить максимум на подотрезке $$$(p_{i+1}, \dots, p_j)$$$, можно использовать дерево отрезков или разреженную таблицу. Это позволяет находить максимум за $$$O(log n)$$$ для каждого запроса, что даёт общую временную сложность $$$O(nlog n)$$$.
Однако можно доказать, что вместо использования дерева отрезков или разреженной таблицы можно просто пробегаться по всем вершинам на подотрезке и завершать цикл при нахождении большей вершины. Это даст решение с временной сложностью $$$O(n)$$$.
#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 12;
vector<int> g[maxn];
vector<int> ord;
int dp[maxn];
int n, m, k;
bool calc(int v, int p, int f){
bool is = 0;
if(v == f) is = 1;
dp[v] = 1;
for(int to:g[v]){
if(to == p){
continue;
}
bool fg = calc(to, v, f);
is |= fg;
if(fg == 0){
dp[v] = max(dp[v], dp[to] + 1);
}
}
if(is){
ord.push_back(v);
}
return is;
}
struct segtree {
int t[maxn * 4];
void build (int v, int tl, int tr, vector <int>& a) {
if (tl == tr) {
t[v] = a[tl];
return;
}
int tm = (tl + tr) >> 1;
build (v * 2, tl, tm, a);
build (v * 2 + 1, tm + 1, tr, a);
t[v] = max(t[v * 2], t[v * 2 + 1]);
}
int get (int v, int tl, int tr, int l, int r) {
if (tr < l || r < tl) return 0;
if (l <= tl && tr <= r) return t[v];
int tm = (tl + tr) >> 1;
return max(get(v * 2, tl, tm, l, r), get(v * 2 + 1, tm + 1, tr, l, r));
}
} st_a, st_b;
int get(int v){
ord.clear();
calc(1, 0 , v);
int m = ord.size();
reverse(ord.begin(), ord.end());
vector<int> a(m), b(m);
for(int i=0;i<m;i++){
a[i] = dp[ord[i]] + i;
b[i] = dp[ord[m - i - 1]] + i;
}
st_a.build(1, 0, m-1, a);
st_b.build(1, 0, m-1, b);
for(int i=0;i < (m + 1) / 2;i++){
if(a[i] > st_b.get(1, 0, m-1, i, m - i - 2)){
return 1;
}
if(b[i] >= st_a.get(1, 0, m-1, i + 1, m - i - 2)){
return 0;
}
}
}
void solve(){
cin >> n;
for(int i=1;i<=n;i++){
g[i].clear();
}
for(int i=1;i<n;i++){
int a, b;
cin >> a >> b;
g[a].push_back(b);
g[b].push_back(a);
}
int u, v;
cin >> u >> v;
ord.clear();
calc(v, 0, u);
auto p = ord;
for(int x:p){
if(get(x) == 1){
cout << "Alice\n";
}
else{
cout << "Bob\n";
}
}
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t = 1;
cin >> t;
while(t--){
solve();
}
}
#include <bits/stdc++.h>
using namespace std;
int dfs(int v, int p, int to, const vector<vector<int>> &g, vector<int> &max_depth) {
int ans = 0;
bool has_to = false;
for (int i : g[v]) {
if (i == p) {
continue;
}
int tmp = dfs(i, v, to, g, max_depth);
if (tmp == -1) {
has_to = true;
} else {
ans = max(ans, tmp + 1);
}
}
if (has_to || v == to) {
max_depth.emplace_back(ans);
return -1;
} else {
return ans;
}
}
int solve(const vector<vector<int>> &g, int to) {
vector<int> max_depth;
dfs(0, -1, to, g, max_depth);
int n = max_depth.size();
reverse(max_depth.begin(), max_depth.end());
int first = 0, second = n - 1;
while (true) {
{
int value1 = max_depth[first] + first;
bool valid = true;
for (int j = second; j > first; --j) {
if (value1 <= max_depth[j] + (n - j - 1)) {
valid = false;
break;
}
}
if (valid) {
return 0;
}
++first;
if (first == second) {
return 1;
}
}
{
int value2 = max_depth[second] + (n - second - 1);
bool valid = true;
for (int j = first; j < second; ++j) {
if (value2 < max_depth[j] + j) {
valid = false;
break;
}
}
if (valid) {
return 1;
}
--second;
if (first == second) {
return 0;
}
}
}
}
void solve() {
int n;
cin >> n;
vector<vector<int>> g(n);
for (int i = 0; i < n - 1; ++i) {
int a, b;
cin >> a >> b;
g[a - 1].push_back(b - 1);
g[b - 1].push_back(a - 1);
}
int s, f;
cin >> s >> f;
--s, --f;
int ans = solve(g, s);
if (ans == 0) {
cout << "Alice\n";
} else {
cout << "Bob\n";
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
int t;
cin >> t;
while (t--)
solve();
}
2013F2 — Игра на дереве (сложная версия)
Первый решивший: rainboy
Прочтите разбор простой версии задачи.
Путь $$$(u, v)$$$ можно разбить на два вертикальных пути $$$(1, u)$$$ и $$$(1, v)$$$, далее мы будем решать для вершин на пути $$$(1, u)$$$, путь $$$(1, v)$$$ решается аналогично.
Для каждой вершины на пути $$$(1, u)$$$, введем два значения.
- $$$fa_i$$$ — Первая вершина на которой победит Алиса, если спустится в поддерево, когда Боб начинает с вершины $$$p_i$$$.
- $$$fb_i$$$ — Первая вершина на который Победит Боб если спустится в поддерево, когда Боб начинает с вершины $$$p_i$$$.
Утверждение, Алисе выгодно спускаться в поддерево вершины $$$v$$$, только на каком-то подотерзке вершин с которых начинает Боб. Аналогичное утверждение выполняется и для Боба.
Теперь нужно для каждой вершины Алисы, определить отрезок на котором нам будет выгодно спускаться. Левая граница отрезка для вершины $$$p_i$$$, будет равна $$$2 \cdot i$$$, так как Алиса всегда будет на левой половине пути. Не трудно заметить, что правую границу отрезка можно находиться с помощью бинарного поиска.
Переопределим значение $$$b_i$$$, приравняем его к $$$d_{p_i} - i$$$. Чтобы проверить выгодно ли нам спускаться в поддереве для фиксированной середины $$$mid$$$, нам необходимо чтобы выполнялось следующее условие: $$$a_i > max(b_{i+1}, b_{i+2}, \ldots, b_{mid - i}) + mid$$$.
Обозначним за $$$(l_j, r_j)$$$, подотрезок на котором Алисе выгодно спуститься вниз, если Боб начнет с вершины $$$p_j$$$. Тогда значение $$$fa_i$$$ ,будет равно минимальной позиции $$$j$$$, на которой выполняется следующее условие: $$$l_j \leq i \leq r_j$$$, это можно находиться с использованием сета.
Значение $$$fb_i$$$, считается аналогично.
Алиса выигрывает на вершине $$$p_i$$$, если $$$fa_i \leq i - fb_i$$$, в противном случае побеждает Боб.
Для эффективного нахождения максимума на подотрезке, можно использовать разряженную таблицу. Также использование сетов и бинарных поисков дает нам временную сложность $$$O(nlogn)$$$.
#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 12;
vector<int> g[maxn], del[maxn], add[maxn];
vector<int> ord;
int ans[maxn];
int dp[maxn];
int n, m, k;
bool calc(int v, int p, int f){
bool is = 0;
if(v == f) is = 1;
dp[v] = 1;
for(int to:g[v]){
if(to == p){
continue;
}
bool fg = calc(to, v, f);
is |= fg;
if(fg == 0){
dp[v] = max(dp[v], dp[to] + 1);
}
}
if(is){
ord.push_back(v);
}
return is;
}
struct sparse {
int mx[20][200200], lg[200200];
int n;
void build(vector<int> &a){
n = a.size();
for(int i=0;i<n;i++){
mx[0][i] = a[i];
}
lg[0] = lg[1] = 0;
for(int i=2;i<=n;i++){
lg[i] = lg[i/2] + 1;
}
for(int k=1;k<20;k++){
for(int i=0;i + (1 << k) - 1 < n;i++){
mx[k][i] = max(mx[k-1][i], mx[k-1][i + (1 << (k - 1))]);
}
}
}
int get (int l, int r) {
if(l > r) return -1e9;
int k = lg[r-l+1];
return max(mx[k][l], mx[k][r - (1 << k) + 1]);
}
} st_a, st_b;
void solve(int v){
ord.clear();
calc(1, 0, v);
reverse(ord.begin(), ord.end());
m = ord.size();
vector<int> a(m+1), b(m+1);
vector<int> fa(m+1, 1e9), fb(m+1, -1e9);
for(int i=0;i<m;i++){
a[i] = dp[ord[i]] + i;
b[i] = dp[ord[i]] - i;
del[i].clear();
add[i].clear();
}
st_a.build(a);
st_b.build(b);
multiset<int> s;
for(int i=1;i<m;i++){
int pos = i;
for(int l=i+1, r=m-1;l<=r;){
int mid = l + r >> 1;
if(st_b.get(i+1 , mid) + mid < a[i] - i){
pos = mid;
l = mid + 1;
}
else r = mid - 1;
}
if(i < pos){
add[min(m, 2 * i)].push_back(i);
del[min(m, pos + i)].push_back(i);
}
for(int x:add[i]){
s.insert(x);
}
if(s.size()) fa[i] = *s.begin();
for(int x:del[i]){
s.erase(s.find(x));
}
}
s.clear();
for(int i=0;i<=m;i++){
add[i].clear();
del[i].clear();
}
for(int i=1;i<m;i++){
int pos = i;
for(int l=1, r = i-1;l<=r;){
int mid = l + r >> 1;
if(st_a.get(mid, i-1) - mid + 1 <= b[i] + i){
pos = mid;
r = mid - 1;
}
else l = mid + 1;
}
pos--;
if(pos >= 0){
add[min(m, pos + i)].push_back(i);
del[min(m, 2 * i - 1)].push_back(i);
}
for(int x:add[i]){
s.insert(x);
}
if(s.size()) fb[i] = *s.rbegin();
for(int x:del[i]){
s.erase(s.find(x));
}
}
for(int i=m-1;i>0;i--){
b[i] = max(b[i+1] + 1, dp[ord[i]]);
if(b[i] >= st_a.get(1, i-1)){
fb[i] = i;
}
if(a[0] > max(st_b.get(1, i-1) + i, b[i])){
fa[i] = 0;
}
ans[ord[i]] = 0;
if(fa[i] <= i - fb[i]){
ans[ord[i]] = 1;
}
}
}
void solve(){
cin >> n;
for(int i=1;i<=n;i++){
g[i].clear();
}
for(int i=1;i<n;i++){
int a, b;
cin >> a >> b;
g[a].push_back(b);
g[b].push_back(a);
}
int u, v;
cin >> u >> v;
solve(u), solve(v);
ord.clear();
calc(v, 0, u);
auto p = ord;
for(int x:p){
if(ans[x] == 1){
cout << "Alice\n";
}
else{
cout << "Bob\n";
}
}
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t = 1;
cin >> t;
while(t--){
solve();
}
}
Problem E originally meant a solution without a gready, but what are rich in :)
And in F you need to separately figure out when the first / second player wins if he starts at his top, because otherwise it hurts a lot)
any intuitive / formal proof to D ? i have a weird one that i'll write when i have time
why is cout.flush() not required in question C?
:< could someone explain why cout<<ceil(double(n) / min(x,y)); in A led to WA
There are two reasons this may cause issue
first (which is mostly the issue here), the output will be in scientific notation
this can be solved by casting the output to long/int
Another issue which usually happens with large numbers is that double may not be precise enough, for example
Here the answer is off by 1 because double is not precise enough, a good solution for both these issues is to not use double for calculating ceil, instead you can calculate it using this
$$$ceil(a/b) = floor((a + b - 1) / b)$$$
Which can be written like this: