codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

1650.md (9964B)


      1 Source: https://codeforces.com/blog/entry/100712
      2 
      3 [1650A - Deletions of Two Adjacent Letters](/contest/1650/problem/A "Codeforces Round 776 (Div. 3)")
      4 
      5 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov")
      6 
      7 **Tutorial**
      8 
      9 Tutorial is loading...
     10 
     11 **Solution**
     12 
     13 ```
     14 #include <bits/stdc++.h>
     15 
     16 using namespace std;
     17 
     18 #define forn(i, n) for (int i = 0; i < int(n); i++)
     19 
     20 int main() {
     21     int t;
     22     cin >> t;
     23     forn(tt, t) {
     24         string s, t;
     25         cin >> s >> t;
     26         bool yes = false;
     27         forn(i, s.length())
     28             if (s[i] == t[0] && i % 2 == 0)
     29                 yes = true;
     30         cout << (yes ? "YES" : "NO") << endl;
     31     }
     32 }
     33 ```
     34 
     35 [1650B - DIV + MOD](/contest/1650/problem/B "Codeforces Round 776 (Div. 3)")
     36 
     37 Idea: [Vladosiya](/profile/Vladosiya "Expert Vladosiya")
     38 
     39 **Tutorial**
     40 
     41 Tutorial is loading...
     42 
     43 **Solution**
     44 
     45 ```
     46 #include <bits/stdc++.h>
     47 
     48 //#define int long long
     49 #define mp make_pair
     50 #define x first
     51 #define y second
     52 #define all(a) (a).begin(), (a).end()
     53 #define rall(a) (a).rbegin(), (a).rend()
     54 
     55 #pragma GCC optimize("Ofast")
     56 #pragma GCC optimize("no-stack-protector")
     57 #pragma GCC optimize("unroll-loops")
     58 #pragma GCC target("sse,sse2,sse3,ssse3,popcnt,abm,mmx,tune=native")
     59 #pragma GCC optimize("fast-math")
     60 
     61 typedef long double ld;
     62 typedef long long ll;
     63 
     64 using namespace std;
     65 
     66 mt19937 rnd(143);
     67 
     68 const ll inf = 1e9;
     69 const ll M = 1e9;
     70 const ld pi = atan2(0, -1);
     71 const ld eps = 1e-4;
     72 
     73 void solve() {
     74     int l, r, x;
     75     cin >> l >> r >> x;
     76     int ans = r / x + r % x;
     77     int m = r / x * x - 1;
     78     if(m >= l)ans = max(ans, m / x + m % x);
     79     cout << ans;
     80 }
     81 
     82 bool multi = true;
     83 
     84 signed main() {
     85     //freopen("in.txt", "r", stdin);
     86     //freopen("in.txt", "w", stdout);
     87     int t = 1;
     88     if (multi) {
     89         cin >> t;
     90     }
     91     for (; t != 0; --t) {
     92         solve();
     93         cout << "\n";
     94     }
     95     return 0;
     96 }
     97 ```
     98 
     99 [1650C - Weight of the System of Nested Segments](/contest/1650/problem/C "Codeforces Round 776 (Div. 3)")
    100 
    101 Idea: [myav](/profile/myav "Pupil myav")
    102 
    103 **Tutorial**
    104 
    105 Tutorial is loading...
    106 
    107 **Solution**
    108 
    109 ```
    110 #include<bits/stdc++.h>
    111 using namespace std;
    112 using ll = long long;
    113 
    114 #define forn(i, n) for (int i = 0; i < int(n); i++)
    115 
    116 struct point{
    117     int weight, position, id;
    118 };
    119 
    120 void solve(){
    121     int n, m;
    122     cin >> n >> m;
    123     vector<point>points(m);
    124 
    125     forn(i, m) {
    126         cin >>  points[i].position >> points[i].weight;
    127         points[i].id = i + 1;
    128     }
    129 
    130     sort(points.begin(), points.end(), [] (point a, point b){
    131         return a.weight < b.weight;
    132     });
    133 
    134     int sum = 0;
    135     forn(i, m){
    136         if(i < 2 * n) sum += points[i].weight;
    137         else points.pop_back();
    138     }
    139 
    140     sort(points.begin(), points.end(), [] (point a, point b){
    141         return a.position < b.position;
    142     });
    143 
    144     cout << sum << endl;
    145     forn(i, n){
    146         cout << points[i].id << ' ' << points[2 * n - i - 1].id << endl;
    147     }
    148 }
    149 
    150 int main() {
    151     int t;
    152     cin >> t;
    153     while(t--){
    154         solve();
    155     }
    156     return 0;
    157 }
    158 ```
    159 
    160 [1650D - Twist the Permutation](/contest/1650/problem/D "Codeforces Round 776 (Div. 3)")
    161 
    162 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov")
    163 
    164 **Tutorial**
    165 
    166 Tutorial is loading...
    167 
    168 **Solution**
    169 
    170 ```
    171 #include <bits/stdc++.h>
    172 
    173 using namespace std;
    174 
    175 typedef long long ll;
    176 
    177 #define forn(i, n) for (int i = 0; i < int(n); i++)
    178 
    179 void solve() {
    180     int n;
    181     cin >> n;
    182     int a[n];
    183     for (int i = 0; i < n; ++i) {
    184         cin >> a[i];
    185     }
    186     int ans[n];
    187     for (int i = n; i > 0; --i) {
    188         int ind = 0;
    189         for (int j = 0; j < i; ++j) {
    190             ind = a[j] == i ? j : ind;
    191         }
    192         int b[i];
    193         for (int j = 0; j < i; ++j) {
    194             b[(i - 1 - ind + j) % i] = a[j];
    195         }
    196         for (int j = 0; j < i; ++j) {
    197             a[j] = b[j];
    198         }
    199         ans[i - 1] = i != 1 ? (ind + 1) % i : 0;
    200     }
    201     for (int i = 0; i < n; ++i) {
    202         cout << ans[i] << ' ';
    203     }
    204     cout << '\n';
    205 }
    206 int main() {
    207     int tests;
    208     cin >> tests;
    209     forn(tt, tests) {
    210         solve();
    211     }
    212 }
    213 ```
    214 
    215 [1650E - Rescheduling the Exam](/contest/1650/problem/E "Codeforces Round 776 (Div. 3)")
    216 
    217 Idea: [ibraevdmitriy](/profile/ibraevdmitriy "Master ibraevdmitriy")
    218 
    219 **Tutorial**
    220 
    221 Tutorial is loading...
    222 
    223 **Solution**
    224 
    225 ```
    226 #include <bits/stdc++.h>
    227 
    228 #define int long long
    229 #define mp make_pair
    230 #define x first
    231 #define y second
    232 #define all(a) (a).begin(), (a).end()
    233 #define rall(a) (a).rbegin(), (a).rend()
    234 
    235 typedef long double ld;
    236 typedef long long ll;
    237 
    238 using namespace std;
    239 
    240 mt19937 rnd(143);
    241 
    242 const ll inf = 1e9;
    243 const ll M = 998'244'353;
    244 const ld pi = atan2(0, -1);
    245 const ld eps = 1e-4;
    246 
    247 int n, d;
    248 
    249 int cnt(vector<int> &schedule){
    250     int mx = 0, mn = inf;
    251     for(int i = 1; i < n; ++i){
    252         mx = max(mx, schedule[i] - schedule[i - 1] - 1);
    253         mn = min(mn, schedule[i] - schedule[i - 1] - 1);
    254     }
    255     return min(mn, max(d - schedule.back() - 1, (mx - 1) / 2));
    256 }
    257 
    258 void solve(int test_case) {
    259     cin >> n >> d;
    260     vector<int> a(n + 1);
    261     int mn = d, min_pos = 0;
    262     for(int i = 1; i <= n; ++i){
    263         cin >> a[i];
    264         if(a[i] - a[i - 1] - 1 < mn){
    265             mn = a[i] - a[i - 1] - 1;
    266             min_pos = i;
    267         }
    268     }
    269     vector<int> schedule;
    270     for(int i = 0; i <= n; ++i){
    271         if(i != min_pos){
    272             schedule.push_back(a[i]);
    273         }
    274     }
    275     int ans = cnt(schedule);
    276     if(min_pos > 1){
    277         schedule[min_pos - 1] = a[min_pos];
    278     }
    279     ans = max(ans, cnt(schedule));
    280     cout << ans;
    281 }
    282 
    283 bool multi = true;
    284 
    285 signed main() {
    286     //freopen("in.txt", "r", stdin);
    287     //freopen("in.txt", "w", stdout);
    288     ios_base::sync_with_stdio(false);
    289     cin.tie(nullptr);
    290     cout.tie(nullptr);
    291     int t = 1;
    292     if (multi) {
    293         cin >> t;
    294     }
    295     for (int i = 1; i <= t; ++i) {
    296         solve(i);
    297         cout << "\n";
    298     }
    299     return 0;
    300 }
    301 ```
    302 
    303 [1650F - Vitaly and Advanced Useless Algorithms](/contest/1650/problem/F "Codeforces Round 776 (Div. 3)")
    304 
    305 Idea: [Aris](/profile/Aris "Candidate Master Aris")
    306 
    307 **Tutorial**
    308 
    309 Tutorial is loading...
    310 
    311 **Solution**
    312 
    313 ```
    314 #include <bits/stdc++.h>
    315 
    316 using namespace std;
    317 
    318 template<class T> bool ckmin(T &a, T b) {return a > b ? a=b, true : false;}
    319 
    320 #define forn(i, n) for (int i = 0; i < int(n); i++)
    321 #define sz(v) (int)v.size()
    322 #define all(v) v.begin(),v.end()
    323 
    324 struct option {
    325     int t, p, id;
    326     option(int _t,int _p, int _id) : t(_t), p(_p), id(_id) {
    327     }
    328 };
    329 
    330 const int INF = INT_MAX >> 1;
    331 
    332 vector<int> get_ans(vector<option> &v) {
    333     int n = sz(v);
    334     vector<vector<int>> dp(101, vector<int>(n+1, INF));
    335     dp[0][0] = 0;
    336     for (int k = 1; k <= n; k++) {
    337         auto [t,p,id] = v[k-1];
    338         dp[0][k] = 0;
    339         for (int i = 100; i > 0; i--) {
    340             int prev = max(0,i - p);
    341             dp[i][k] = dp[i][k-1];
    342             ckmin(dp[i][k], dp[prev][k-1] + t);
    343         }
    344     }
    345     vector<int> ans;
    346     int t = dp[100][n];
    347 
    348     if (t == INF) return {-1};
    349     for (int i = 100, k = n; k >= 1; k--) {
    350         if (dp[i][k] == dp[i][k-1]) {
    351             continue;
    352         }
    353         ans.emplace_back(v[k-1].id);
    354         i = max(0, i - v[k-1].p);
    355     }
    356 
    357     reverse(all(ans));
    358     ans.emplace_back(t);
    359     return ans;
    360 }
    361 
    362 void solve(bool flag=true) {
    363 
    364     int n,m; cin >> n >> m;
    365     vector<int> a(n);
    366     forn(i, n) {
    367         cin >> a[i];
    368     }
    369     for (int i = n-1; i > 0; i--) {
    370         a[i] -= a[i-1];
    371     }
    372 
    373     vector<vector<option>> v(n);
    374     forn(j, m) {
    375         int e,t,p; cin >> e >> t >> p, e--;
    376         v[e].emplace_back(t, p, j+1);
    377     }
    378     vector<int> ans;
    379     forn(i, n) {
    380         vector<int> cur = get_ans(v[i]);
    381         if (sz(cur) == 1 && cur[0] == -1) {
    382             cout << "-1\n";
    383             return;
    384         }
    385         int t = cur.back();
    386         if (t > a[i]) {
    387             cout << "-1\n";
    388             return;
    389         }
    390         cur.pop_back();
    391         if (i+1 < n) a[i+1] += a[i] - t;
    392 
    393         ans.insert(ans.end(), all(cur));
    394     }
    395 
    396     cout << sz(ans) << '\n';
    397     for (auto e:ans) cout << e << ' ';
    398     cout << '\n';
    399 }
    400 
    401 int main() {
    402     int t;
    403     cin >> t;
    404 
    405     forn(tt, t) {
    406         solve();
    407     }
    408 }
    409 ```
    410 
    411 [1650G - Counting Shortcuts](/contest/1650/problem/G "Codeforces Round 776 (Div. 3)")
    412 
    413 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov")
    414 
    415 **Tutorial**
    416 
    417 Tutorial is loading...
    418 
    419 **Solution**
    420 
    421 ```
    422 #include <bits/stdc++.h>
    423 
    424 using namespace std;
    425 
    426 #define forn(i, n) for (int i = 0; i < int(n); i++)
    427 #define sz(v) (int)v.size()
    428 #define eb emplace_back
    429 #define mt make_tuple
    430 
    431 const int INF = INT_MAX >> 1;
    432 const int mod = 1e9 + 7;
    433 
    434 void csum(int &a,int b) {
    435     a = (a + b) % mod;
    436 }
    437 
    438 int s, t;
    439 vector<int> us;
    440 vector<int> dist;
    441 vector<int> dp[2];
    442 int bfs(vector<vector<int>> &g) {
    443     queue<tuple<int,int,int>> q;
    444     q.push(mt(s, 0, 0)); //[v, dist, count]
    445 
    446     int ans = 0, mnd = INF;
    447     us[s] = 1;
    448     dp[0][s] = 1;
    449     dist[s] = 0;
    450     while(!q.empty()) {
    451         auto [v,d, x] = q.front(); q.pop();
    452         // cerr << v << ' ' << d << ' ' << dp[x][v] << endl;
    453         if (v == t) {
    454             if (mnd == INF) {
    455                 mnd = d;
    456             }
    457             csum(ans, dp[x][v]);
    458         }
    459         if (d == mnd + 1) continue;
    460         for (int to : g[v]) if(d <= dist[to]) {
    461             dist[to] = min(dist[to], d+1);
    462             csum(dp[d - dist[to] + 1][to], dp[x][v]);
    463             // cerr << "TO: " <<  to << ' ' << dist[to] << ' ' << d << endl;
    464             if(us[to] == 0 || (us[to] == 1 && dist[to] == d)) q.push(mt(to, d+1, us[to]++));
    465         }
    466     }
    467     return ans;
    468 }
    469 
    470 void solve() {
    471     int n,m; cin >> n >> m;
    472     cin >> s >> t;
    473     us.resize(n+1);
    474     dp[0].resize(n+1);
    475     dp[1].resize(n+1);
    476     dist.resize(n+1);
    477     forn(i, n+1) {
    478         us[i] = dp[0][i] = dp[1][i] = 0;
    479         dist[i] = INF;
    480     }
    481 
    482     vector<vector<int>> g(n+1);
    483     forn(i, m) {
    484         int a,b; cin >> a >> b;
    485         g[a].eb(b);
    486         g[b].eb(a);
    487     }
    488 
    489     cout << bfs(g) << '\n';
    490 }
    491 
    492 int main() {
    493     int t;
    494     cin >> t;
    495 
    496     forn(tt, t) {
    497         solve();
    498     }
    499 }
    500 ```