codeforces-scrape

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

1475.md (6716B)


      1 Source: https://codeforces.com/blog/entry/87188
      2 
      3 [1475A - Odd Divisor](/contest/1475/problem/A "Codeforces Round 697 (Div. 3)")
      4 
      5 Problem authors: [Stepavly](/profile/Stepavly "Master Stepavly"), [Supermagzzz](/profile/Supermagzzz "Master Supermagzzz")
      6 
      7 **Editorial**
      8 
      9 Tutorial is loading...
     10 
     11 **Solution**
     12 
     13 ```
     14 #include <bits/stdc++.h>
     15 
     16 using namespace std;
     17 using ll = long long;
     18 using ld = long double;
     19 
     20 void solve() {
     21   ll n;
     22   cin >> n;
     23   if (n & (n - 1)) {
     24     cout << "YES\n";
     25   } else {
     26     cout << "NO\n";
     27   }
     28 }
     29 
     30 int main() {
     31   int t;
     32   cin >> t;
     33   while (t--) {
     34     solve();
     35   }
     36 }
     37 ```
     38 
     39 [1475B - New Year's Number](/contest/1475/problem/B "Codeforces Round 697 (Div. 3)")
     40 
     41 Problem author: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov")
     42 
     43 **Editorial**
     44 
     45 Tutorial is loading...
     46 
     47 **Solution**
     48 
     49 ```
     50 #include <bits/stdc++.h>
     51 
     52 #include <utility>
     53 using namespace std;
     54 
     55 using pii = pair<int, int>;
     56 
     57 int main() {
     58   int test;
     59   cin >> test;
     60   while (test-- > 0) {
     61     int n;
     62     cin >> n;
     63     int cnt2021 = n % 2020;
     64     int cnt2020 = (n - cnt2021) / 2020 - cnt2021;
     65     if (cnt2020 >= 0 && 2020 * cnt2020 + 2021 * cnt2021 == n) {
     66       cout << "YES\n";
     67     } else {
     68       cout << "NO\n";
     69     }
     70   }
     71   return 0;
     72 }
     73 ```
     74 
     75 [1475C - Ball in Berland](/contest/1475/problem/C "Codeforces Round 697 (Div. 3)")
     76 
     77 Problem authors: [Stepavly](/profile/Stepavly "Master Stepavly"), [Supermagzzz](/profile/Supermagzzz "Master Supermagzzz")
     78 
     79 **Editorial**
     80 
     81 Tutorial is loading...
     82 
     83 **Solution**
     84 
     85 ```
     86 #include <bits/stdc++.h>
     87 
     88 using namespace std;
     89 using ll = long long;
     90 using ld = long double;
     91 
     92 void solve() {
     93   int A, B, k;
     94   cin >> A >> B >> k;
     95   vector<int> a(A), b(B);
     96   vector<pair<int, int>> edges(k);
     97   for (auto &[x, y] : edges) {
     98     cin >> x;
     99   }
    100   for (auto &[x, y] : edges) {
    101     cin >> y;
    102   }
    103   for (auto &[x, y] : edges) {
    104     x--;
    105     y--;
    106     a[x]++;
    107     b[y]++;
    108   }
    109   ll ans = 0;
    110   for (auto &[x, y] : edges) {
    111     ans += k - a[x] - b[y] + 1;
    112   }
    113   cout << ans / 2 << "\n";
    114 }
    115 
    116 int main() {
    117   int t;
    118   cin >> t;
    119   while (t--) {
    120     solve();
    121   }
    122 }
    123 ```
    124 
    125 [1475D - Cleaning the Phone](/contest/1475/problem/D "Codeforces Round 697 (Div. 3)")
    126 
    127 Problem authors: [Stepavly](/profile/Stepavly "Master Stepavly"), [Supermagzzz](/profile/Supermagzzz "Master Supermagzzz")
    128 
    129 **Editorial**
    130 
    131 Tutorial is loading...
    132 
    133 **Solution**
    134 
    135 ```
    136 #include <bits/stdc++.h>
    137 
    138 using namespace std;
    139 using ll = long long;
    140 using ld = long double;
    141 
    142 void solve() {
    143   int n, m;
    144   cin >> n >> m;
    145   vector<int> a, b;
    146   vector<int> v(n);
    147   for (int &e : v) {
    148     cin >> e;
    149   }
    150   for (int &e : v) {
    151     int x;
    152     cin >> x;
    153     if (x == 1) {
    154       a.push_back(e);
    155     } else {
    156       b.push_back(e);
    157     }
    158   }
    159   sort(a.rbegin(), a.rend());
    160   sort(b.rbegin(), b.rend());
    161   ll curSumA = 0;
    162   int r = (int)b.size();
    163   ll curSumB = accumulate(b.begin(), b.end(), 0ll);
    164   int ans = INT_MAX;
    165   for (int l = 0; l <= a.size(); l++) {
    166     while (r > 0 && curSumA + curSumB - b[r - 1] >= m) {
    167       r--;
    168       curSumB -= b[r];
    169     }
    170     if (curSumB + curSumA >= m) {
    171       ans = min(ans, 2 * r + l);
    172     }
    173     if (l != a.size()) {
    174       curSumA += a[l];
    175     }
    176   }
    177   cout << (ans == INT_MAX ? -1 : ans) << "\n";
    178 }
    179 
    180 int main() {
    181   int t;
    182   cin >> t;
    183   while (t--) {
    184     solve();
    185   }
    186 }
    187 ```
    188 
    189 [1475E - Advertising Agency](/contest/1475/problem/E "Codeforces Round 697 (Div. 3)")
    190 
    191 Problem authors: [Stepavly](/profile/Stepavly "Master Stepavly"), [Supermagzzz](/profile/Supermagzzz "Master Supermagzzz")
    192 
    193 **Editorial**
    194 
    195 Tutorial is loading...
    196 
    197 **Solution**
    198 
    199 ```
    200 #include <bits/stdc++.h>
    201 
    202 using namespace std;
    203 using ll = long long;
    204 using ld = long double;
    205 
    206 int mod = 1e9 + 7;
    207 
    208 int fast_pow(int a, int p) {
    209   int res = 1;
    210   while (p) {
    211     if (p % 2 == 0) {
    212       a = a * 1ll * a % mod;
    213       p /= 2;
    214     } else {
    215       res = res * 1ll * a % mod;
    216       p--;
    217     }
    218   }
    219   return res;
    220 }
    221 
    222 int fact(int n) {
    223   int res = 1;
    224   for (int i = 1; i <= n; i++) {
    225     res = res * 1ll * i % mod;
    226   }
    227   return res;
    228 }
    229 
    230 int C(int n, int k) {
    231   return fact(n) * 1ll * fast_pow(fact(k), mod - 2) % mod * 1ll * fast_pow(fact(n - k), mod - 2) % mod;
    232 }
    233 
    234 void solve() {
    235   int n, k;
    236   cin >> n >> k;
    237   vector<int> cnt(n + 1);
    238   for (int i = 0; i < n; i++) {
    239     int x;
    240     cin >> x;
    241     cnt[x]++;
    242   }
    243   for (int i = n; i >= 0; i--) {
    244     if (cnt[i] >= k) {
    245       cout << C(cnt[i], k) << "\n";
    246       return;
    247     } else {
    248       k -= cnt[i];
    249     }
    250   }
    251   cout << 1;
    252 }
    253 
    254 int main() {
    255   int t;
    256   cin >> t;
    257   while (t--) {
    258     solve();
    259   }
    260 }
    261 ```
    262 
    263 [1475F - Unusual Matrix](/contest/1475/problem/F "Codeforces Round 697 (Div. 3)")
    264 
    265 Problem authors: [Stepavly](/profile/Stepavly "Master Stepavly"), [Supermagzzz](/profile/Supermagzzz "Master Supermagzzz")
    266 
    267 **Editorial**
    268 
    269 Tutorial is loading...
    270 
    271 **Solution**
    272 
    273 ```
    274 #include <bits/stdc++.h>
    275 using namespace std;
    276 
    277 using pii = pair<int, int>;
    278 
    279 bool check(vector<vector<int>> a, vector<vector<int>> const &b) {
    280   int n = (int) a.size();
    281   for (int j = 0; j < n; j++) {
    282     if (a[0][j] != b[0][j]) {
    283       for (int i = 0; i < n; i++) {
    284         a[i][j] ^= 1;
    285       }
    286     }
    287   }
    288   for (int i = 0; i < n; i++) {
    289     int need_xor = (a[i][0] ^ b[i][0]);
    290     for (int j = 1; j < n; j++) {
    291       if (need_xor != (a[i][j] ^ b[i][j])) {
    292         return false;
    293       }
    294     }
    295   }
    296   return true;
    297 }
    298 
    299 void solve() {
    300   int n;
    301   cin >> n;
    302   vector<vector<int>> a(n, vector<int>(n));
    303   vector<vector<int>> b(n, vector<int>(n));
    304   for (int i = 0; i < n; i++) {
    305     string s;
    306     cin >> s;
    307     for (int j = 0; j < n; j++) {
    308       a[i][j] = s[j] - '0';
    309     }
    310   }
    311   for (int i = 0; i < n; i++) {
    312     string s;
    313     cin >> s;
    314     for (int j = 0; j < n; j++) {
    315       b[i][j] = s[j] - '0';
    316     }
    317   }
    318 
    319   for (int times = 0; times < 2; times++) {
    320     if (check(a, b)) {
    321       cout << "YES\n";
    322       return;
    323     }
    324     for (int j = 0; j < n; j++) {
    325       a[0][j] ^= 1;
    326     }
    327   }
    328   cout << "NO\n";
    329 }
    330 
    331 int main() {
    332   int test;
    333   cin >> test;
    334   while (test-- > 0) {
    335     solve();
    336   }
    337   return 0;
    338 }
    339 ```
    340 
    341 [1475G - Strange Beauty](/contest/1475/problem/G "Codeforces Round 697 (Div. 3)")
    342 
    343 Problem author: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov")
    344 
    345 **Editorial**
    346 
    347 Tutorial is loading...
    348 
    349 **Solution**
    350 
    351 ```
    352 #include <bits/stdc++.h>
    353 using namespace std;
    354 
    355 const int N = (int) 2e5 + 100;
    356 
    357 int dp[N];
    358 int cnt[N];
    359 
    360 void solve() {
    361   int n;
    362   cin >> n;
    363   fill(dp, dp + N, 0);
    364   fill(cnt, cnt + N, 0);
    365   for (int i = 0; i < n; i++) {
    366     int x;
    367     cin >> x;
    368     cnt[x]++;
    369   }
    370   for (int i = 1; i < N; i++) {
    371     dp[i] += cnt[i];
    372     for (int j = 2 * i; j < N; j += i) {
    373       dp[j] = max(dp[j], dp[i]);
    374     }
    375   }
    376   cout << (n - *max_element(dp, dp + N)) << endl;
    377 }
    378 
    379 int main() {
    380   int test;
    381   cin >> test;
    382   while (test-- > 0) {
    383     solve();
    384   }
    385   return 0;
    386 }
    387 ```