codeforces-scrape

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

1848.md (7745B)


      1 Source: https://codeforces.com/blog/entry/118333
      2 
      3 [1848A - Vika and Her Friends](/contest/1848/problem/A "Codeforces Round 885 (Div. 2)")
      4 
      5 Idea: [diskoteka](/profile/diskoteka "Candidate Master diskoteka")
      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 int long long
     19  
     20 int32_t main() {
     21     int t;
     22     cin >> t;
     23     while (t--) {
     24         int n, m, k;
     25         cin >> n >> m >> k;
     26         int x, y;
     27         cin >> x >> y;
     28         string ans = "YES\n";
     29         for (int i = 0; i < k; ++i) {
     30             int xx, yy;
     31             cin >> xx >> yy;
     32             if ((x + y) % 2 == (xx + yy) % 2) {
     33                 ans = "NO\n";
     34             }
     35         }
     36         cout << ans;
     37     }
     38     return 0;
     39 }
     40 ```
     41 
     42 [1848B - Vika and the Bridge](/contest/1848/problem/B "Codeforces Round 885 (Div. 2)")
     43 
     44 Idea: [diskoteka](/profile/diskoteka "Candidate Master diskoteka")
     45 
     46 **Tutorial**
     47 
     48 Tutorial is loading...
     49 
     50 **Solution**
     51 
     52 ```
     53 #include <bits/stdc++.h>
     54  
     55 using namespace std;
     56  
     57 int main() {
     58     int t;
     59     cin >> t;
     60     while (t--) {
     61         int n, k;
     62         cin >> n >> k;
     63         vector<int> c(n);
     64         for (int i = 0; i < n; ++i) {
     65             cin >> c[i];
     66         }
     67         vector<int> last(k, -1);
     68         vector<int> max_step(k), max2_step(k);
     69         for (int i = 0; i < n; ++i) {
     70             int step = i - last[c[i] - 1];
     71             if (step > max_step[c[i] - 1]) {
     72                 max2_step[c[i] - 1] = max_step[c[i] - 1];
     73                 max_step[c[i] - 1] = step;
     74             } else if (step > max2_step[c[i] - 1]) {
     75                 max2_step[c[i] - 1] = step;
     76             }
     77             last[c[i] - 1] = i;
     78         }
     79         for (int i = 0; i < k; ++i) {
     80             int step = n - last[i];
     81             if (step > max_step[i]) {
     82                 max2_step[i] = max_step[i];
     83                 max_step[i] = step;
     84             } else if (step > max2_step[i]) {
     85                 max2_step[i] = step;
     86             }
     87         }
     88         int ans = 1e9;
     89         for (int i = 0; i < k; ++i) {
     90             ans = min(ans, max((max_step[i] + 1) / 2, max2_step[i]));
     91         }
     92         cout << ans - 1 << "\n";
     93     }
     94     return 0;
     95 }
     96 ```
     97 
     98 [1848C - Vika and Price Tags](/contest/1848/problem/C "Codeforces Round 885 (Div. 2)")
     99 
    100 Idea: [pavlekn](/profile/pavlekn "Candidate Master pavlekn")
    101 
    102 **Tutorial**
    103 
    104 Tutorial is loading...
    105 
    106 **Solution**
    107 
    108 ```
    109 #include <bits/stdc++.h>
    110  
    111 using namespace std;
    112  
    113 #define int long long
    114  
    115 int gcd(int a, int b) {
    116     if (a == 0) {
    117         return 0;
    118     }
    119     if (b == 0) {
    120         return 1;
    121     }
    122     if (a >= b) {
    123         int r = a % b;
    124         int k = a / b;
    125         if (k % 2 == 1) {
    126             return gcd(b, r) + k + k / 2;
    127         } else {
    128             return gcd(r, b) + k + k / 2;
    129         }
    130     }
    131     return 1 + gcd(b, abs(a - b));
    132 }
    133  
    134 int calc(int a, int b) {
    135     if (a == 0) {
    136         return 0;
    137     }
    138     if (b == 0) {
    139         return 1;
    140     }
    141     return 1 + calc(b, abs(a - b));
    142 }
    143  
    144 int32_t main() {
    145     ios_base::sync_with_stdio(false);
    146     cin.tie(0);
    147     int t;
    148     cin >> t;
    149     for (int _ = 0; _ < t; ++_) {
    150         int n;
    151         cin >> n;
    152         vector<int> a(n);
    153         vector<int> b(n);
    154         for (int i = 0; i < n; ++i) {
    155             cin >> a[i];
    156         }
    157         for (int i = 0; i < n; ++i) {
    158             cin >> b[i];
    159         }
    160         set<int> cnt;
    161         for (int i = 0; i < n; ++i) {
    162             if (a[i] == 0 && b[i] == 0) {
    163                 continue;
    164             }
    165             cnt.insert(gcd(a[i], b[i]) % 3);
    166         }
    167         if (cnt.size() <= 1) {
    168             cout << "YES" << endl;
    169         } else {
    170             cout << "NO" << endl;
    171         }
    172     }
    173     return 0;
    174 }
    175 ```
    176 
    177 [1848D - Vika and Bonuses](/contest/1848/problem/D "Codeforces Round 885 (Div. 2)")
    178 
    179 Idea: [diskoteka](/profile/diskoteka "Candidate Master diskoteka")
    180 
    181 **Tutorial**
    182 
    183 Tutorial is loading...
    184 
    185 **Solution**
    186 
    187 ```
    188 #include <bits/stdc++.h>
    189  
    190 using namespace std;
    191  
    192 #define int long long
    193  
    194 int f(int s, int k) {
    195     // (s + 20x) * (k - 4x)
    196     // (-80)x^2 + (20k - 4s)x + (sk)
    197     // -b/2a = (5k-s)/40
    198     int x = (5 * k - s) / 40;
    199     x = min(x, k / 4);
    200     int res = s * k;
    201     if (x > 0) {
    202         res = max(res, (s + 20 * x) * (k - 4 * x));
    203     }
    204     x = min(x + 1, k / 4);
    205     if (x > 0) {
    206         res = max(res, (s + 20 * x) * (k - 4 * x));
    207     }
    208     return res;
    209 }
    210  
    211 int32_t main() {
    212     int t;
    213     cin >> t;
    214     while (t--) {
    215         int s, k;
    216         cin >> s >> k;
    217         int ans = s * k;
    218         if (s % 10 == 5) {
    219             ans = max(ans, (s + 5) * (k - 1));
    220         } else if (s % 10) {
    221             if (s % 2 == 1) {
    222                 s += s % 10;
    223                 --k;
    224             }
    225             for (int i = 0; i < 4; ++i) {
    226                 if (k > 0) {
    227                     ans = max(ans, f(s, k));
    228                 }
    229                 s += s % 10;
    230                 --k;
    231             }
    232         }
    233         cout << ans << "\n";
    234     }
    235     return 0;
    236 }
    237 ```
    238 
    239 [1848E - Vika and Stone Skipping](/contest/1848/problem/E "Codeforces Round 885 (Div. 2)")
    240 
    241 Idea: [diskoteka](/profile/diskoteka "Candidate Master diskoteka")
    242 
    243 **Tutorial**
    244 
    245 Tutorial is loading...
    246 
    247 **Solution**
    248 
    249 ```
    250 #include <bits/stdc++.h>
    251  
    252 using namespace std;
    253  
    254 const int K = 1e6;
    255  
    256 #define int long long
    257  
    258 int mod;
    259  
    260 int dp[K + 1];
    261 int cnt[K + 1];
    262  
    263 const int MM = 3e6 + 7;
    264  
    265 int inv[MM];
    266  
    267 int cc = 0;
    268  
    269 int mul(int a, int b) {
    270     int bb = b;
    271     while (bb % mod == 0) {
    272         ++cc;
    273         bb /= mod;
    274     }
    275     return (a * (bb % mod)) % mod;
    276 }
    277  
    278 int dv(int a, int b) {
    279     int bb = b;
    280     while (bb % mod == 0) {
    281         --cc;
    282         bb /= mod;
    283     }
    284     return (a * inv[bb % mod]) % mod;
    285 }
    286  
    287  
    288 int32_t main() {
    289     ios_base::sync_with_stdio(false);
    290     cin.tie(0);
    291     int x, q;
    292     cin >> x >> q >> mod;
    293     inv[1] = 1;
    294     for (int i = 2; i < MM && i < mod; i++) {
    295         inv[i] = mod - inv[mod % i] * (mod / i) % mod;
    296     }
    297     int y = x;
    298     for (int i = 3; i <= K; i += 2) {
    299         if (dp[i]) {
    300             continue;
    301         }
    302         for (int j = i; j <= K; j += 2 * i) {
    303             dp[j] = i;
    304         }
    305     }
    306     int ans = 1;
    307     while (x % 2 == 0) {
    308         x /= 2;
    309     }
    310     for (int i = 3; i <= K; i += 2) {
    311         while (x % i == 0) {
    312             ans = dv(ans, cnt[i] + 1);
    313             ++cnt[i];
    314             ans = mul(ans, cnt[i] + 1);
    315             x /= i;
    316         }
    317     }
    318     int f = 1;
    319     if (x > 1) {
    320         ans = mul(ans, 2);
    321     }
    322     x = y;
    323     for (int i = 0; i < q; ++i) {
    324         int d;
    325         cin >> d;
    326         while (d % 2 == 0) {
    327             d /= 2;
    328         }
    329         int k = d;
    330         while (dp[k]) {
    331             ans = dv(ans, cnt[dp[k]] + 1);
    332             ++cnt[dp[k]];
    333             ans = mul(ans, cnt[dp[k]] + 1);
    334             k /= dp[k];
    335         }
    336         if (cc) {
    337             cout << 0 << '\n';
    338         } else {
    339             cout << ans << '\n';
    340         }
    341     }
    342     return 0;
    343 }
    344 ```
    345 
    346 [1848F - Vika and Wiki](/contest/1848/problem/F "Codeforces Round 885 (Div. 2)")
    347 
    348 Idea: [pavlekn](/profile/pavlekn "Candidate Master pavlekn")
    349 
    350 **Tutorial**
    351 
    352 Tutorial is loading...
    353 
    354 **Solution**
    355 
    356 ```
    357 #include <bits/stdc++.h>
    358  
    359 using namespace std;
    360  
    361 const int MAXN = (1 << 20);
    362  
    363 int a[MAXN];
    364  
    365 int solve(int n) {
    366     if (n == 1) {
    367         if (a[0] == 0) {
    368             return 0;
    369         } else {
    370             return 1;
    371         }
    372     }
    373     int fl = true;
    374     for (int i = 0; i < n / 2; ++i) {
    375         if (a[i] != a[i + n / 2]) {
    376             fl = false;
    377         }
    378     }
    379     if (fl) {
    380         return solve(n / 2);
    381     }
    382     for (int i = 0; i < n / 2; ++i) {
    383         a[i] ^= a[i + n / 2];
    384     }
    385     return n / 2 + solve(n / 2);
    386 }
    387  
    388 int32_t main() {
    389     int n;
    390     scanf("%d", &n);
    391     for (int i = 0; i < n; ++i) {
    392         scanf("%d", &a[i]);
    393     }
    394     cout << solve(n) << endl;
    395     return 0;
    396 }
    397 ```