codeforces-scrape

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

1811.md (9076B)


      1 Source: https://codeforces.com/blog/entry/114788
      2 
      3 [1811A - Insert Digit](/contest/1811/problem/A "Codeforces Round 863 (Div. 3)")
      4 
      5 Idea: [ibraevdmitriy](/profile/ibraevdmitriy "Master ibraevdmitriy"), prepared: [ibraevdmitriy](/profile/ibraevdmitriy "Master ibraevdmitriy")
      6 
      7 **Tutorial**
      8 
      9 Tutorial is loading...
     10 
     11 **Solution**
     12 
     13 ```
     14 #include <iostream>
     15 
     16 using namespace std;
     17 
     18 void solve() {
     19     int n, d;
     20     cin >> n >> d;
     21     string s;
     22     cin >> s;
     23     for (int i = 0; i < n; ++i) {
     24         if (s[i] - '0' >= d) {
     25             cout << s[i];
     26         } else {
     27             cout << d;
     28             for (int j = i; j < n; ++j) {
     29                 cout << s[j];
     30             }
     31             cout << '\n';
     32             return;
     33         }
     34     }
     35     cout << d << '\n';
     36 }
     37 
     38 int main() {
     39     int t;
     40     cin >> t;
     41     for (int _ = 0; _ < t; ++_) {
     42         solve();
     43     }
     44     return 0;
     45 }
     46 ```
     47 
     48 [1811B - Conveyor Belts](/contest/1811/problem/B "Codeforces Round 863 (Div. 3)")
     49 
     50 Idea: [Vladosiya](/profile/Vladosiya "Expert Vladosiya"), prepared: [ibraevdmitriy](/profile/ibraevdmitriy "Master ibraevdmitriy")
     51 
     52 **Tutorial**
     53 
     54 Tutorial is loading...
     55 
     56 **Solution**
     57 
     58 ```
     59 def layer(n, x, y):
     60     return min([x, y, n + 1 - x, n + 1 - y])
     61 
     62 def solve():
     63     n, x1, y1, x2, y2 = map(int, input().split())
     64     print(abs(layer(n, x1, y1) - layer(n, x2, y2)))
     65 
     66 t = int(input())
     67 for _ in range(t):
     68     solve()
     69 ```
     70 
     71 [1811C - Restore the Array](/contest/1811/problem/C "Codeforces Round 863 (Div. 3)")
     72 
     73 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov"), prepared: [myav](/profile/myav "Pupil myav")
     74 
     75 **Tutorial**
     76 
     77 Tutorial is loading...
     78 
     79 **Solution**
     80 
     81 ```
     82 #include "bits/stdc++.h"
     83 using namespace std;
     84 
     85 void solve(){
     86     int n;
     87     cin >> n;
     88     vector<int>b(n-1), a;
     89     for(int i = 0; i < n - 1; i++) cin >> b[i];
     90     a.emplace_back(b[0]);
     91     for(int i = 0; i < n - 2; i++){
     92         a.emplace_back(min(b[i], b[i + 1]));
     93     }
     94     a.emplace_back(b[n - 2]);
     95     for(auto &i : a) cout << i << ' ';
     96     cout << "\n";
     97 }
     98 int main(){
     99     int t;
    100     cin >> t;
    101     while(t--){
    102         solve();
    103     }
    104     return 0;
    105 }
    106 ```
    107 
    108 [1811D - Umka and a Long Flight](/contest/1811/problem/D "Codeforces Round 863 (Div. 3)")
    109 
    110 Idea: [Gornak40](/profile/Gornak40 "Expert Gornak40"), prepared: [Gornak40](/profile/Gornak40 "Expert Gornak40")
    111 
    112 **Tutorial**
    113 
    114 Tutorial is loading...
    115 
    116 **Solution**
    117 
    118 ```
    119 #include <bits/stdc++.h>
    120 
    121 using namespace std;
    122 
    123 const int MAXN = 50;
    124 
    125 int fib[MAXN];
    126 
    127 void build() {
    128 	fib[0] = fib[1] = 1;
    129 	for (int i = 2; i < MAXN; ++i)
    130 		fib[i] = fib[i - 2] + fib[i - 1];
    131 }
    132 
    133 bool solve(int n, int x, int y) {
    134 	if (n == 1) return true;
    135 	if (fib[n - 1] <= y && y < fib[n])
    136 		return false;
    137 	if (fib[n] <= y)
    138 		y -= fib[n];
    139 	return solve(n - 1, y, x);
    140 }
    141 
    142 int main() {
    143 	int t; cin >> t;
    144 	build();
    145 	while (t--) {
    146 		int n, x, y; cin >> n >> x >> y;
    147 		cout << (solve(n, --x, --y) ? "YES" : "NO") << '\n';
    148 	}
    149 }
    150 ```
    151 
    152 [1811E - Living Sequence](/contest/1811/problem/E "Codeforces Round 863 (Div. 3)")
    153 
    154 Idea: [Aris](/profile/Aris "Candidate Master Aris"), prepared: [Aris](/profile/Aris "Candidate Master Aris")
    155 
    156 **Tutorial**
    157 
    158 Tutorial is loading...
    159 
    160 **Solution**
    161 
    162 ```
    163 #include <iostream>
    164 #include <cmath>
    165 #include <cctype>
    166 #include <vector>
    167 #include <algorithm>
    168 #include <set>
    169 #include <map>
    170 #include <deque>
    171 #include <stack>
    172 #include <unordered_set>
    173 #include <sstream>
    174 #include <cstring>
    175 #include <iomanip>
    176 #include <queue>
    177 #include <unordered_map>
    178 #include <random>
    179 #include <cfloat>
    180 #include <chrono>
    181 #include <bitset>
    182 #include <complex>
    183 #include <immintrin.h>
    184 
    185 int main() {
    186     std::ios::sync_with_stdio(false);
    187     std::cin.tie(0);
    188 
    189     int32_t num_tests;
    190     std::cin >> num_tests;
    191 
    192     for(int32_t t = 0; t < num_tests; t++) {
    193         int64_t k;
    194         std::cin >> k;
    195 
    196         std::vector<int32_t> digits;
    197         while(k > 0) {
    198             digits.push_back(k % 9);
    199             k /= 9;
    200         }
    201         std::reverse(digits.begin(), digits.end());
    202 
    203         for(int32_t i = 0; i < digits.size(); i++)
    204             std::cout << (char)(digits[i] < 4 ? (digits[i] + '0') : (digits[i] + '1'));
    205         std::cout << "\n";
    206     }
    207     return 0;
    208 }
    209 ```
    210 
    211 [1811F - Is It Flower?](/contest/1811/problem/F "Codeforces Round 863 (Div. 3)")
    212 
    213 Idea: [Vladosiya](/profile/Vladosiya "Expert Vladosiya"), prepared: [Vladosiya](/profile/Vladosiya "Expert Vladosiya")
    214 
    215 **Tutorial**
    216 
    217 Tutorial is loading...
    218 
    219 **Solution**
    220 
    221 ```
    222 #include <bits/stdc++.h>
    223 
    224 using namespace std;
    225 
    226 int sz(int v, vector<vector<int>> &g, vector<bool> &used){
    227     used[v] = true;
    228     int s = 1;
    229     for(int u: g[v]){
    230         if(!used[u]) s += sz(u, g, used);
    231     }
    232     return s;
    233 }
    234 
    235 void remove(vector<int> &from, int x){
    236     for(int &e: from){
    237         if(e == x){
    238             swap(e, from.back());
    239             from.pop_back();
    240             return;
    241         }
    242     }
    243 }
    244 
    245 void solve(int tc) {
    246     int n, m;
    247     cin >> n >> m;
    248     vector<vector<int>> sl(n);
    249     for(int i = 0; i < m; ++i){
    250         int u, v;
    251         cin >> u >> v;
    252         sl[--u].emplace_back(--v);
    253         sl[v].emplace_back(u);
    254     }
    255     int k = sqrt(n);
    256     if(n != k * k || m != n + k){
    257         cout << "NO";
    258         return;
    259     }
    260     for(int i = 0; i < n; ++i){
    261         if(sl[i].size() != 2 && sl[i].size() != 4){
    262             cout << "NO";
    263             return;
    264         }
    265     }
    266     vector<bool> used(n);
    267     if(sz(0, sl, used) != n){
    268         cout << "NO";
    269         return;
    270     }
    271     for(int i = 0; i < n; ++i){
    272         if(sl[i].size() == 2) continue;
    273         for(int j = 0; j < sl[i].size();){
    274             int u = sl[i][j];
    275             if(sl[u].size() > 2){
    276                 remove(sl[i], u);
    277                 remove(sl[u], i);
    278             }
    279             else{
    280                 j++;
    281             }
    282         }
    283     }
    284     used = vector<bool>(n);
    285     for(int i = 0; i < n; ++i){
    286         if(!used[i] && sz(i, sl, used) != k){
    287             cout << "NO";
    288             return;
    289         }
    290     }
    291     cout << "YES";
    292 }
    293 
    294 bool multi = true;
    295 
    296 signed main() {
    297     cout.tie(nullptr);
    298     int t = 1;
    299     if (multi)cin >> t;
    300     for (int i = 1; i <= t; ++i) {
    301         solve(i);
    302         cout << "\n";
    303     }
    304     return 0;
    305 }
    306 ```
    307 
    308 [1811G1 - Vlad and the Nice Paths (easy version)](/contest/1811/problem/G1 "Codeforces Round 863 (Div. 3)")
    309 
    310 Idea: [Vladosiya](/profile/Vladosiya "Expert Vladosiya"), prepared: [Vladosiya](/profile/Vladosiya "Expert Vladosiya")
    311 
    312 **Tutorial**
    313 
    314 Tutorial is loading...
    315 
    316 **Solution**
    317 
    318 ```
    319 M = 10 ** 9 + 7
    320 
    321 def pw(a, n):
    322     if n == 0:
    323         return 1
    324     b = pw(a, n // 2)
    325     return b * b % M * (a if n % 2 == 1 else 1) % M
    326 
    327 def obr(x):
    328     return pw(x, M - 2)
    329 
    330 def cnk(n, k):
    331     return fact[n] * obr(fact[k]) % M * obr(fact[n - k]) % M
    332 
    333 def solve():
    334     n, k = map(int, input().split())
    335     c = [-1] + [int(x) for x in input().split()]
    336     if k == 1:
    337         print(1)
    338         return
    339     dp = [[0] * (n // k + 1) for i in range(n + 1)]  # dp[i][j] = number for i prefix with j blocks
    340     dp[0][0] = 1
    341     for i in range(1, n + 1):
    342         for j in range(0, n // k + 1):
    343             if j > 0:
    344                 sz = 1
    345                 for s in range(i - 1, - 1, -1):
    346                     if c[s] == c[i]:
    347                         sz += 1
    348                         if sz >= k:
    349                             dp[i][j] += dp[s - 1][j - 1] * cnk(sz - 2, k - 2) % M
    350                             dp[i][j] %= M
    351             dp[i][j] += dp[i - 1][j]
    352             dp[i][j] %= M
    353     for j in range(n // k, -1, -1):
    354         if dp[n][j] > 0:
    355             print(dp[n][j])
    356             return
    357 
    358 t = int(input())
    359 fact = [1] * 101
    360 for i in range(1, 101):
    361     fact[i] = fact[i - 1] * i % M
    362 for _ in range(t):
    363     solve()
    364 ```
    365 
    366 [1811G2 - Vlad and the Nice Paths (hard version)](/contest/1811/problem/G2 "Codeforces Round 863 (Div. 3)")
    367 
    368 Idea: [Vladosiya](/profile/Vladosiya "Expert Vladosiya"), prepared: [Vladosiya](/profile/Vladosiya "Expert Vladosiya")
    369 
    370 **Tutorial**
    371 
    372 Tutorial is loading...
    373 
    374 **Solution**
    375 
    376 ```
    377 from sys import stdin
    378 input = lambda: stdin.readline().strip()
    379 
    380 M = 10 ** 9 + 7
    381 cnk = [[0] * (5000 + 1) for i in range(5000 + 1)]
    382 
    383 def solve():
    384     n, k = map(int, input().split())
    385     c = [-1] + [int(x) for x in input().split()]
    386     if k == 1:
    387         print(1)
    388         return
    389     dp = [[0, 0] for i in range(n + 1)]  # dp[i] = [number, max] for i prefix
    390     dp[0][0] = 1
    391     for i in range(1, n + 1):
    392         sz = 1
    393         for s in range(i - 1, - 1, -1):
    394             if c[s] == c[i]:
    395                 sz += 1
    396                 if sz == k:
    397                     dp[i][1] = dp[s - 1][1] + 1
    398                 if sz >= k:
    399                     if dp[s - 1][1] < dp[i][1] - 1:
    400                         break
    401                     dp[i][0] += dp[s - 1][0] * cnk[sz - 2][k - 2] % M
    402                     dp[i][0] %= M
    403         if dp[i][1] < dp[i - 1][1]:
    404             dp[i] = [0, dp[i - 1][1]]
    405         if dp[i][1] == dp[i - 1][1]:
    406             dp[i][0] += dp[i - 1][0]
    407             dp[i][0] %= M
    408     print(dp[n][0])
    409 
    410 for i in range(5000 + 1):
    411     cnk[i][0] = 1
    412 for i in range(1, 5000 + 1):
    413     for j in range(1, i + 1):
    414         cnk[i][j] = (cnk[i - 1][j] + cnk[i - 1][j - 1]) % M
    415 
    416 t = int(input())
    417 for _ in range(t):
    418     solve()
    419 ```