codeforces-scrape

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

1932.md (8967B)


      1 Source: https://codeforces.com/blog/entry/126196
      2 
      3 [1932A - Thorns and Coins](/contest/1932/problem/A "Codeforces Round 927 (Div. 3)")
      4 
      5 Idea: [denk](/profile/denk "Expert denk")
      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 signed main() {
     19     cin.tie(nullptr);
     20     cout.tie(nullptr);
     21     ios::sync_with_stdio(false);
     22  
     23     int t;
     24     cin >> t;
     25     for(int _ = 0; _ < t; ++_){
     26         int n, ans = 0;
     27         cin >> n;
     28         string s;
     29         cin >> s;
     30         for (int i = 1; i < n; i++) {
     31             ans += (s[i] == '@');
     32             if (s[i] == '*' && s[i - 1] == '*')
     33                 break;
     34         }
     35         cout << ans << "\n";
     36     }
     37     return 0;
     38 }
     39 ```
     40 
     41 [1932B - Chaya Calendar](/contest/1932/problem/B "Codeforces Round 927 (Div. 3)")
     42 
     43 Idea: [Vladosiya](/profile/Vladosiya "Expert Vladosiya")
     44 
     45 **Tutorial**
     46 
     47 Tutorial is loading...
     48 
     49 **Solution**
     50 
     51 ```
     52 def solve():
     53     n = int(input())
     54     a = [int(x) for x in input().split()]
     55     cur = 0
     56     for e in a:
     57         cur += e - cur % e
     58     print(cur)
     59  
     60  
     61 for _ in range(1, int(input()) + 1):
     62     solve()
     63 ```
     64 
     65 [1932C - LR-remainders](/contest/1932/problem/C "Codeforces Round 927 (Div. 3)")
     66 
     67 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov")
     68 
     69 **Tutorial**
     70 
     71 Tutorial is loading...
     72 
     73 **Solution**
     74 
     75 ```
     76 #include <bits/stdc++.h>
     77  
     78 using namespace std;
     79  
     80 #define forn(i, n) for (int i = 0; i < int(n); i++)
     81  
     82 int main() {
     83     int t;
     84     cin >> t;
     85     forn(tt, t) {
     86         int n, m;
     87         cin >> n >> m;
     88         vector<int> a(n);
     89         forn(i, n)
     90             cin >> a[i];
     91         string s;
     92         cin >> s;
     93  
     94         int l = 0;
     95         int r = n - 1;
     96         forn(i, n - 1)
     97             if (s[i] == 'L')
     98                 l++;
     99             else
    100                 r--;
    101         assert(l == r);
    102  
    103         vector<int> b(n);
    104         b[n - 1] = a[l] % m;
    105  
    106         for (int i = n - 2; i >= 0; i--) {
    107             if (s[i] == 'L')
    108                 b[i] = (b[i + 1] * a[--l]) % m;
    109             else
    110                 b[i] = (b[i + 1] * a[++r]) % m;
    111         }
    112         assert(l == 0);
    113         assert(r == n - 1);
    114  
    115         forn(i, n)
    116             cout << b[i] << " ";
    117         cout << endl;
    118     }
    119 }
    120 ```
    121 
    122 [1932D - Card Game](/contest/1932/problem/D "Codeforces Round 927 (Div. 3)")
    123 
    124 Idea: [goncharovmike](/profile/goncharovmike "Candidate Master goncharovmike")
    125 
    126 **Tutorial**
    127 
    128 Tutorial is loading...
    129 
    130 **Solution**
    131 
    132 ```
    133 #include <bits/stdc++.h>
    134  
    135 #define long long long int
    136 #define DEBUG
    137 using namespace std;
    138  
    139 // @author: pashka
    140  
    141 int main() {
    142     ios::sync_with_stdio(false);
    143     
    144     int t;
    145     cin >> t;
    146     for (int tt = 0; tt < t; tt++) {
    147         int n;
    148         cin >> n;
    149     
    150         string suites = "CDHS";
    151     
    152         string ts;
    153         cin >> ts;
    154         int trump = suites.find(ts[0]);
    155     
    156         vector<int> bs[4];
    157         for (int i = 0; i < 2 * n; i++) {
    158             string s;
    159             cin >> s;
    160             bs[suites.find(s[1])].push_back(s[0] - '2');
    161         }
    162     
    163         vector<string> res;
    164         vector<string> left;
    165         for (int i = 0; i < 4; i++) {
    166             sort(bs[i].begin(), bs[i].end());
    167             if (i == trump) continue;
    168             if (bs[i].size() % 2 == 1) {
    169                 int x = bs[i].back();
    170                 left.push_back(string() + char('2' + x) + suites[i]);
    171                 bs[i].pop_back();
    172             }
    173             for (int j = 0; j < (int) bs[i].size(); j++) {
    174                 int x = bs[i][j];
    175                 res.push_back(string() + char('2' + x) + suites[i]);
    176             }
    177         }
    178         if (left.size() > bs[trump].size()) {
    179             cout << "IMPOSSIBLE\n";
    180         } else {
    181             for (string s : left) {
    182                 res.push_back(s);
    183                 int x = bs[trump].back();
    184                 bs[trump].pop_back();
    185                 res.push_back(string() + char('2' + x) + suites[trump]);
    186             }
    187             for (int j = 0; j < (int) bs[trump].size(); j++) {
    188                 int x = bs[trump][j];
    189                 res.push_back(string() + char('2' + x) + suites[trump]);
    190             }
    191             for (int i = 0; i < 2 * n; i += 2) {
    192                 cout << res[i] << " " << res[i + 1] << "\n";
    193             }
    194         }
    195     }
    196 }
    197 ```
    198 
    199 [1932E - Final Countdown](/contest/1932/problem/E "Codeforces Round 927 (Div. 3)")
    200 
    201 Idea: [step_by_step](/profile/step_by_step "International Grandmaster step_by_step")
    202 
    203 **Tutorial**
    204 
    205 Tutorial is loading...
    206 
    207 **Solution**
    208 
    209 ```
    210 #include <bits/stdc++.h>
    211 #define long long long int
    212 #define DEBUG
    213 using namespace std;
    214  
    215 // @author: pashka
    216  
    217 int main() {
    218     ios::sync_with_stdio(false);
    219     
    220     int t;
    221     cin >> t;
    222     while (t--) {
    223         int n;
    224         cin >> n;
    225         string s;
    226         cin >> s;
    227         reverse(s.begin(), s.end());
    228         vector<int> a(n + 1);
    229         for (int i = n - 1; i >= 0; i--) {
    230             a[i] = a[i + 1] + (s[i] - '0');
    231         }
    232         string res;
    233         int c = 0;
    234         for (int i = 0; i < n; i++) {
    235             c += a[i];
    236             res += (char)(c % 10 + '0');
    237             c /= 10;
    238         }
    239         res += (char)(c + '0');
    240         while (res.back() == '0') {
    241             res.pop_back();
    242         }
    243         reverse(res.begin(), res.end());
    244         cout << res << "\n";
    245     }
    246  
    247     return 0;
    248 }
    249 ```
    250 
    251 [1932F - Feed Cats](/contest/1932/problem/F "Codeforces Round 927 (Div. 3)")
    252 
    253 Idea: [denk](/profile/denk "Expert denk")
    254 
    255 **Tutorial**
    256 
    257 Tutorial is loading...
    258 
    259 **Solution**
    260 
    261 ```
    262 #include <bits/stdc++.h>
    263  
    264 //#define int long long
    265 #define pb emplace_back
    266 #define mp make_pair
    267 #define x first
    268 #define y second
    269 #define all(a) a.begin(), a.end()
    270 #define rall(a) a.rbegin(), a.rend()
    271  
    272 typedef long double ld;
    273 typedef long long ll;
    274  
    275 using namespace std;
    276  
    277 mt19937 rnd(time(nullptr));
    278  
    279 const ll inf = 1e18;
    280 const ll M = 998244353;
    281 const ld pi = atan2(0, -1);
    282 const ld eps = 1e-6;
    283  
    284 void solve(int tc){
    285     int n, m;
    286     cin >> n >> m;
    287     vector<pair<int, int>> a(m);
    288     vector<int> op(n + 1);
    289     vector<vector<int>> del(n + 1);
    290     for(auto &e: a) {
    291         cin >> e.x >> e.y;
    292         op[e.x]++;
    293         del[e.y].emplace_back(e.x);
    294     }
    295     multiset<int> cur;
    296     vector<int> dp(n + 1);
    297     for(int i = 1; i <= n; ++i){
    298         dp[i] = dp[i - 1];
    299         for(int j = 0; j < op[i]; ++j){
    300             cur.insert(i);
    301         }
    302         if(!cur.empty()){
    303             dp[i] = max(dp[i], int(dp[*cur.begin() - 1] + cur.size()));
    304         }
    305         for(int e: del[i]){
    306             cur.erase(cur.find(e));
    307         }
    308     }
    309     cout << dp[n];
    310 }
    311  
    312 bool multi = true;
    313  
    314 signed main() {
    315     int t = 1;
    316     if (multi)cin >> t;
    317     for (int i = 1; i <= t; ++i) {
    318         solve(i);
    319         cout << "\n";
    320     }
    321     return 0;
    322 }
    323 ```
    324 
    325 [1932G - Moving Platforms](/contest/1932/problem/G "Codeforces Round 927 (Div. 3)")
    326 
    327 Idea: [denk](/profile/denk "Expert denk")
    328 
    329 **Tutorial**
    330 
    331 Tutorial is loading...
    332 
    333 **Solution**
    334 
    335 ```
    336 #include <bits/stdc++.h>
    337 #define long long long int
    338 #define DEBUG
    339 using namespace std;
    340  
    341 // @author: pashka
    342  
    343 struct triple {
    344     long d, x, y;
    345 };
    346  
    347 triple eucl(long a, long b) {
    348     if (b == 0) {
    349         return {a, 1, 0};
    350     }
    351     long k = a / b;
    352     auto [d, x, y] = eucl(b, a - k * b);
    353     return {d, y, x - k * y};
    354 }
    355  
    356 struct test {
    357     void solve() {
    358         int n, m, H;
    359         cin >> n >> m >> H;
    360         vector<long> l(n);
    361         for (int i = 0; i < n; i++) cin >> l[i];
    362         vector<long> s(n);
    363         for (int i = 0; i < n; i++) cin >> s[i];
    364  
    365         vector<vector<int>> g(n);
    366         for (int i = 0; i < m; i++) {
    367             int x, y;
    368             cin >> x >> y;
    369             x--;
    370             y--;
    371             g[x].push_back(y);
    372             g[y].push_back(x);
    373         }
    374  
    375         const long INF = 1e18;
    376         vector<long> d(n, INF);
    377         d[0] = 0;
    378         set<pair<long, int>> q;
    379         q.insert({d[0], 0});
    380         while (!q.empty()) {
    381             auto p = *q.begin();
    382             q.erase(p);
    383             int v = p.second;
    384             long t = d[v];
    385             for (int u: g[v]) {
    386                 long a = (l[v] + (t % H) * s[v]) - (l[u] + (t % H) * s[u]);
    387                 a %= H;
    388                 if (a < 0) a += H;
    389                 long b = s[u] - s[v];
    390                 b %= H;
    391                 if (b < 0) b += H;
    392                 // a - bx = yH
    393                 auto [dd, x, y] = eucl(b, H);
    394                 // xb + yH = dd
    395                 if (a % dd != 0) continue;
    396                 x *= a / dd;
    397                 x %= (H / dd);
    398                 if (x < 0) x += H / dd;
    399                 long dt = x;
    400                 if (d[v] + dt + 1 < d[u]) {
    401                     q.erase({d[u], u});
    402                     d[u] = d[v] + dt + 1;
    403                     q.insert({d[u], u});
    404                 }
    405             }
    406         }
    407         long res = d[n - 1];
    408         if (res == INF) res = -1;
    409         cout << res << "\n";
    410     }
    411 };
    412  
    413 int main() {
    414     ios::sync_with_stdio(false);
    415  
    416     int n;
    417     cin >> n;
    418     for (int i = 0; i < n; i++) {
    419         test().solve();
    420     }
    421     
    422     return 0;
    423 }
    424 ```