Idea: BledDest
Tutorial
Tutorial is loading...
Solution
def f(x):
x += 1
while(x % 10 == 0):
x //= 10
return x
a = set()
n = int(input())
while(not(n in a)):
a.add(n)
n = f(n)
print(len(a))
Idea: BledDest
Tutorial
Tutorial is loading...
Solution
#include<bits/stdc++.h>
using namespace std;
int f[10];
string s;
int main()
{
int n;
cin >> n;
cin >> s;
for(int i = 1; i <= 9; i++)
cin >> f[i];
vector<int> diff;
for(int i = 0; i < n; i++)
diff.push_back(f[s[i] - '0'] - (s[i] - '0'));
for(int i = 0; i < n; i++)
if(diff[i] > 0)
{
while(i < n && diff[i] >= 0)
{
s[i] = char(f[s[i] - '0'] + '0');
i++;
}
break;
}
cout << s << endl;
}
1157C1 - Increasing Subsequence (easy version)
Idea: MikeMirzayanov
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 n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; ++i) {
cin >> a[i];
}
string res;
int l = 0, r = n - 1;
int lst = 0;
while (l <= r) {
vector<pair<int, char>> cur;
if (lst < a[l]) cur.push_back(make_pair(a[l], 'L'));
if (lst < a[r]) cur.push_back(make_pair(a[r], 'R'));
sort(cur.begin(), cur.end());
if (int(cur.size()) == 2) {
cur.pop_back();
}
if (int(cur.size()) == 1) {
if (cur[0].second == 'L') {
res += 'L';
lst = a[l];
++l;
} else {
res += 'R';
lst = a[r];
--r;
}
} else {
break;
}
}
cout << res.size() << endl << res << endl;
return 0;
}
1157C2 - Increasing Subsequence (hard version)
Idea: MikeMirzayanov
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 n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; ++i) {
cin >> a[i];
}
string res;
int l = 0, r = n - 1;
int lst = 0;
while (l <= r) {
vector<pair<int, char>> cur;
if (lst < a[l]) cur.push_back(make_pair(a[l], 'L'));
if (lst < a[r]) cur.push_back(make_pair(a[r], 'R'));
sort(cur.begin(), cur.end());
if (int(cur.size()) == 2 && cur[0].first != cur[1].first) {
cur.pop_back();
}
if (int(cur.size()) == 1) {
if (cur[0].second == 'L') {
res += 'L';
lst = a[l];
++l;
} else {
res += 'R';
lst = a[r];
--r;
}
} else if (int(cur.size()) == 2) {
int cl = 1, cr = 1;
while (l + cl <= r && a[l + cl] > a[l + cl - 1]) ++cl;
while (r - cr >= l && a[r - cr] > a[r - cr + 1]) ++cr;
if (cl > cr) {
res += string(cl, 'L');
} else {
res += string(cr, 'R');
}
break;
} else {
break;
}
}
cout << res.size() << endl << res << endl;
return 0;
}
1157D - N Problems During K Days
Idea: MikeMirzayanov
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 n, k;
cin >> n >> k;
if (n < k * 1ll * (k + 1) / 2) {
cout << "NO" << endl;
return 0;
}
int nn = n - k * (k + 1) / 2;
vector<int> a(k);
for (int i = 0; i < k; ++i) {
a[i] = i + 1 + (nn / k) + (i >= k - nn % k);
}
if (nn != k - 1) {
cout << "YES" << endl;
for (int i = 0; i < k; ++i) cout << a[i] << " ";
cout << endl;
} else {
if (k > 3) {
--a[1];
++a[k - 1];
}
if (k == 2 || k == 3) {
cout << "NO" << endl;
} else {
cout << "YES" << endl;
for (int i = 0; i < k; ++i) cout << a[i] << " ";
cout << 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 n;
cin >> n;
vector<int> a(n);
multiset<int> b;
for (int i = 0; i < n; ++i) {
cin >> a[i];
}
for (int i = 0; i < n; ++i) {
int x;
cin >> x;
b.insert(x);
}
for (int i = 0; i < n; ++i) {
auto it = b.lower_bound(n - a[i]);
if (it == b.end()) it = b.begin();
cout << (a[i] + *it) % n << " ";
b.erase(it);
}
cout << endl;
return 0;
}
1157F - Maximum Balanced Circle
Idea: MikeMirzayanov
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 n;
cin >> n;
vector<int> a(n);
vector<int> cnt(200 * 1000 + 1);
for (int i = 0; i < n; ++i) {
cin >> a[i];
++cnt[a[i]];
}
sort(a.begin(), a.end());
a.resize(unique(a.begin(), a.end()) - a.begin());
int l = 0, r = 0;
int ans = cnt[a[0]];
for (int i = 0; i < int(a.size()); ++i) {
int j = i + 1;
int sum = cnt[a[i]];
while (a[j] - a[j - 1] == 1 && cnt[a[j]] > 1) {
sum += cnt[a[j]];
++j;
}
int cr = j - 1;
if (j < n && a[j] - a[j - 1] == 1) {
sum += cnt[a[j]];
cr = j;
}
if (ans < sum) {
ans = sum;
l = i;
r = cr;
}
i = j - 1;
}
cout << ans << endl;
for (int c = 0; c < cnt[a[l]]; ++c) cout << a[l] << " ";
for (int i = l + 1; i < r; ++i) {
for (int c = 0; c < cnt[a[i]] - 1; ++c) cout << a[i] << " ";
}
for (int c = 0; l != r && c < cnt[a[r]]; ++c) cout << a[r] << " ";
for (int i = r - 1; i > l; --i) cout << a[i] << " ";
cout << endl;
return 0;
}
1157G - Inverse of Rows and Columns
Idea: vovuh
This is the comment about the quadratic solution. Thank you so much for mentioning this fact, STommydx!
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
int n, m;
void invRow(vector<vector<int>> &a, int idx) {
for (int pos = 0; pos < m; ++pos) {
a[idx][pos] ^= 1;
}
}
void invCol(vector<vector<int>> &a, int idx) {
for (int pos = 0; pos < n; ++pos) {
a[pos][idx] ^= 1;
}
}
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
#endif
cin >> n >> m;
vector<vector<int>> a(n, vector<int>(m));
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
cin >> a[i][j];
}
}
for (int cnt0 = 0; cnt0 <= m; ++cnt0) {
string r(n, '0');
string c(m, '0');
vector<vector<int>> b = a;
for (int j = 0; j < m; ++j) {
if ((j < cnt0 && b[0][j] == 1) || (j >= cnt0 && b[0][j] == 0)) {
invCol(b, j);
c[j] = '1';
}
}
bool ok = true;
if (cnt0 < m) {
for (int i = 1; i < n; ++i) {
int sum = accumulate(b[i].begin(), b[i].end(), 0);
if (sum != 0 && sum != m) {
ok = false;
} else if (sum == 0) {
invRow(b, i);
r[i] = '1';
}
}
} else {
int idx = -1;
for (int i = 1; i < n; ++i) {
int sum = accumulate(b[i].begin(), b[i].end(), 0);
if (sum != 0 && sum != m) {
if (idx != -1) ok = false;
else idx = i;
}
}
if (idx == -1) {
for (int i = 1; i < n; ++i) {
int sum = accumulate(b[i].begin(), b[i].end(), 0);
if (sum == 0) {
invRow(b, i);
r[i] = '1';
}
}
} else {
for (int i = 1; i < idx; ++i) {
int sum = accumulate(b[i].begin(), b[i].end(), 0);
if (sum == m) {
invRow(b, i);
r[i] = '1';
}
}
if (b[idx][0] == 1) {
invRow(b, idx);
r[idx] = '1';
}
for (int j = 1; j < m; ++j) {
if (b[idx][j] < b[idx][j - 1]) {
ok = false;
}
}
for (int i = idx + 1; i < n; ++i) {
int sum = accumulate(b[i].begin(), b[i].end(), 0);
if (sum == 0) {
invRow(b, i);
r[i] = '1';
}
}
}
}
if (ok) {
cout << "YES" << endl << r << endl << c << endl;
return 0;
}
}
cout << "NO" << endl;
return 0;
}