Codeforces Round #787 (Div. 3) Editorial
Difference between en1 and en2, changed 1 character(s)
[problem:1690A]↵

Idea: [user:MikeMirzayanov,2022-06-08]↵

<spoiler summary="Tutorial">↵
[tutorial:1690A]↵
</spoiler>↵

<spoiler summary="Solution">↵
~~~~~↵
#include <bits/stdc++.h>↵
 ↵
using namespace std;↵
 ↵
#define forn(i, n) for (int i = 0; i < int(n); i++)↵
#define sz(v) (int)v.size()↵
#define all(v) v.begin(),v.end()↵
#define eb emplace_back↵
 ↵
 ↵
 ↵
void solve() {↵
    int n; ↵
    cin >> n;↵
    for (int a = 3; a < n; a++) {↵
        int c = (n - a) / 2;↵
        int b = n - a - c;↵
        if (c > 1 && b+1 < a) {↵
            c--;↵
            b++;↵
        }↵
        if (a > b && b > c) {↵
            cout << b << ' ' << a << ' ' << c << endl;↵
            return;↵
        }↵
    }↵
}↵
 ↵
int main() {↵
    int t;↵
    cin >> t;↵
 ↵
    forn(tt, t) {↵
        solve();↵
    }↵
}↵
~~~~~↵
</spoiler>↵

[problem:1690B]↵

Idea: [user:MikeMirzayanov,2022-06-08]↵

<spoiler summary="Tutorial">↵
[tutorial:1690B]↵
</spoiler>↵

<spoiler summary="Solution">↵
~~~~~↵
#include<bits/stdc++.h>↵
 ↵
#define forn(i, n) for (int i = 0; i < int(n); i++)↵
 ↵
using namespace std;↵
const int inf = 1e9 + 7;↵
 ↵
bool equals(vector<int>&a, vector<int>&b, int n){↵
    int dif = inf;↵
    forn(i, n){↵
        if(b[i] != 0) dif = min(dif, a[i] - b[i]);↵
    }↵
    if(dif < 0) return false; ↵
    if(dif == inf) return true;↵
    forn(i, n){↵
        if(a[i] - b[i] > dif) return false;↵
        if(b[i] != 0 && a[i] - b[i] < dif) return false;↵
    }↵
    return true;↵
}↵
 ↵
void solve(){↵
    int n;↵
    cin >> n;↵
    vector<int>a(n), b(n);↵
    forn(i, n) cin >> a[i];↵
    forn(i, n) cin >> b[i];↵
    cout << (equals(a, b, n) ? "YES\n" : "NO\n");↵
 ↵
}↵
 ↵
int main(){↵
    int t;↵
    cin >> t;↵
    while(t--){↵
        solve();↵
    }↵
}↵

~~~~~↵
</spoiler>↵

[problem:1690C]↵

Idea: [user:MikeMirzayanov,2022-06-08]↵

<spoiler summary="Tutorial">↵
[tutorial:1690C]↵
</spoiler>↵

<spoiler summary="Solution">↵
~~~~~↵
#include <bits/stdc++.h>↵
 ↵
using namespace std;↵
 ↵
typedef long long ll;↵
 ↵
#define forn(i, n) for (int i = 0; i < int(n); i++)↵
 ↵
 ↵
void solve() {↵
    int n;↵
    cin >> n;↵
    int s[n];↵
    int f[n];↵
    for (int i = 0; i < n; ++i) {↵
        cin >> s[i];↵
    }↵
 ↵
    for (int i = 0; i < n; ++i) {↵
        cin >> f[i];↵
    }↵
    int curTime = 0;↵
    int d[n];↵
    for (int i = 0; i < n; ++i) {↵
        curTime = max(curTime, s[i]);↵
        d[i] = f[i] - curTime;↵
        curTime = f[i];↵
    }↵
    for (auto now: d) {↵
        cout << now << " ";↵
    }↵
    cout << '\n';↵
}↵
int main() {↵
    int tests;↵
    cin >> tests;↵
    forn(tt, tests) {↵
        solve();↵
    }↵
}↵
~~~~~↵
</spoiler>↵

[problem:1690D]↵

Idea: [user:MikeMirzayanov,2022-06-08]↵

<spoiler summary="Tutorial">↵
[tutorial:1690D]↵
</spoiler>↵

<spoiler summary="Solution">↵
~~~~~↵
#include <bits/stdc++.h>↵
 ↵
using namespace std;↵
 ↵
#define forn(i, n) for (int i = 0; i < int(n); i++)↵
 ↵
int main() {↵
    int t;↵
    cin >> t;↵
    forn(tt, t) {↵
        int n, k;↵
        cin >> n >> k;↵
        string s;↵
        cin >> s;↵
        vector<int> w(n + 1);↵
        for (int i = 1; i <= n; i++)↵
            w[i] = w[i - 1] + int(s[i - 1] == 'W');↵
        int result = INT_MAX;↵
        for (int i = k; i <= n; i++)↵
            result = min(result, w[i] - w[i - k]);↵
        cout << result << endl;↵
    }↵
}↵
~~~~~↵
</spoiler>↵

[problem:1690E]↵

Idea: [user:Vladosiya,2022-06-08], [user:Aris,2022-06-08]↵

<spoiler summary="Tutorial">↵
[tutorial:1690E]↵
</spoiler>↵

<spoiler summary="Solution">↵
~~~~~↵
#include<bits/stdc++.h>↵
#define len(s) (int)s.size()↵
using namespace std;↵
using ll = long long;↵
 ↵
void solve(){↵
    int n, k;↵
    cin >> n >> k;↵
    vector<ll>a(n);↵
    ll sum = 0;↵
    for(int i = 0; i < n; i++) {↵
        cin >> a[i];↵
        sum += a[i] / k;↵
        a[i] = a[i] % k;↵
    }↵
    sort(a.begin(), a.end(), [] (int x, int y){↵
        return x > y;↵
    });↵
 ↵
    for(int i = 0, j = n - 1; i < j; i++, j--){↵
        while(a[i] + a[j] < k && i < j) j--;↵
        if(i == j) break;↵
        sum++;↵
    }↵
    cout << sum << endl;↵
}↵
 ↵
int main(){↵
    int t;↵
    cin >> t;↵
    while(t--){↵
        solve();↵
    }↵
    return 0;↵
}↵
~~~~~↵
</spoiler>↵

[problem:1690F]↵

Idea: [user:MikeMirzayanov,2022-06-08]↵

<spoiler summary="Tutorial">↵
[tutorial:1690F]↵
</spoiler>↵

<spoiler summary="Solution">↵
~~~~~↵
def gcd(a, b):↵
    if b == 0:↵
        return a;↵
    return gcd(b, a % b)↵
    ↵
    ↵
def shift(s):↵
    for i in range(1, len(s) + 1):↵
        if s == s[i:] + s[:i]:↵
            return i↵
    ↵
 ↵
def solve():↵
    n = int(input())↵
    s = input()↵
    p = [int(x)-1 for x in input().split()]↵
    used = [False] * n↵
    ans = 1↵
    i = 0↵
    while i < n:↵
        ss = ''↵
        while not used[i]:↵
            ss += s[i]↵
            used[i] = True↵
            i = p[i];↵
        i += 1↵
        if len(ss) == 0:↵
            continue↵
        ln = shift(ss)↵
        ans = ans * ln // gcd(ans, ln)↵
    print(ans)↵
    ↵
 ↵
t = int(input())↵
for _ in range(t):↵
    solve()↵
~~~~~↵
</spoiler>↵

[problem:1690G]↵

Idea: [user:Aris,2022-06-08]↵

<spoiler summary="Tutorial">↵
[tutorial:1690G]↵
</spoiler>↵

<spoiler summary="Solution">↵
~~~~~↵
#include<bits/stdc++.h>↵
 ↵
using namespace std;↵
 ↵
int main() {↵
    ios_base::sync_with_stdio(0);↵
    cin.tie(0);↵
    cout.tie(0);↵
    int t;↵
    cin >> t;↵
    while (t--) {↵
        int n, m;↵
        cin >> n >> m;↵
        vector<int> a(n);↵
        set<int> tmp;↵
        for (int i = 0; i < n; i++) {↵
            cin >> a[i];↵
            if (tmp.empty() || a[i] < a[*tmp.rbegin()]) {↵
                tmp.insert(i);↵
            }↵
        }↵
        for (int i = 0; i < m; i++) {↵
            int j, d;↵
            cin >> j >> d;↵
            j--;↵
            a[j] -= d;↵
            auto it = tmp.upper_bound(j);↵
            if (it != tmp.begin()) {↵
                it = prev(it);↵
                if (*it == j || a[*it] > a[j]) {↵
                    tmp.insert(j);↵
                }↵
            } else {↵
                tmp.insert(j);↵
            }↵
            while (1) {↵
                it = tmp.upper_bound(j);↵
                if (it != tmp.end() && a[*it] >= a[j]) {↵
                    tmp.erase(it);↵
                } else {↵
                    break;↵
                }↵
            }↵
            cout << (int) tmp.size() << " ";↵
        }↵
        cout << '\n';↵
    }↵
}↵
~~~~~↵
</spoiler>↵

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
ru3 Russian Aris 2022-06-08 20:39:01 17
en3 English Aris 2022-06-08 20:38:05 2
en2 English Aris 2022-06-08 15:59:16 1 (published)
ru2 Russian Aris 2022-06-08 15:58:37 1 (опубликовано)
ru1 Russian Aris 2022-06-08 15:58:21 6523 Первая редакция перевода на Русский (сохранено в черновиках)
en1 English Aris 2022-06-08 15:53:19 6544 Initial revision (saved to drafts)