codeforces-scrape

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

1462.md (6271B)


      1 Source: https://codeforces.com/blog/entry/85594
      2 
      3 All problems were created by [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov") and developed by me ([Stepavly](/profile/Stepavly "Master Stepavly")) and [Supermagzzz](/profile/Supermagzzz "Master Supermagzzz").
      4 
      5 [1462A - Favorite Sequence](/contest/1462/problem/A "Codeforces Round 690 (Div. 3)")
      6 
      7 **Editorial**
      8 
      9 Tutorial is loading...
     10 
     11 **Solution**
     12 
     13 ```
     14 #include <bits/stdc++.h>
     15 
     16 using namespace std;
     17 
     18 void solve() {
     19   int n;
     20   cin >> n;
     21   vector<int> v(n);
     22   for (int &e : v) {
     23     cin >> e;
     24   }
     25   int left = 0, right = n - 1;
     26   vector<int> ans(n);
     27   for (int i = 0; i < n; i++) {
     28     if (i % 2 == 0) {
     29       ans[i] = v[left++];
     30     } else {
     31       ans[i] = v[right--];
     32     }
     33   }
     34   for (int i : ans) {
     35     cout << i << " ";
     36   }
     37   cout << "\n";
     38 }
     39 
     40 int main() {
     41   int t;
     42   cin >> t;
     43   while (t--) {
     44     solve();
     45   }
     46 }
     47 ```
     48 
     49 [1462B - Last Year's Substring](/contest/1462/problem/B "Codeforces Round 690 (Div. 3)")
     50 
     51 **Editorial**
     52 
     53 Tutorial is loading...
     54 
     55 **Solution**
     56 
     57 ```
     58 #include <bits/stdc++.h>
     59 
     60 using namespace std;
     61 
     62 void solve() {
     63   int n;
     64   cin >> n;
     65   string s;
     66   cin >> s;
     67 
     68   for (int i = 0; i <= 4; i++) {
     69     if (s.substr(0, i) + s.substr(n - 4 + i, 4 - i) == "2020") {
     70       cout << "YES" << endl;
     71       return;
     72     }
     73   }
     74   cout << "NO" << endl;
     75 }
     76 
     77 int main() {
     78   int tests;
     79   cin >> tests;
     80   while (tests-- > 0) {
     81     solve();
     82   }
     83   return 0;
     84 }
     85 ```
     86 
     87 [1462C - Unique Number](/contest/1462/problem/C "Codeforces Round 690 (Div. 3)")
     88 
     89 **Editorial**
     90 
     91 Tutorial is loading...
     92 
     93 **Solution**
     94 
     95 ```
     96 #include <bits/stdc++.h>
     97 
     98 using namespace std;
     99 
    100 void solve() {
    101   int x;
    102   cin >> x;
    103   vector<int> ans;
    104   int sum = 0, last = 9;
    105   while (sum < x && last > 0) {
    106     ans.push_back(min(x - sum, last));
    107     sum += last;
    108     last--;
    109   }
    110   if (sum < x) {
    111     cout << -1 << "\n";
    112   } else {
    113     reverse(ans.begin(), ans.end());
    114     for (int i : ans) {
    115       cout << i;
    116     }
    117     cout << "\n";
    118   }
    119 }
    120 
    121 int main() {
    122   int t;
    123   cin >> t;
    124   while (t--) {
    125     solve();
    126   }
    127 }
    128 ```
    129 
    130 [1462D - Add to Neighbour and Remove](/contest/1462/problem/D "Codeforces Round 690 (Div. 3)")
    131 
    132 Problem authors: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov"), [Supermagzzz](/profile/Supermagzzz "Master Supermagzzz"), [Stepavly](/profile/Stepavly "Master Stepavly").
    133 
    134 **Editorial**
    135 
    136 Tutorial is loading...
    137 
    138 **Solution**
    139 
    140 ```
    141 #include <bits/stdc++.h>
    142 using namespace std;
    143 
    144 using ll = long long;
    145 
    146 void solve() {
    147   int n;
    148   cin >> n;
    149   vector<ll> a(n);
    150   ll sum = 0;
    151   for (ll &x : a) {
    152     cin >> x;
    153     sum += x;
    154   }
    155 
    156   for (int i = n; i >= 1; i--) {
    157     if (sum % i == 0) {
    158       ll needSum = sum / i;
    159       ll curSum = 0;
    160       bool ok = true;
    161       for (int j = 0; j < n; j++) {
    162         curSum += a[j];
    163         if (curSum > needSum) {
    164           ok = false;
    165           break;
    166         } else if (curSum == needSum) {
    167           curSum = 0;
    168         }
    169       }
    170 
    171       if (ok) {
    172         cout << n - i << endl;
    173         return;
    174       }
    175     }
    176   }
    177 }
    178 
    179 int main() {
    180   int tests;
    181   cin >> tests;
    182   while (tests-- > 0) {
    183     solve();
    184   }
    185   return 0;
    186 }
    187 ```
    188 
    189 [1462E1 - Close Tuples (easy version)](/contest/1462/problem/E1 "Codeforces Round 690 (Div. 3)")
    190 
    191 **Editorial**
    192 
    193 Tutorial is loading...
    194 
    195 **Solution**
    196 
    197 ```
    198 #include <bits/stdc++.h>
    199 
    200 using namespace std;
    201 using ll = long long;
    202 
    203 void solve() {
    204   int n;
    205   cin >> n;
    206   vector<ll> cnt(n + 1);
    207   for (int i = 0; i < n; i++) {
    208     int x;
    209     cin >> x;
    210     cnt[x]++;
    211   }
    212   ll ans = 0;
    213   for (int i = 2; i < n; i++) {
    214     ans += cnt[i - 1] * cnt[i] * cnt[i + 1];
    215   }
    216   for (int i = 1; i < n; i++) {
    217     ans += cnt[i] * (cnt[i] - 1) / 2 * cnt[i + 1];
    218   }
    219   for (int i = 2; i <= n; i++) {
    220     ans += cnt[i - 1] * cnt[i] * (cnt[i] - 1) / 2;
    221   }
    222   for (int i = 2; i < n; i++) {
    223     ans += cnt[i - 1] * cnt[i + 1] * (cnt[i + 1] - 1) / 2;
    224   }
    225   for (int i = 2; i < n; i++) {
    226     ans += cnt[i + 1] * cnt[i - 1] * (cnt[i - 1] - 1) / 2;
    227   }
    228   for (int i = 1; i <= n; i++) {
    229     ans += cnt[i] * (cnt[i] - 1) * (cnt[i] - 2) / 6;
    230   }
    231   cout << ans << "\n";
    232 }
    233 
    234 int main() {
    235   int t;
    236   cin >> t;
    237   while (t--) {
    238     solve();
    239   }
    240 }
    241 ```
    242 
    243 [1462E2 - Close Tuples (hard version)](/contest/1462/problem/E2 "Codeforces Round 690 (Div. 3)")
    244 
    245 **Editorial**
    246 
    247 Tutorial is loading...
    248 
    249 **Solution**
    250 
    251 ```
    252 #include <bits/stdc++.h>
    253 
    254 using namespace std;
    255 using ll = long long;
    256 
    257 const int N = 300500;
    258 const int mod = 1000000007;
    259 ll fact[N];
    260 ll invFact[N];
    261 
    262 ll fast_pow(ll a, ll p) {
    263     ll res = 1;
    264     while (p) {
    265         if (p % 2 == 0) {
    266             a = (a * a) % mod;
    267             p /= 2;
    268         } else {
    269             res = (res * a) % mod;
    270             p--;
    271         }
    272     }
    273     return res;
    274 }
    275 
    276 ll C(int n, int k) {
    277     if (k > n) {
    278         return 0;
    279     }
    280     return fact[n] * invFact[k] % mod * invFact[n - k] % mod;
    281 }
    282 
    283 void solve() {
    284     int n, m, k;
    285     cin >> n >> m >> k;
    286     vector<ll> v(n);
    287     for (ll &e : v) {
    288         cin >> e;
    289     }
    290     sort(v.begin(), v.end());
    291     ll ans = 0;
    292     for (int i = 0; i < n; i++) {
    293         int l = i + 1;
    294         int r = upper_bound(v.begin(), v.end(), v[i] + k) - v.begin();
    295         ans = (ans + C(r - l, m - 1)) % mod;
    296     }
    297     cout << ans << "\n";
    298 }
    299 
    300 int main() {
    301     fact[0] = invFact[0] = 1;
    302     for (int i = 1; i < N; i++) {
    303         fact[i] = (fact[i - 1] * i) % mod;
    304         invFact[i] = fast_pow(fact[i], mod - 2);
    305     }
    306     int t;
    307     cin >> t;
    308     while (t--) {
    309         solve();
    310     }
    311 }
    312 ```
    313 
    314 [1462F - The Treasure of The Segments](/contest/1462/problem/F "Codeforces Round 690 (Div. 3)")
    315 
    316 **Editorial**
    317 
    318 Tutorial is loading...
    319 
    320 **Solution**
    321 
    322 ```
    323 #include <bits/stdc++.h>
    324 
    325 using namespace std;
    326 using ll = long long;
    327 
    328 void solve() {
    329     vector<int> L;
    330     vector<int> R;
    331     int n;
    332     cin >> n;
    333     vector<pair<int, int>> v(n);
    334     for (auto &[l, r] : v) {
    335         cin >> l >> r;
    336         L.push_back(l);
    337         R.push_back(r);
    338     }
    339     sort(L.begin(), L.end());
    340     sort(R.begin(), R.end());
    341     int ans = n - 1;
    342     for (auto [l, r] : v) {
    343         int left = lower_bound(R.begin(), R.end(), l) - R.begin();
    344         int right = max(0, n - (int)(upper_bound(L.begin(), L.end(), r) - L.begin()));
    345         ans = min(ans, left + right);
    346     }
    347     cout << ans << "\n";
    348 }
    349 
    350 int main() {
    351     int t;
    352     cin >> t;
    353     while (t--) {
    354         solve();
    355     }
    356 }
    357 ```