I'm so thankful to all testers, especially to Gassa and Rox for their invaluable help!
1409A - Yet Another Two Integers Problem
Idea: vovuh
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
#endif
int t;
cin >> t;
while (t--) {
int a, b;
cin >> a >> b;
cout << (abs(a - b) + 9) / 10 << endl;
}
return 0;
}
Idea: vovuh
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
#endif
int t;
cin >> t;
while (t--) {
int a, b, x, y, n;
cin >> a >> b >> x >> y >> n;
long long ans = 1e18;
for (int i = 0; i < 2; ++i) {
int da = min(n, a - x);
int db = min(n - da, b - y);
ans = min(ans, (a - da) * 1ll * (b - db));
swap(a, b);
swap(x, y);
}
cout << ans << endl;
}
return 0;
}
1409C - Yet Another Array Restoration
Idea: vovuh
Tutorial
Tutorial is loading...
Solution (Gassa)
// Author: Ivan Kazmenko ([email protected])
module solution;
import std.algorithm;
import std.conv;
import std.range;
import std.stdio;
import std.string;
void main ()
{
auto tests = readln.strip.to !(int);
foreach (test; 0..tests)
{
int n, x, y;
readf !(" %s %s %s") (n, x, y);
auto answer = int.max.repeat (n).array;
foreach (start; 1..51)
{
foreach (d; 1..51)
{
auto a = iota (start, start + d * n, d).array;
if (a.canFind (x) && a.canFind (y))
{
if (answer.back > a.back)
{
answer = a;
}
}
}
}
writefln !("%(%s %)") (answer);
}
}
Solution (vovuh)
#include <bits/stdc++.h>
using namespace std;
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
#endif
int t;
cin >> t;
while (t--) {
int n, x, y;
cin >> n >> x >> y;
vector<int> ans;
for (int d = 1; d <= y - x; ++d) {
if ((y - x) % d != 0) continue;
vector<int> res;
bool foundx = false;
int cur = y;
int need = n;
while (cur >= 1 && need > 0) {
res.push_back(cur);
foundx |= cur == x;
--need;
cur -= d;
}
cur = y;
while (need > 0) {
cur += d;
res.push_back(cur);
--need;
}
sort(res.begin(), res.end());
if (need == 0 && foundx) {
if (ans.empty() || ans.back() > res.back()) {
ans = res;
}
}
}
assert(!ans.empty());
for (auto it : ans) cout << it << " ";
cout << endl;
}
return 0;
}
Solution (Rox)
#include <bits/stdc++.h>
using namespace std;
int main() {
int tcs;
cin >> tcs;
while (tcs--) {
int n, x, y;
cin >> n >> x >> y;
int diff = y - x;
for (int delta = 1; delta <= diff; ++delta) {
if (diff % delta) continue;
if (diff / delta + 1 > n) continue;
int k = min((y - 1) / delta, n - 1);
int a0 = y - k * delta;
for (int i = 0; i < n; ++i) {
cout << (a0 + i * delta) << ' ';
}
cout << endl;
break;
}
}
}
1409D - Decrease the Sum of Digits
Idea: MikeMirzayanov
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
int sum(long long n) {
int res = 0;
while (n > 0) {
res += n % 10;
n /= 10;
}
return res;
}
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
#endif
int t;
cin >> t;
while (t--) {
long long n;
int s;
cin >> n >> s;
long long ans = 0;
if (sum(n) <= s) {
cout << 0 << endl;
continue;
}
long long pw = 1;
for (int i = 0; i < 18; ++i) {
int digit = (n / pw) % 10;
long long add = pw * ((10 - digit) % 10);
n += add;
ans += add;
if (sum(n) <= s) {
break;
}
pw *= 10;
}
cout << ans << endl;
}
return 0;
}
Idea: vovuh
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
#endif
int t;
cin >> t;
while (t--) {
int n, k;
cin >> n >> k;
vector<int> x(n), y(n);
for (auto &it : x) cin >> it;
for (auto &it : y) cin >> it;
sort(x.begin(), x.end());
int j = n - 1;
vector<int> l(n), r(n);
for (int i = n - 1; i >= 0; --i) {
while (x[j] - x[i] > k) --j;
r[i] = j - i + 1;
if (i + 1 < n) r[i] = max(r[i], r[i + 1]);
}
j = 0;
for (int i = 0; i < n; ++i) {
while (x[i] - x[j] > k) ++j;
l[i] = i - j + 1;
if (i > 0) l[i] = max(l[i], l[i - 1]);
}
int ans = 1;
for (int i = 0; i < n - 1; ++i) {
ans = max(ans, r[i + 1] + l[i]);
}
cout << ans << endl;
}
return 0;
}
1409F - Subsequences of Length Two
Idea: vovuh
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9;
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
#endif
int n, k;
string s, t;
cin >> n >> k >> s >> t;
vector<vector<vector<int>>> dp(n + 1, vector<vector<int>>(n + 1, vector<int>(n + 1, -INF)));
dp[0][0][0] = 0;
for (int i = 0; i < n; ++i) {
for (int ck = 0; ck <= k; ++ck) {
for (int cnt0 = 0; cnt0 <= n; ++cnt0) {
if (dp[i][ck][cnt0] == -INF) continue;
int e0 = s[i] == t[0];
int e1 = s[i] == t[1];
int e01 = t[0] == t[1];
dp[i + 1][ck][cnt0 + e0] = max(dp[i + 1][ck][cnt0 + e0], dp[i][ck][cnt0] + (e1 ? cnt0 : 0));
if (ck < k) {
dp[i + 1][ck + 1][cnt0 + 1] = max(dp[i + 1][ck + 1][cnt0 + 1], dp[i][ck][cnt0] + (e01 ? cnt0 : 0));
dp[i + 1][ck + 1][cnt0 + e01] = max(dp[i + 1][ck + 1][cnt0 + e01], dp[i][ck][cnt0] + cnt0);
}
}
}
}
int ans = 0;
for (int ck = 0; ck <= k; ++ck) {
for (int cnt0 = 0; cnt0 <= n; ++cnt0) {
ans = max(ans, dp[n][ck][cnt0]);
}
}
cout << ans << endl;
return 0;
}
Solution (Gassa, greedy, O(n^4))
// Author: Ivan Kazmenko ([email protected])
module solution;
import std.algorithm;
import std.conv;
import std.range;
import std.stdio;
import std.string;
void main ()
{
int n, k;
while (readf !(" %s %s") (n, k) > 0)
{
readln;
auto s0 = readln.strip;
auto t = readln.strip;
auto s = s0.dup;
int res = 0;
foreach (b0; 0..k + 1)
{
auto e0 = k - b0;
loop_x0:
foreach (x0; 0..b0 + 1)
{
loop_y0:
foreach (y0; 0..e0 + 1)
{
int b = b0;
int e = e0;
int x = x0;
int y = y0;
s[] = s0[];
for (int i = 0; i < n && b; i++)
{
if (s[i] == t[0])
{
}
else if (s[i] != t[1])
{
s[i] = t[0];
b -= 1;
}
else if (x > 0)
{
s[i] = t[0];
x -= 1;
b -= 1;
}
}
for (int j = n - 1; j >= 0 && e; j--)
{
if (s[j] == t[1])
{
}
else if (s[j] != t[0])
{
s[j] = t[1];
e -= 1;
}
else if (y > 0)
{
s[j] = t[1];
y -= 1;
e -= 1;
}
}
int cur = 0;
int add = 0;
for (int i = 0; i < n; i++)
{
if (s[i] == t[1])
{
cur += add;
}
if (s[i] == t[0])
{
add += 1;
}
}
res = max (res, cur);
if (x > 0)
{
break loop_x0;
}
if (y > 0)
{
break loop_y0;
}
}
}
}
writeln (res);
}
}