codeforces-scrape

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

1493.md (9829B)


      1 Source: https://codeforces.com/blog/entry/88422
      2 
      3 [1493A - Anti-knapsack](/contest/1493/problem/A "Codeforces Round 705 (Div. 2)")
      4 
      5 Idea: [AlFlen](/profile/AlFlen "Master AlFlen"), [74TrAkToR](/profile/74TrAkToR "Master 74TrAkToR")
      6 
      7 **Tutorial**
      8 
      9 Tutorial is loading...
     10 
     11 **Solution (74TrAkToR)**
     12 
     13 ```
     14 #include <bits/stdc++.h>
     15 
     16 using namespace std;
     17 
     18 int main() {
     19     ios_base::sync_with_stdio(0);
     20     cin.tie(0);
     21 
     22     int t, n, k;
     23     cin >> t;
     24     while (t--) {
     25         cin >> n >> k;
     26         cout << n - k + k / 2 << '\n';
     27         for (int i = k + 1; i <= n; ++i) cout << i << " ";
     28         for (int i = (k + 1) / 2; i < k; ++i) cout << i << " ";
     29         cout << '\n';
     30     }
     31 
     32     return 0;
     33 }
     34 ```
     35 
     36 [1493B - Planet Lapituletti](/contest/1493/problem/B "Codeforces Round 705 (Div. 2)")
     37 
     38 Idea: [AlFlen](/profile/AlFlen "Master AlFlen")
     39 
     40 **Tutorial**
     41 
     42 Tutorial is loading...
     43 
     44 **Solution (74TrAkToR)**
     45 
     46 ```
     47 #include <bits/stdc++.h>
     48 
     49 using namespace std;
     50 
     51 vector < int > go = {0, 1, 5, -1, -1, 2, -1, -1, 8, -1};
     52 int inf = 1e9 + 7;
     53 
     54 int get(int x) {
     55     string s = to_string(x);
     56     if ((int)s.size() == 1) s = "0" + s;
     57     string answ = "";
     58     for (int i = 1; i >= 0; --i) {
     59         if (go[s[i] - '0'] == -1) return inf;
     60         answ += char(go[s[i] - '0'] + '0');
     61     }
     62     return stoi(answ);
     63 }
     64 
     65 string good(int x) {
     66     string ans = to_string(x);
     67     if (x < 10) {
     68         ans = "0" + ans;
     69     }
     70     return ans;
     71 }
     72 
     73 main() {
     74     ios_base::sync_with_stdio(0);
     75     cin.tie(0);
     76     cout.tie(0);
     77     int t, h, m, H, M;
     78     cin >> t;
     79     string s;
     80     while (t--) {
     81         cin >> h >> m;
     82         cin >> s;
     83         H = (s[0] - '0') * 10 + s[1] - '0';
     84         M = (s[3] - '0') * 10 + s[4] - '0';
     85         while (1) {
     86             if (M == m) {
     87                 H++, M = 0;
     88             }
     89             if (H == h) {
     90                 H = 0;
     91             }
     92             if (get(M) < h && get(H) < m) {
     93                 cout << good(H) << ":" << good(M) << '\n';
     94                 break;
     95             }
     96             M++;
     97         }
     98     }
     99     return 0;
    100 }
    101 ```
    102 
    103 [1493C - K-beautiful Strings](/contest/1493/problem/C "Codeforces Round 705 (Div. 2)")
    104 
    105 Idea: [74TrAkToR](/profile/74TrAkToR "Master 74TrAkToR")
    106 
    107 **Tutorial**
    108 
    109 Tutorial is loading...
    110 
    111 **Solution (74TrAkToR)**
    112 
    113 ```
    114 #include <bits/stdc++.h>
    115 
    116 using namespace std;
    117 
    118 int cnt[26];
    119 
    120 int get(int x, int k) {
    121     return (k - x % k) % k;
    122 }
    123 
    124 main() {
    125     ios_base::sync_with_stdio(0);
    126     cin.tie(0);
    127     cout.tie(0);
    128     int n, k, t;
    129     cin >> t;
    130     while (t--) {
    131         cin >> n >> k;
    132         string s;
    133         cin >> s;
    134         for (int j = 0; j < 26; ++j) cnt[j] = 0;
    135         for (auto c : s) cnt[c - 'a']++;
    136 
    137         int sum = 0, flag = 1;
    138         for (int i = 0; i < 26; ++i) {
    139             sum += get(cnt[i], k);
    140         }
    141 
    142         if (sum == 0) {
    143             cout << s << '\n';
    144             flag = 0;
    145         }
    146 
    147         if (n % k != 0) {
    148             cout << -1 << '\n';
    149             continue;
    150         }
    151 
    152         for (int i = n - 1; i >= 0 && flag; --i) {
    153             sum -= get(cnt[s[i] - 'a'], k);
    154             cnt[s[i] - 'a']--;
    155             sum += get(cnt[s[i] - 'a'], k);
    156             for (int j = s[i] - 'a' + 1; j < 26; ++j) {
    157 
    158                 int lst_sum = sum;
    159                 sum -= get(cnt[j], k);
    160                 cnt[j]++;
    161                 sum += get(cnt[j], k);
    162 
    163                 if (i + sum + 1 <= n) {
    164                     for (int pos = 0; pos < i; ++pos) {
    165                         cout << s[pos];
    166                     }
    167                     cout << char('a' + j);
    168 
    169                     string add = "";
    170                     for (int w = 0; w < 26; ++w) {
    171                         int f = get(cnt[w], k);
    172                         while (f) {
    173                             f--;
    174                             add += char('a' + w);
    175                         }
    176                     }
    177                     while ((int)add.size() + i + 1 < n) {
    178                         add += "a";
    179                     }
    180 
    181                     sort(add.begin(), add.end());
    182                     cout << add << '\n';
    183                     flag = 0;
    184                     break;
    185                 }
    186 
    187                 cnt[j]--;
    188                 sum = lst_sum;
    189             }
    190         }
    191     }
    192     return 0;
    193 }
    194 ```
    195 
    196 [1493D - GCD of an Array](/contest/1493/problem/D "Codeforces Round 705 (Div. 2)")
    197 
    198 Idea: [74TrAkToR](/profile/74TrAkToR "Master 74TrAkToR")
    199 
    200 **Tutorial**
    201 
    202 Tutorial is loading...
    203 
    204 **Solution (74TrAkToR)**
    205 
    206 ```
    207 #include <bits/stdc++.h>
    208 
    209 using namespace std;
    210 
    211 typedef long long ll;
    212 
    213 int const maxn = 2e5 + 5, max_val = 2e5 + 5;
    214 ll mod = 1e9 + 7, ans = 1;
    215 int nxt[max_val], n;
    216 multiset <int> cnt[max_val];
    217 map <int, int> cnt_divisor[maxn];
    218 
    219 void add(int i, int x) {
    220     while (x != 1) {
    221         int div = nxt[x], add = 0;
    222         while (nxt[x] == div) add++, x = x / nxt[x];
    223 
    224         int lst = cnt_divisor[i][div];
    225         cnt_divisor[i][div] += add;
    226         int lst_min = 0;
    227         if ((int)cnt[div].size() == n) {
    228             lst_min = (*cnt[div].begin());
    229         }
    230         if (lst != 0) {
    231             cnt[div].erase(cnt[div].find(lst));
    232         }
    233         cnt[div].insert(lst + add);
    234         if ((int)cnt[div].size() == n) {
    235             for (int j = lst_min + 1; j <= (*cnt[div].begin()); ++j) {
    236                 ans = ans * (ll)div % mod;
    237             }
    238         }
    239     }
    240 }
    241 
    242 main() {
    243     ios_base::sync_with_stdio(0);
    244     cin.tie(0);
    245 
    246     int q, l, x;
    247     cin >> n >> q;
    248 
    249     for (int i = 2; i < maxn; ++i) {
    250         if (nxt[i] == 0) {
    251             nxt[i] = i;
    252             if (i > 10000) continue;
    253             for (int j = i * i; j < maxn; j += i) {
    254                 if (nxt[j] == 0) nxt[j] = i;
    255             }
    256         }
    257     }
    258 
    259     for (int i = 1; i <= n; ++i) {
    260         cin >> x;
    261         add(i, x);
    262     }
    263 
    264     for (int i = 1; i <= q; ++i) {
    265         cin >> l >> x;
    266         add(l, x);
    267         cout << ans << '\n';
    268     }
    269 
    270     return 0;
    271 }
    272 ```
    273 
    274 [1493E - Enormous XOR](/contest/1493/problem/E "Codeforces Round 705 (Div. 2)")
    275 
    276 Idea: [AlFlen](/profile/AlFlen "Master AlFlen")
    277 
    278 **Tutorial**
    279 
    280 Tutorial is loading...
    281 
    282 **Solution (74TrAkToR)**
    283 
    284 ```
    285 #include<bits/stdc++.h>
    286 
    287 using namespace std;
    288 
    289 string add(string s) {
    290     int i = (int)s.size() - 1;
    291     while (s[i] == '1') {
    292         s[i] = '0';
    293         i--;
    294     }
    295     s[i] = '1';
    296     return s;
    297 }
    298 
    299 main() {
    300     ios_base::sync_with_stdio(0);
    301     cin.tie(0);
    302     cout.tie(0);
    303     int n;
    304     cin >> n;
    305     string l, r;
    306     cin >> l >> r;
    307     if (l == r) {
    308         cout << r << '\n';
    309         return 0;
    310     }
    311     if (l[0] != r[0]) {
    312         for (int i = 1; i <= n; ++i) cout << "1";
    313         return 0;
    314     }
    315     if (add(l) == r || r.back() == '1') {
    316         cout << r << '\n';
    317         return 0;
    318     }
    319     cout << add(r) << '\n';
    320     return 0;
    321 }
    322 ```
    323 
    324 [1493F - Enchanted Matrix](/contest/1493/problem/F "Codeforces Round 705 (Div. 2)")
    325 
    326 Idea: [74TrAkToR](/profile/74TrAkToR "Master 74TrAkToR")
    327 
    328 **Tutorial**
    329 
    330 Tutorial is loading...
    331 
    332 **Solution (74TrAkToR)**
    333 
    334 ```
    335 #include <bits/stdc++.h>
    336 
    337 using namespace std;
    338 
    339 int const maxn = 1005;
    340 int dp[maxn];
    341 vector < vector < int > > T;
    342 
    343 int ask(int lx1, int ly1, int rx1, int ry1, int lx2, int ly2, int rx2, int ry2) {
    344     cout << "? " << rx1 - lx1 + 1 << " " << ry1 - ly1 + 1 << " " << lx1 << " " << ly1
    345     << " " << lx2 << " " << ly2 << endl;
    346     int ans;
    347     cin >> ans;
    348     return ans;
    349 }
    350 
    351 int good(int l, int r) {
    352     if (l == r) return 1;
    353 
    354     int cnt = (r - l + 1) / 2;
    355     if (ask(T[l][0], T[l][1], T[l + cnt - 1][2], T[l + cnt - 1][3], T[l + cnt][0], T[l + cnt][1], T[l + 2 * cnt - 1][2], T[l + 2 * cnt - 1][3])) {
    356         return good(l + cnt, r);
    357     }
    358     return 0;
    359 }
    360 
    361 main() {
    362     ios_base::sync_with_stdio(0);
    363     cin.tie(0);
    364     cout.tie(0);
    365     int n, m, cntn = 0, cntm = 0;
    366     cin >> n >> m;
    367 
    368     for (int i = n; i >= 1; --i) {
    369         if (n % i != 0 || dp[i] != 0) continue;
    370 
    371         for (int j = 2 * i; j <= n; j += i) {
    372             if (n % j == 0 && j % i == 0) {
    373                 T = {};
    374                 for (int k = 1; k <= j / i; ++k) {
    375                     T.push_back({(k - 1) * i + 1, 1, k * i, m});
    376                 }
    377                 if (good(0, (int)T.size() - 1)) dp[i] = 1;
    378                 else dp[i] = 2;
    379                 break;
    380             }
    381         }
    382 
    383         if (dp[i] == 2) {
    384             for (int j = 1; j <= n; ++j) {
    385                 if (i % j == 0) dp[j] = 2;
    386             }
    387         }
    388         else {
    389             dp[i] = 1;
    390             for (int j = i; j <= n; ++j) {
    391                 if (dp[j] == 1) {
    392                     int w = __gcd(i, j);
    393                     for (int pos = w; pos <= n; pos += w) {
    394                         dp[pos] = 1;
    395                     }
    396                 }
    397             }
    398         }
    399     }
    400 
    401     for (int i = 1; i <= n; ++i) {
    402         if (n % i == 0) cntn += (dp[i] == 1);
    403         dp[i] = 0;
    404     }
    405 
    406     for (int i = m; i >= 1; --i) {
    407         if (m % i != 0 || dp[i] != 0) continue;
    408 
    409         for (int j = 2 * i; j <= m; j += i) {
    410             if (m % j == 0 && j % i == 0) {
    411                 T = {};
    412                 for (int k = 1; k <= j / i; ++k) {
    413                     T.push_back({1, (k - 1) * i + 1, n, k * i});
    414                 }
    415                 if (good(0, (int)T.size() - 1)) dp[i] = 1;
    416                 else dp[i] = 2;
    417                 break;
    418             }
    419         }
    420         if (dp[i] == 2) {
    421             for (int j = 1; j <= i; ++j) {
    422                 if (i % j == 0) {
    423                     dp[j] = 2;
    424                 }
    425             }
    426         }
    427         else {
    428             dp[i] = 1;
    429             for (int j = i; j <= m; ++j) {
    430                 if (dp[j] == 1) {
    431                     int w = __gcd(i, j);
    432                     for (int pos = w; pos <= m; pos += w) {
    433                         dp[pos] = 1;
    434                     }
    435                 }
    436             }
    437         }
    438     }
    439 
    440     for (int i = 1; i <= m; ++i) {
    441         if (m % i == 0) cntm += (dp[i] == 1);
    442     }
    443     cout << "! " << cntn * cntm << endl;
    444     return 0;
    445 }
    446 ```