Первый решивший: 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();
}
}