Идея решения:
Пройдемся по строке c. Если c[i]=='V', добавляем b[i] в начало строки a, иначе — в конец строки a.
Алгоритм:
- Идем по строке
cот 0 до n-1. - Проверяем
c[i] == 'V'. - Вставляем
b[i]в начало или конецaв зависимости от условия.
Особенности:
- Жадный проход по строке достаточно для корректного формирования
a. - Нет необходимости в дополнительной сортировке.
#include <iostream>
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
using namespace std;
ll binpow(ll a, ll b){
ll res = 1;
while (b){
if(b&1){
res = res * a;
}
a = a * a;
b>>=1;
}
return res;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
ll t; cin >> t;
// erase(unique(spisok.begin(),spisok.end()),spisok.end())
//vector<ll> dp(spisok.size()+1,0);
//dp[0] = 1;
while (t--){
ll n; cin >> n;
string s; cin >> s;
ll k; cin >> k;
string a; cin >> a;
string b; cin >> b;
for (ll i = 0;i<k;i++){
if(b[i]=='V'){
s = a[i]+s;
}else{
s= s+a[i];
}
}
cout << s << endl;
}}
Идея решения:
Если x+y=n и y = x*10^k, то x(1+10^k) = n => x = n/(1+10^k).
Проверяем делимость n на (1+10^k) для всех k от 1 до 18.
Алгоритм:
- Перебираем k = 1..18.
- Вычисляем
x = n/(1+10^k)и проверяем, что делится нацело. - Если делится — добавляем
xв массив, иначе пропускаем.
Особенности:
- Ограничение k ≤ 18 связано с диапазоном чисел.
- Прямое вычисление x без полного перебора экономит время.
#include <iostream>
#include <vector>
#include <algorithm>
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define speed ios::sync_with_stdio(false); cin.tie();
using namespace std;
ll binpow(ll a, ll b){
ll res = 1;
while (b){
if(b&1){
res = res * a;
}
a = a*a;
b>>=1;
}
return res;
}
void bruh(){
ll n; cin >> n;
vector<ll> a;
ll base = 0;
for (ll x = 1;x<=18;x++){
ll opt = binpow(10,x)+1;
if (n%opt==0){
a.pb(n/opt);
}
}
if(a.empty()){
cout << 0 << endl;
}else{
cout << a.size() << endl;
sort(a.begin(),a.end());
for (ll x: a){
cout << x << " ";
}cout << endl;
}
}
int main() {
ll t; cin >> t;
while (t--){
bruh();
}
}
Идея решения:
Минимизируем количество сделок, используя троичную систему. Каждая позиция троичной репрезентации числа n — потенциальная сделка.
Алгоритм:
- Преобразуем n в троичный вид.
- Для каждой позиции добавляем к ответу соответствующее количество сделок.
- Если позиция = 0, корректируем bas-1 → bas, чтобы избежать отрицательных значений.
Особенности:
- Троичная репрезентация полностью задает минимальные сделки.
- Жадный выбор максимальных степеней числа 3 гарантирует минимум операций.
#include <iostream>
#include <vector>
#include <algorithm>
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define f first
#define s second
#define speed ios::sync_with_stdio(false); cin.tie(0)
using namespace std;
ll binpow(ll a, ll b){
ll res = 1;
while (b){
if(b&1){
res = res * a;
}
a = a*a;
b>>=1;
}
return res;
}
void bruh(){
ll n; cin >> n;
ll base= 0;
ll ans = 0;
ll mn = 0;
while (n){
ll cur = n%3;
if(base>0){
ll opt = binpow(3,base+1)+base*(binpow(3,base-1));
ans+=opt*cur;}else{
mn+=cur;
}
n/=3;
base++;
}
cout<<mn*3+ans<< endl;
}
int main() {
speed;
ll t; cin >> t;
while (t--){
bruh();
}
}
Идея решения:
Можно расщеплять 3^x → 3^(x-1)*3, чтобы увеличить количество сделок без превышения k.
Алгоритм:
- Определяем минимальное количество сделок с прошлого решения (троичная репрезентация).
- Если mn > k, выводим -1.
- Создаем массив cnt = троичная репрезентация числа n.
- Расщепляем числа, начиная с самой большой степени 3, пока не достигнем k.
Особенности:
- Жадный подход — расщепление с самой большой сделки.
- Контроль за числом операций гарантирует правильный ответ.
#include <iostream>
#include <vector>
#include <algorithm>
#define ll long long
#include <bits/stdc++.h>
#define pb push_back
#define f first
#define s second
#define speed ios::sync_with_stdio(false); cin.tie(0)
using namespace std;
ll MXN = 1e6+1;
vector<ll> resheto(MXN+1,0);
void bruh(){
ll n,k; cin >> n >> k;
vector<ll> dp(21,0);
vector<ll> ans;
ll cnt = 0;
ll mn = 0;
while (n>=1){
ll cur = n%3;
mn+=cur;
dp[cnt] = cur;
n/=3;
cnt++;
}
if(mn>k){
cout << -1 << endl;
return;
}
k-=mn;
// k/=2;
//cout << k<< endl;
for (ll i = 20;i>=1;i--){
if(k<=0){
break;
}
ll opt = min(dp[i],k/2);
dp[i]-=opt;
dp[i-1]+=opt*3;
k-=opt*2;
}
ll anss = 0;
for (ll i = 0;i<20;i++){
ll base1 = (i==0? 0: i-1);
// cout << dp[i] <<" ";
// if(dp[i]>0){
anss += (pow(3,i+1)+i*(pow(3,base1)))*dp[i];
}
// cout << endl;
cout << anss<< endl;
}
int main() {
speed;
ll t; cin >> t;
while (t--){
bruh();}
}
Идея решения:
Находим k-ю цифру числа в последовательности 123456789101112… используя группы 9, 90, 900, …
Алгоритм:
- Делим последовательность на группы: 1–9, 10–99, 100–999…
- Вычисляем длину группы:
len = 9*10^i*i. - Определяем группу, в которой находится k-я цифра.
- Находим конкретное число в группе через
(k-1)/len. - Считаем сумму цифр числа рекурсивно, используя разряды и префиксы.
Особенности:
- Деление на группы ускоряет поиск числа с k-й цифрой.
- DP и рекурсия позволяют быстро вычислить сумму цифр до N.
#include <iostream>
#include <vector>
#include <algorithm>
#define ull unsigned long long
#include <bits/stdc++.h>
#define pb push_back
#define f first
#define s second
#define speed ios::sync_with_stdio(false); cin.tie(0)
using namespace std;
vector<ull> g(30,0);
ull sum(ull x){
if(x <= 9){
return x*(x+1)/2;
}
ull mx = (log10(x));
ull p = ceil(pow(10,mx));
ull ost = x/p;
ull low = x%(p);
return ost*g[mx] + (ost*(ost-1)/2)*p + ost*(low+1) + sum(low);
}
void bruh(){
ull n; cin >> n;
ull base = 1;
ull b = 9;
ull ln = 1;
while (n > ln*b){
n -= ln*b;
ln++;
b *= 10;
base *= 10;
}
ull ind = (n-1)/ln;
ull num = base + ind;
ull ik = (n-1)%ln;
ull ans = 0;
// for (ll i = 0;i<)
string s = to_string(num);
for (ull i = 0;i<=ik;i++){
ans+=s[i]-'0';
}
ull cnt = sum(num-1);
cout << cnt+ans << endl;
}
int main() {
speed;
ull MXN = 18;
g[0] = 0;
g[1] = 45;
for (ull i = 2; i <= MXN; i++){
g[i] = g[i-1]*10 + (ceil(pow(10,i-1)))*45;
}
ull t; cin >> t;
while(t--){
bruh();
}
}
Идея решения:
Используем тернарный поиск для выбора префиксов массивов a и b, чтобы максимизировать сумму.
Алгоритм:
- Определяем границы: l = z-y, r = x.
- Пока r-l > 3, вычисляем m1, m2 для тернарного поиска.
- Сравниваем pA[m1]+pB[z-m1] и pA[m2]+pB[z-m2].
- Обновляем границы l или r в зависимости от сравнения.
- После выхода берем максимум среди потенциальных l ≤ k ≤ r.
Особенности:
- Унемодальная функция суммы позволяет использовать тернарный поиск.
- Префиксные суммы массивов ускоряют вычисление суммы.
~~~~~
include <bits/stdc++.h>
using namespace std;
define ll long long
int main() { ios::sync_with_stdio(false); cin.tie(nullptr); ll t; cin >> t; while (t--) { ll n, m, q; cin >> n >> m >> q; vector a(n), b(m); for (ll i = 0; i < n; i++) cin >> a[i]; for (ll i = 0; i < m; i++) cin >> b[i]; sort(a.rbegin(), a.rend()); sort(b.rbegin(), b.rend()); vector prefA(n + 1), prefB(m + 1); for (ll i = 0; i < n; i++) prefA[i + 1] = prefA[i] + a[i]; for (ll i = 0; i < m; i++) prefB[i + 1] = prefB[i] + b[i]; auto form = [&](ll k, ll z, const vector& prefA, const vector& prefB) { return prefA[k] + prefB[z — k]; }; while (q--) { ll x, y, z; cin >> x >> y >> z; ll low = max(0LL, z — y); ll high = min(x, z); if (low > high) { cout << 0 << "\n"; continue; } ll l = low, r = high; while (r — l > 3) { ll mo = l + (r — l) / 3; ll moo = r — (r — l) / 3; if (form(mo, z, prefA, prefB) < form(moo, z, prefA, prefB)) l = mo + 1; else r = moo — 1; } ll ans = 0; for (ll k = l; k <= r; k++) { ans = max(ans, form(k, z, prefA, prefB)); } cout << ans << "\n"; } } //return 0; }~~~~~
