codeforces-scrape

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

1931.md (7329B)


      1 Source: https://codeforces.com/blog/entry/125878
      2 
      3 [1931A - Recovering a Small String](/contest/1931/problem/A "Codeforces Round 925 (Div. 3)")
      4 
      5 Idea: [myav](/profile/myav "Pupil myav") Prepared by: [myav](/profile/myav "Pupil myav")
      6 
      7 **Tutorial**
      8 
      9 Tutorial is loading...
     10 
     11 **Solution**
     12 
     13 ```
     14 #include<bits/stdc++.h>
     15 using namespace std;
     16  
     17  
     18 void solve(){
     19     int n, sz = 26;
     20     cin >> n;
     21     string mins = "zzz", cur;
     22     for(int i = 0; i < sz; i++){
     23         for(int j = 0; j < sz; j++){
     24             for(int k = 0; k < sz; k++){
     25                 if(i + j + k + 3 == n){
     26                     cur += char(i + 'a');
     27                     cur += char(j + 'a');
     28                     cur += char(k + 'a');
     29                     mins = min(cur, mins);
     30                 }
     31             }
     32         }
     33     }
     34     cout << mins << "\n";
     35  
     36 }
     37 int main(){
     38     int t;
     39     cin >> t;
     40     while(t--) {
     41         solve();
     42     }
     43 }
     44 ```
     45 
     46 [1931B - Make Equal](/contest/1931/problem/B "Codeforces Round 925 (Div. 3)")
     47 
     48 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov") Prepared by: [Vladosiya](/profile/Vladosiya "Expert Vladosiya")
     49 
     50 **Tutorial**
     51 
     52 Tutorial is loading...
     53 
     54 **Solution**
     55 
     56 ```
     57 def solve():
     58     n = int(input())
     59     a = [int(x) for x in input().split()]
     60     k = sum(a) // n
     61     for i in range(n - 1):
     62         if a[i] < k:
     63             print('NO')
     64             return
     65         a[i + 1] += a[i] - k
     66         a[i] = k
     67     print('YES')
     68     
     69     
     70 for _ in range(int(input())):
     71     solve()
     72 ```
     73 
     74 [1931C - Make Equal Again](/contest/1931/problem/C "Codeforces Round 925 (Div. 3)")
     75 
     76 Idea: [ibraevdmitriy](/profile/ibraevdmitriy "Master ibraevdmitriy") Prepared by: [ibraevdmitriy](/profile/ibraevdmitriy "Master ibraevdmitriy")
     77 
     78 **Tutorial**
     79 
     80 Tutorial is loading...
     81 
     82 **Solution**
     83 
     84 ```
     85 def solve():
     86     n = int(input())
     87     a = list(map(int, input().split()))
     88     i1 = 0
     89     i2 = 0
     90     while i1 < n and a[i1] == a[0]:
     91         i1 += 1
     92     while i2 < n and a[n - i2 - 1] == a[n - 1]:
     93         i2 += 1
     94     res = n
     95     if a[0] == a[n - 1]:
     96         res -= i1
     97         res -= i2
     98     else:
     99         res -= max(i1, i2)
    100     print(max(0, res))
    101  
    102  
    103 t = int(input())
    104  
    105  
    106 for i in range(t):
    107     solve()
    108 ```
    109 
    110 [1931D - Divisible Pairs](/contest/1931/problem/D "Codeforces Round 925 (Div. 3)")
    111 
    112 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov") Prepared by: [Vladosiya](/profile/Vladosiya "Expert Vladosiya")
    113 
    114 **Tutorial**
    115 
    116 Tutorial is loading...
    117 
    118 **Solution**
    119 
    120 ```
    121 def solve():
    122     n, x, y = map(int, input().split())
    123     a = [int(x) for x in input().split()]
    124     cnt = dict()
    125     ans = 0
    126     for e in a:
    127         xx, yy = e % x, e % y
    128         ans += cnt.get(((x - xx) % x, yy), 0)
    129         cnt[(xx, yy)] = cnt.get((xx, yy), 0) + 1
    130     print(ans)
    131     
    132     
    133 for _ in range(int(input())):
    134     solve()
    135 ```
    136 
    137 [1931E - Anna and the Valentine's Day Gift](/contest/1931/problem/E "Codeforces Round 925 (Div. 3)")
    138 
    139 Idea: [Gornak40](/profile/Gornak40 "Expert Gornak40") Prepared by: [Gornak40](/profile/Gornak40 "Expert Gornak40")
    140 
    141 **Tutorial**
    142 
    143 Tutorial is loading...
    144 
    145 **Solution**
    146 
    147 ```
    148 #include <bits/stdc++.h>
    149  
    150 #define all(arr) arr.begin(), arr.end()
    151  
    152 using namespace std;
    153  
    154 const int MAXN = 200200;
    155  
    156 int n, m;
    157 string arr[MAXN];
    158 int len[MAXN], zrr[MAXN];
    159  
    160 void build() {
    161     memset(zrr, 0, sizeof(*zrr) * n);
    162     for (int i = 0; i < n; ++i) {
    163         len[i] = arr[i].size();
    164         for (auto it = arr[i].rbegin(); it != arr[i].rend() && *it == '0'; ++it) {
    165             ++zrr[i];
    166         }
    167     }
    168 }
    169  
    170 string solve() {
    171     int ans = 0;
    172     for (int i = 0; i < n; ++i) {
    173         ans += len[i] - zrr[i];
    174     }
    175     sort(zrr, zrr + n);
    176     reverse(zrr, zrr + n);
    177     for (int i = 0; i < n; ++i) {
    178         if (i & 1) ans += zrr[i];
    179     }
    180     return (ans - 1 >= m ? "Sasha" : "Anna");
    181 }
    182  
    183 int main() {
    184     int t; cin >> t;
    185     while (t--) {
    186         cin >> n >> m;
    187         for (int i = 0; i < n; ++i)
    188             cin >> arr[i];
    189         build();
    190         cout << solve() << '\n';
    191     }
    192 }
    193 ```
    194 
    195 [1931F - Chat Screenshots](/contest/1931/problem/F "Codeforces Round 925 (Div. 3)")
    196 
    197 Idea: [ibraevdmitriy](/profile/ibraevdmitriy "Master ibraevdmitriy") Prepared by: [ibraevdmitriy](/profile/ibraevdmitriy "Master ibraevdmitriy")
    198 
    199 **Tutorial**
    200 
    201 Tutorial is loading...
    202 
    203 **Solution**
    204 
    205 ```
    206 #include <iostream>
    207 #include <vector>
    208 #include <set>
    209 #include <queue>
    210 #include <algorithm>
    211  
    212 using namespace std;
    213  
    214 typedef long long ll;
    215  
    216 int timer = 0;
    217  
    218 void dfs(int v, vector<vector<int>> &g, vector<bool> &vis, vector<int> &tout) {
    219     vis[v] = true;
    220     for (int u: g[v]) {
    221         if (!vis[u]) {
    222             dfs(u, g, vis, tout);
    223         }
    224     }
    225     tout[v] = timer++;
    226 }
    227  
    228 void solve() {
    229     timer = 0;
    230     int n, k;
    231     cin >> n >> k;
    232     vector<vector<int>> a(k, vector<int>(n));
    233     vector<int> authors(k);
    234     for (int i = 0; i < k; ++i) {
    235         for (int j = 0; j < n; ++j) {
    236             cin >> a[i][j];
    237             a[i][j]--;
    238         }
    239         authors[i] = a[i][0];
    240     }
    241     vector<vector<int>> g(n);
    242     for (int i = 0; i < k; ++i) {
    243         for (int j = 1; j + 1 < n; ++j) {
    244             int i1 = a[i][j], i2 = a[i][j + 1];
    245             g[i1].push_back(i2);
    246         }
    247     }
    248     vector<int> tout(n, -1);
    249     vector<bool> vis(n);
    250     for (int i = 0; i < n; ++i) {
    251         if (tout[i] == -1) {
    252             dfs(i, g, vis, tout);
    253         }
    254     }
    255     for (int i = 0; i < k; ++i) {
    256         for (int j = 1; j + 1 < n; ++j) {
    257             int i1 = a[i][j], i2 = a[i][j + 1];
    258             if (tout[i1] < tout[i2]) {
    259                 cout << "NO";
    260                 return;
    261             }
    262         }
    263     }
    264     cout << "YES";
    265 }
    266  
    267 int main() {
    268     int t;
    269     cin >> t;
    270     for (int _ = 0; _ < t; ++_) {
    271         solve();
    272         cout << "\n";
    273     }
    274 }
    275 ```
    276 
    277 [1931G - One-Dimensional Puzzle](/contest/1931/problem/G "Codeforces Round 925 (Div. 3)")
    278 
    279 Idea: [ibraevdmitriy](/profile/ibraevdmitriy "Master ibraevdmitriy") Prepared by: [ibraevdmitriy](/profile/ibraevdmitriy "Master ibraevdmitriy")
    280 
    281 **Tutorial**
    282 
    283 Tutorial is loading...
    284 
    285 **Solution**
    286 
    287 ```
    288 #include <iostream>
    289 #include <vector>
    290 #include <set>
    291 #include <queue>
    292 #include <algorithm>
    293  
    294 using namespace std;
    295  
    296 typedef long long ll;
    297  
    298 const int mod = 998244353;
    299  
    300 ll pow_mod(ll x, ll p) {
    301     if (p == 0) {
    302         return 1;
    303     }
    304     if (p % 2 == 0) {
    305         ll y = pow_mod(x, p / 2);
    306         return (y * y) % mod;
    307     }
    308     return (x * pow_mod(x, p - 1)) % mod;
    309 }
    310  
    311 ll inv(ll x) {
    312     return pow_mod(x, mod - 2);
    313 }
    314  
    315 vector<ll> fact = {1};
    316  
    317 ll cnk(ll n, ll k) {
    318     ll res = fact[n];
    319     res = (res * inv(fact[k])) % mod;
    320     res = (res * inv(fact[n - k])) % mod;
    321     return res;
    322 }
    323  
    324 ll calc(int n1, int n2, int n3, int n4) {
    325     return (cnk(n1 + n3 - 1, n3) * cnk(n2 + n4 - 1, n4)) % mod;
    326 }
    327  
    328 void solve() {
    329     int n1, n2, n3, n4;
    330     cin >> n1 >> n2 >> n3 >> n4;
    331     if (n1 + n2 == 0) {
    332         cout << (n3 == 0 || n4 == 0 ? 1 : 0) << '\n';
    333         return;
    334     }
    335     if (abs(n1 - n2) > 1) {
    336         cout << "0\n";
    337         return;
    338     }
    339     ll res = 0;
    340     if (n1 <= n2) {
    341         res += calc(n1 + 1, n2, n3, n4);
    342     }
    343     if (n2 <= n1) {
    344         res += calc(n1, n2 + 1, n3, n4);
    345     }
    346     cout << res % mod << '\n';
    347 }
    348  
    349 int main() {
    350     for (ll i = 1; i <= 4e6; ++i) {
    351         fact.push_back((fact.back() * i) % mod);
    352     }
    353     int t;
    354     cin >> t;
    355     for (int _ = 0; _ < t; ++_) {
    356         solve();
    357     }
    358 }
    359 ```