Всем привет! Сегодня я бы хотел разобрать Codeforces Round 1047 (Div. 3). Поидее разбор вышел еще давно, просто я хотел дождаться именно окончание хакерской фазы. Всем спасибо за внимание. GLHF:)
Идея решения: Нам предлагают идти от конца операции. Давайте определим обратные действия для каждой операции:
- Если x четное, при обратной операции мы умножаем на 2.
- Если x нечетное, проверяем, можно ли получить x как (x-1)/3, и если это число нечетное, делим на него.
Алгоритм:
- Читаем число x.
- Если оно четное — умножаем на 2.
- Если нечетное — проверяем условие (x-1)/3 и делим, если подходит.
- Выводим результат.
#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()
using namespace std;
const ll MOD = 1e9+7;
void bruh(){
ll n,k; cin >> n >> k;
for (ll i = 0;i<n;i++){
if((k-1)%3==0 && !((k-1)/3==0) && k%2==0){
k--;
k/=3;
}else{
k*=2;
// k/=3;
}
}
cout << k << endl;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
ll t; cin >> t;
while (t--){
bruh();
}
}
Идея решения: Пусть нам дан массив, и мы хотим гарантировать gcd(array) = n, где массив — перестановка.
Замечаем: любое число x < n можно превратить в n, добавив n-x.
Алгоритм:
- Для каждого элемента a[i]:
- Если a[i] = n, добавляем n.
- Иначе добавляем n-a[i].
- Новый массив — ответ.
#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()
using namespace std;
const ll MOD = 1e9+7;
void bruh(){
ll n; cin >> n;
vector<ll> a(n);
for (ll &x: a){
cin >> x;
}
ll r = n;
if(n==2){
if(a[0]==1 && a[1]==2){
cout << "2 1" << endl;}else{
cout << "1 2" << endl;
}
}else{
vector<ll> res(n);
for (ll i = 0;i<n;i++){
if(a[i]==n){
res[i] = n;
}else{
res[i] = n-a[i];
}
}
for (ll x: res){
cout << x << " ";
}cout << endl;
}}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
ll t; cin >> t;
while (t--){
bruh();
}
}
Идея решения: Рассмотрим ситуации, когда решение невозможно:
- a четное, а b нечетное.
- Даже если разделить b на его делитель, b останется нечетным, а a четное — сумма a+b никогда не станет четной.
- a нечетное, b четное, но (b/2) нечетное.
- Любой делитель b, умножая a, даст четное число, но при этом сумма не получится четной.
Иначе:
- Если оба числа нечетные — берем делитель d = b, b/b = 1.
- Иначе — берем d = b/2, чтобы получить максимальную четную сумму.
#include <iostream>
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define f first
#define s second
#define all(x) x.rbegin(),x.rend()
using namespace std;
const ll MOD = 1e9+7;
void bruh(){
ll a,b; cin >> a >> b;
if(a%2==0 && b%2==1 || a%2==1 && b%2==0 && (b/2)%2!=0){
cout << -1 << endl;
}else{
if(a%2==1 && b%2==1){
cout << a*b+1 << endl;
}else{
cout << a*(b/2)+2 << endl;
}}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
ll t; cin >> t;
while (t--){
bruh();
}
}
Идея решения: Проверим, когда ответ невозможен:
Если f(x) ≥ x и f(x) % x != 0, корректного расположения нет.
Пример: Массив [2,2,3,3,3,2]
f(2) = 3, f(3) = 3
Можно попытаться составить массив [1,1,2,2,2,3], но последняя тройка не совпадает с a[n] = 2 → решения нет
Если таких ситуаций нет, решение всегда существует:
Группируем одинаковые числа.
Ставим их на позиции, соответствующие их количеству.
Если f(x) > x, начинаем с стартового числа st = 1, кладем x раз, затем обновляем st и продолжаем. Для полной ясности просмотрите мой код.
#include <bits/stdc++.h>
using namespace std;
#define f first
#define s second
#define pb push_back
using ll = long long;
void bruh(){
ll n;
if(!(cin >> n)) return;
vector<ll> a(n);
for (ll i = 0; i < n; ++i) cin >> a[i];
map<ll,ll> mp;
for (ll x : a) mp[x]++;
map<ll,ll> total;
for (auto &p : mp) {
ll x = p.f;
ll cnt = p.s;
if (x <= 0 || cnt % x != 0) {
cout << -1 << '\n';
return;
}
total[x] = cnt / x;
}
vector<ll> ans(n);
map<ll,ll> rem;
map<ll,ll> group;
vector<pair<ll,ll>> rek;
for (ll i = 0;i<n;i++){
rek.pb({a[i],i});
}
sort(rek.begin(),rek.end());
ll idx = 1;
for (ll i = 0; i < n; ++i){
ll x = rek[i].f;
ll y = rek[i].s;
if (rem[x] == 0){
if (group[x] >=total[x]) {
cout << -1 << '\n';
return;
}
rem[x] = x;
group[x]++;
}
ans[y] = idx;
rem[x]--;
if (rem[x] == 0) idx++;
}
for (ll v : ans) cout << v << ' ';
cout << '\n';
// cout << n << '\n';
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
ll t; cin >> t;
while (t--) bruh();
return 0;
}
Идея решения: Наблюдение: после трёх операций массив стабилизируется.
Пример:
[0,2,1,2,3,8] -> [0,4,1,4,3,4] -> [0,2,1,2,2,2] -> [0,3,1,3,3,3] -> [0,2,1,2,2,2]
- После третьей операции массив больше не меняется.
- Достаточно посчитать суммы после 1-й, 2-й и 3-й операций.
Вывод:
- Если k = 1 — берем сумму после первой операции.
- Если k четное — берем сумму после второй операции.
- Иначе — берем сумму после третьей операции.
#include <bits/stdc++.h>
using namespace std;
#define f first
#define s second
#define pb push_back
using ll = long long;
void bruh() {
ll n, k;
cin >> n >> k;
vector<ll> a(n);
for (ll &x : a) cin >> x;
vector<ll> freq(n + 2, 0);
for (ll x : a) if (x <= n) freq[x]++;
ll mex = 0;
while (freq[mex]) mex++;
vector<ll> b(n);
for (ll i = 0; i < n; i++) {
if (a[i] >= mex || freq[a[i]] > 1) b[i] = mex;
else b[i] = a[i];
}
ll sum1 = 0;
for (ll x : b) sum1 += x;
if (k == 1) {
cout << sum1 << "\n";
return;
}
vector<ll> freq2(n + 2, 0);
for (ll x : b) if (x <= n) freq2[x]++;
ll mex2 = 0;
while (freq2[mex2]) mex2++;
ll sum2 = 0;
map<ll,ll> mpp;
for (ll i = 0; i < n; i++) {
if (b[i] >= mex2 || freq2[b[i]] > 1){ sum2 += mex2;
b[i] = mex2;
mpp[b[i]]++;
}
else{ sum2 += b[i];
b[i] = b[i];
mpp[b[i]]++;
}
}
ll mex3 = 0;
while (mpp[mex3]) mex3++;
ll sm3 = 0;
for (ll i = 0;i<n;i++){
if(b[i]>=mex3 || mpp[b[i]]>1){
sm3+=mex3;
}else{
sm3+=b[i];
}
}
// cout << sm3 << endl;
if(k==1){
cout << sum1 << endl;
}else{
if(k%2==1){
cout << sm3 << endl;
}else{
cout << sum2 << endl;
}}
// cout << (k % 2 == 0 ? sum2 : sum1) << "\n";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
ll t;
cin >> t;
while (t--) bruh();
return 0;
}
