1650A - Deletions of Two Adjacent Letters
Idea : MikeMirzayanov
Tutorial:
There will be one character left in the end, so we have to delete all the characters going before and after it. That is, delete some prefix and suffix. Since we always delete some substring of length $$$2$$$, we can only delete the prefix and suffix of even length, it means the answer is $$$YES$$$ in the case when there is an odd position in $$$s$$$ with the character $$$c$$$ and $$$NO$$$ otherwise.
Solution (ucode.vn):
#include<bits/stdc++.h>
using namespace std;
int main() {
int t; cin >> t;
while (t--) {
string s; char t; cin >> s >> t;
int ok = 0;
for (int i = 0; i < s.length(); i++) {
if (i % 2 == 0 && s[i] == t[0]) ok = 1;
}
cout << (ok ? "YES\n" : "NO\n");
}
}
Idea:Vladosiya
Tutorial:
Consider $$$f_a(r)$$$. Note that $$$⌊\frac{r}{a}⌋$$$ is maximal over the entire segment from $$$l$$$ to $$$r$$$, so if there is $$$x$$$ in which $$$f_a$$$ gives $$$a$$$ greater result, then $$$x \mod a > r \mod a$$$.
Note that numbers from $$$r − r \mod a$$$ to $$$r$$$ that have an incomplete quotient when divided by $$$a$$$ equal to $$$⌊\frac{r}{a}⌋$$$ do not fit this condition (and are guaranteed to have a value fa less than $$$f_a(r)$$$. And the number $$$x = r − r \mod a − 1$$$:
Has the maximum possible remainder $$$x \mod a = a − 1$$$; Has the maximum possible $$$⌊\frac{r}{a}⌋$$$ among numbers less than $$$r−r \mod a$$$. So there are two candidates for the answer — these are $$$r$$$ and $$$r − r \mod a − 1$$$. The second candidate is suitable only if it is at least $$$l$$$. It remains only to compare the values of $$$f_a$$$ and select the maximum.
Solution (ucode.vn)
#include<bits/stdc++.h>
using namespace std;
void solve() {
int l, r, x;
cin >> l >> r >> x;
int res = r / x + r % x;
int m = r / x * x - 1;
if (m >= l) res = max(res, m / x + m % x);
cout << res << "\n";
}
int main() {
int t; cin >> t;
while (t--)
solve();
}
}
1650C - Weight of the System of Nested Segments
Idea:ucode.vn
Tutorial:
We create the structure to stores for each point its coordinate, weight, and index in the input data. So we sort the $$$points$$$ increasing by weight. Now we sort the $$$points$$$ increasing by its coordinate.
So the $$$i^{th}$$$ segment is $$$points[i]$$$ and $$$points[2 \times n - i + 1]$$$
Print the output!!!!!!!!!!
Solution (ucode.vn):
#include<bits/stdc++.h>
using namespace std;
struct point {
int w, p, id; // int weight, position, index;
};
void solve() {
int n, m; cin >> n >> m;
vector<point> points(m);
for (int i = 0; i < m; i++) {
cin >> points[i].p >> points[i].w;
points[i].id = i + 1;
}
sort(points.begin(), points.end(), [] (point a, point b){
return a.w < b.w;
});
int s = 0;
for (int i = 0; i < m; i++) {
if (i < 2 * n) s += points[i].w;
else points.pop_back();
}
cout << s << "\n";
sort(points.begin(), points.end(), [] (point a, point b){
return a.p < b.p;
});
for (int i = 0; i < n; i++) {
cout << points[i].id << ' ' << points[2 * n - i - 1].id << "\n";
}
}
int main() {
int t; cin >> t;
while (t--) solve();
}
Idea:MikeMirzayanov
Tutorial: The first thing to notice — the answer always exists. For $$$n$$$ numbers $$$1 ⋅ 2⋅3 \cdot \dots n=n!$$$ answer choices, as well as $$$n!$$$ permutation combinations. It remains only to restore the answer from this permutation.
We will restore by performing reverse operations. On the $$$i-th$$$ $$$(i=n, n−1, …, 2, 1)$$$ operation will be selectd the first $$$i$$$ elements of the array and rotate them $$$d[i]$$$ times to the left ( elements with numbers $$$i+1$$$ and more remain in their places).
Where $$$d[i]$$$ is equal to $$$0$$$ if $$$i=1$$$, otherwise $$$d[i]=(index+1) \mod i$$$, and $$$index$$$ – is the index of the number $$$i$$$.
Thus, for each $$$i$$$ from right to left, performing a left cyclic shift operation, we move the number $$$i$$$ at index $$$i$$$. Solution (ucode.vn):
#include <bits/stdc++.h>
using namespace std;
void solve() {
int n;
cin >> n;
int a[n];
for (int i = 0; i < n; ++i) cin >> a[i];
int res[n];
for (int i = n; i > 0; --i) {
int ind = 0;
for (int j = 0; j < i; ++j) {
ind = a[j] == i ? j : ind;
}
int b[i];
for (int j = 0; j < i; ++j) {
b[(i - 1 - ind + j) % i] = a[j];
}
for (int j = 0; j < i; ++j) {
a[j] = b[j];
}
res[i - 1] = i != 1 ? (ind + 1) % i : 0;
}
for (int i = 0; i < n; ++i) cout << res[i] << ' ';
cout << '\n';
}
int main() {
int t; cin >> t;
while (t--) solve();
}
