Идея: MikeMirzayanov
Разбор
Tutorial is loading...
Решение
#include <iostream>
using namespace std;
int main() {
int q;
cin >> q;
for (int qr = 0; qr < q; ++qr) {
int a, b, n, s;
cin >> a >> b >> n >> s;
if (s % n <= b && 1ll * a * n + b >= s) {
cout << "YES\n";
}
else {
cout << "NO\n";
}
}
}
1256B - Минимизация перестановки
Идея: vovuh
Разбор
Tutorial is loading...
Решение
#include <bits/stdc++.h>
using namespace std;
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
#endif
int q;
cin >> q;
for (int i = 0; i < q; ++i) {
int n;
cin >> n;
vector<int> a(n);
for (int j = 0; j < n; ++j) {
cin >> a[j];
--a[j];
}
int pos = 0;
while (pos < n) {
int nxt = min_element(a.begin() + pos, a.end()) - a.begin();
int el = a[nxt];
a.erase(a.begin() + nxt);
a.insert(a.begin() + pos, el);
if (pos == nxt) pos = nxt + 1;
else pos = nxt;
}
for (auto it : a) cout << it + 1 << " ";
cout << endl;
}
return 0;
}
Идея: MikeMirzayanov
Разбор
Tutorial is loading...
Решение
#include <bits/stdc++.h>
using namespace std;
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
#endif
int n, m, d;
cin >> n >> m >> d;
vector<int> c(m);
for (int i = 0; i < m; ++i) {
cin >> c[i];
}
vector<int> ans(n + 2);
for (int i = m - 1, pos = n; i >= 0; --i) {
for (int len = 0; len < c[i]; ++len) {
ans[pos - len] = i + 1;
}
pos -= c[i];
}
int now = 0;
while (true) {
while (now + 1 < n + 1 && ans[now + 1] > 0) ++now;
if (now + d >= n + 1) break;
if (ans[now + d] == 0) {
int lpos = -1;
for (int i = now + d; i < n + 2; ++i) {
if (ans[i] != 0) {
lpos = i;
break;
}
}
if (lpos == -1) {
cout << "NO" << endl;
return 0;
}
int rpos = -1;
for (int i = lpos; i < n + 2; ++i) {
if (ans[i] == ans[lpos]) rpos = i;
}
while (ans[now + d] == 0) {
swap(ans[lpos - 1], ans[rpos]);
--lpos, --rpos;
}
}
now += d;
}
cout << "YES" << endl;
for (int i = 1; i <= n; ++i) {
cout << ans[i] << " ";
}
cout << endl;
return 0;
}
1256D - Минимизация бинарной строки
Идея: MikeMirzayanov
Разбор
Tutorial is loading...
Решение
#include <bits/stdc++.h>
using namespace std;
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
#endif
int q;
cin >> q;
while (q--) {
int n;
long long k;
string s;
cin >> n >> k >> s;
string res;
int cnt = 0;
bool printed = false;
for (int i = 0; i < n; ++i) {
if (s[i] == '0') {
if (cnt <= k) {
res += '0';
k -= cnt;
} else {
res += string(cnt - k, '1');
res += '0';
res += string(k, '1');
res += s.substr(i + 1);
cout << res << endl;
printed = true;
break;
}
} else {
++cnt;
}
}
if (!printed) {
res += string(cnt, '1');
cout << res << endl;
}
}
return 0;
}
1256E - Очередное разделение на команды
Идея: MikeMirzayanov
Разбор
Tutorial is loading...
Решение
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pt;
#define x first
#define y second
#define mp make_pair
const int N = 200043;
const int INF = int(1e9) + 43;
int n;
int dp[N];
int p[N];
pt a[N];
int t[N];
int main() {
scanf("%d", &n);
for(int i = 0; i < n; i++)
{
a[i].y = i;
scanf("%d", &a[i].x);
}
sort(a, a + n);
for(int i = 1; i <= n; i++)
{
dp[i] = INF;
p[i] = -1;
}
for(int i = 0; i < n; i++)
for(int j = 3; j <= 5 && i + j <= n; j++)
{
int diff = a[i + j - 1].x - a[i].x;
if(dp[i + j] > dp[i] + diff)
{
p[i + j] = i;
dp[i + j] = dp[i] + diff;
}
}
int cur = n;
int cnt = 0;
while(cur != 0)
{
for(int i = cur - 1; i >= p[cur]; i--)
t[a[i].y] = cnt;
cnt++;
cur = p[cur];
}
printf("%d %d\n", dp[n], cnt);
for(int i = 0; i < n; i++)
{
if(i) printf(" ");
printf("%d", t[i] + 1);
}
puts("");
return 0;
}
1256F - Приравнивание двух строк
Идея: vovuh
Разбор
Tutorial is loading...
Решение
#include <bits/stdc++.h>
using namespace std;
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
#endif
int q;
cin >> q;
for (int i = 0; i < q; ++i) {
int n;
string s, t;
cin >> n >> s >> t;
vector<int> cnts(26), cntt(26);
for (int j = 0; j < n; ++j) {
++cnts[s[j] - 'a'];
++cntt[t[j] - 'a'];
}
bool ok = true;
bool good = false;
for (int j = 0; j < 26; ++j) {
ok &= cnts[j] == cntt[j];
good |= cnts[j] > 1;
}
if (!ok) {
cout << "NO" << endl;
continue;
}
if (good) {
cout << "YES" << endl;
continue;
}
int invs = 0, invt = 0;
for (int l = 0; l < n; ++l) {
for (int r = 0; r < l; ++r) {
invs += s[l] > s[r];
invt += t[l] > t[r];
}
}
ok &= (invs & 1) == (invt & 1);
if (ok) cout << "YES" << endl;
else cout << "NO" << endl;
}
return 0;
}