Всем привет! Сегодня я хотел бы представить разбор на вчерашний раунд. Если какая-то часть останется не до конца ясной, смело смотрите код — он полностью прояснит решение.
Полное решение:
Заметим:
- если a < b, то ответ всегда равен 2. Мы можем сначала выбрать a, затем b.
Пример: a = 2, b = 5 → 2 → 5.
- если a > b, то ответ не может быть 2.
Пример: a = 4, b = 2. Если взять 4, то потом выбрать 2 нельзя.
Однако есть другой способ:
- если
a > bиa - 1 > b, то можно выбрать1, затемb, и затемa - (b+1). Всего получится3хода. - если же
a - 1 == b, то решение невозможно. Пример:a = 5, b = 4. После выбора1и4придётся снова выбрать4, но это запрещено. Ответ:-1.
Алгоритм:
- Если
a < b→ ответ2. - Если
a > bиa - 1 > b→ ответ3. - Если
a - 1 == b→ ответ-1.
#include <iostream>
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define f first
#define s second
#define all(x) x.begin(),x.end()
#define allr(x) x.rbegin(),x.rend()
using namespace std;
//vector<ll> vis;void
void bruh(){
ll a,b; cin >> a >> b;
if(b>a){
cout << 2 << endl;
}else{
if(b>=2 && a-b>=2){
cout << 3 << endl;
}else{
cout << -1 << endl;
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
ll t; cin >> t;
// cout << dp[3][2] << endl;
// for (ll i = 1;)
while (t--){
bruh();
}
}
Полное решение:
Идея: Заметим, что 1,1+n, 2,2-n-1,... такое решение будет работать всегда. Иногда индексы могут перекрываться, поэтому будем делать это пока индекс не свободно x+n-(x-1)..... Для каждого таких индексов ставим n, a[l] = n, a[l+n-(l-1)], и снизим наш н. Это гарантирует для каждого n, что дистанция будет делиться на n.
Алгоритм:
- Идём по индексам и формируем пары с расстоянием
n. - Заполняем значения.
- Уменьшаем
nи повторяем. - Выводим перестановку.
#include <iostream>
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define f first
#define s second
#define all(x) x.begin(),x.end()
#define allr(x) x.rbegin(),x.rend()
using namespace std;
//vector<ll> vis;void
void bruh(){
ll n; cin >> n;
vector<ll> temp(n*2+1);
vector<bool> vis(n*2+1,0);
ll st = n;
ll ind = 1;
ll cnt = 0;
while (st>0){
ll j = ind;
vis[j] = 1;
while (vis[j]){
j+=st;
// vis[j] = st;
}
temp[ind] = st;
temp[j] = st;
vis[ind] = 1;
vis[j] = 1;
st--;
ind++;
}
for (ll i = 1;i<=n*2;i++){
cout << temp[i] << " ";
}cout <<endl;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
ll t; cin >> t;
// cout << dp[3][2] << endl;
// for (ll i = 1;)
while (t--){
bruh();
}
}
Полное решение:
Рассмотрим, когда ответ невозможен:
- базовый плохой случай — подстрока 101.
В этом случае кролика перекрывают два непустых горшка, и сделать ничего нельзя.
- более сложные варианты (100101, 010011 и т.д.) тоже сводятся к наличию шаблона 101.
Таким образом, условие сводится к проверке на подстроку 101.
Алгоритм:
- Заводим два указателя.
- Ищем чередующуюся последовательность, начинающуюся с
1. - Если её длина кратна
3, то где-то внутри обязательно будет101, → ответ "NO". - Иначе выводим "YES".
#include <iostream>
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define f first
#define s second
#define all(x) x.begin(),x.end()
#define allr(x) x.rbegin(),x.rend()
using namespace std;
//vector<ll> vis;void
void bruh(){
ll n; cin >> n;
string s; cin >> s;
// bool opt = 1;
// ll i = 0;
vector<ll> ind;
for (ll i = 0;i<n;i++){
if(s[i]=='0'){
ind.pb(i);
}
}
vector<ll> preff(n,0);
vector<ll> suff(n,0);
vector<vector<ll>> dp(n,vector<ll>(2));
ll lst = -1;
ll i = 0;
bool check = 1;
while (i<n){
ll j = i+1;
bool opt = (s[i]=='1');
while (j<n && s[j]!=s[j-1]){
j++;
}
// cout << opt << endl;
// cout << j-i<< endl;
if(opt && (j-i)%4==3){
check = 0;
break;
}
i = j;
}
cout << (check?"YES": "NO") << endl;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
ll t; cin >> t;
// cout << dp[3][2] << endl;
// for (ll i = 1;)
while (t--){
bruh();
}
}
Полное решение:
Разберём отдельно два случая:
- Если
xчётное. Пусть у Алисыsum1, у Бобаsum2. Тогда после выбора хода суммы будут меняться так:
(sum1+f(x)), (sum2+f(x-1)), (sum1+f(x-2)), (sum2+f(x-3))...
В итоге оба игрока могут сделать так, чтобы суммы были равны.
- Если
xнечётное. Теперь счёт всегда смещается в пользу того, кто сделал ход. Игроки будут выбирать только нечётные числа, причём самые выгодные (с максимальнымf(x)).
Подсчёт:
- для нечётных
xвклад в счёт:
sum += ((x+1)/2) * f(x)
(для игрока, чей ход). * у второго игрока остаётся:
sum2 += (x - (x+1)/2) * f(x). * для чётных x вклад одинаковый для обоих игроков, поэтому порядок ходов не важен.
Алгоритм:
- Подсчитать
f(x)для каждого элемента. - Разбить на чётные и нечётные.
- Отсортировать нечётные по убыванию частоты.
- Ход за ходом распределять числа:
- если ход Алисы → она берёт лучшие нечётные;
- если ход Боба → он берёт следующие.
- Добавить чётные к обеим суммам поровну.
- Вывести суммы Алисы и Боба.
#include <iostream>
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define f first
#define s second
#define all(x) x.begin(),x.end()
#define allr(x) x.rbegin(),x.rend()
using namespace std;
//vector<ll> vis;void
void bruh(){
ll n; cin >> n;
vector<ll> a(n);
vector<pair<ll,ll>> ans;
map<ll,ll> mp;
for (ll &x: a){
cin >> x;
mp[x]++;
}
map<ll,ll> mpp;
vector<pair<ll,ll>> anss;
for (ll x: a){
mpp[x]++;
if(mpp[x]==1 && x%2==1){
ans.pb({mp[x],x});}else{
if(mpp[x]==1 & x%2==0){
anss.pb({mp[x],x});
}
}
}
sort(all(ans),[](const auto &x, const auto &y){
if(x.f!=y.f){
return x.f>y.f;
}else{
return x.s>y.s;
}
});
ll hod= 1;
ll sm1 = 0; ll sm2 = 0;
for (ll i = 0;i<ans.size();i++){
ll x = ans[i].f;
ll y = ans[i].s;
if(hod){
sm1+=((y+1)/2)*x;
sm2+=(y-(y+1)/2)*x;
// hod = 0;
}else{
sm1+=((y)/2)*x;
sm2+=(y-(y/2))*x;
// hod = 1;
}
if(y%2==1){
hod = (hod? 0: 1);
}
}
hod = 1;
for (ll i = 0;i<anss.size();i++){
ll x = anss[i].f;
ll y = anss[i].s;
if(hod){
sm1+=((y+1)/2)*x;
sm2+=(y-(y+1)/2)*x;
}else{
sm1+=(y/2)*x;
sm2+=(y-(y/2))*x;
}
if(y%2==1){
hod = (hod?0: 1);
}
}
cout << sm1 << " " << sm2 << endl;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
ll t; cin >> t;
// cout << dp[3][2] << endl;
// for (ll i = 1;)
while (t--){
bruh();
}
}
