codeforces-scrape

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

1671.md (11901B)


      1 Source: https://codeforces.com/blog/entry/102181
      2 
      3 [1671A - String Building](/contest/1671/problem/A "Educational Codeforces Round 127 (Rated for Div. 2)")
      4 
      5 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
      6 
      7 **Tutorial**
      8 
      9 Tutorial is loading...
     10 
     11 **Solution (BledDest)**
     12 
     13 ```
     14 t = int(input())
     15 for i in range(t):
     16     s = input()
     17     ans = True
     18     n = len(s)
     19     for j in range(n):
     20         if (j == 0 or s[j] != s[j - 1]) and (j == n - 1 or s[j] != s[j + 1]):
     21             ans = False
     22     print('YES' if ans else 'NO')
     23 ```
     24 
     25 [1671B - Consecutive Points Segment](/contest/1671/problem/B "Educational Codeforces Round 127 (Rated for Div. 2)")
     26 
     27 Idea: [vovuh](/profile/vovuh "Master vovuh")
     28 
     29 **Tutorial**
     30 
     31 Tutorial is loading...
     32 
     33 **Solution (vovuh)**
     34 
     35 ```
     36 for i in range(int(input())):
     37     n = int(input())
     38     x = list(map(int, input().split()))
     39     print('YES' if x[-1] - x[0] - n + 1 <= 2 else 'NO')
     40 ```
     41 
     42 [1671C - Dolce Vita](/contest/1671/problem/C "Educational Codeforces Round 127 (Rated for Div. 2)")
     43 
     44 Idea: [vovuh](/profile/vovuh "Master vovuh") and [BledDest](/profile/BledDest "International Grandmaster BledDest")
     45 
     46 **Tutorial**
     47 
     48 Tutorial is loading...
     49 
     50 **Solution (adedalic)**
     51 
     52 ```
     53 fun main() {
     54     repeat(readLine()!!.toInt()) {
     55         val (n, x) = readLine()!!.split(' ').map { it.toInt() }
     56         val a = readLine()!!.split(' ').map { it.toInt() }.sorted()
     57 
     58         var sum = a.sumOf { it.toLong() }
     59         var prevDay = -1L
     60         var ans = 0L
     61         for (i in n - 1 downTo 0) {
     62             val curDay = if (x - sum >= 0) (x - sum) / (i + 1) else -1
     63             ans += (i + 1) * (curDay - prevDay)
     64             prevDay = curDay
     65             sum -= a[i]
     66         }
     67         println(ans)
     68     }
     69 }
     70 ```
     71 
     72 [1671D - Insert a Progression](/contest/1671/problem/D "Educational Codeforces Round 127 (Rated for Div. 2)")
     73 
     74 Idea: [vovuh](/profile/vovuh "Master vovuh") and [BledDest](/profile/BledDest "International Grandmaster BledDest")
     75 
     76 **Tutorial**
     77 
     78 Tutorial is loading...
     79 
     80 **Solution (awoo)**
     81 
     82 ```
     83 #include <bits/stdc++.h>
     84 
     85 #define forn(i, n) for (int i = 0; i < int(n); i++)
     86 
     87 using namespace std;
     88 
     89 int main() {
     90     int t;
     91     scanf("%d", &t);
     92     forn(_, t){
     93         int n, x;
     94         scanf("%d%d", &n, &x);
     95         vector<int> a(n);
     96         forn(i, n) scanf("%d", &a[i]);
     97         long long ans = 1e18;
     98         long long cur = 0;
     99         forn(i, n - 1){
    100             cur += abs(a[i] - a[i + 1]);
    101         }
    102         forn(_, 2){
    103             long long mn = abs(a[0] - 1);
    104             ans = min(ans, cur + abs(a[0] - x) + (x - 1));
    105             forn(i, n - 1){
    106                 ans = min(ans, cur + mn - abs(a[i] - a[i + 1]) + abs(a[i] - x) + abs(a[i + 1] - x));
    107                 ans = min(ans, cur - abs(a[i] - a[i + 1]) + abs(a[i] - x) + abs(a[i + 1] - 1) + (x - 1));
    108                 mn = min(mn, 0ll - abs(a[i] - a[i + 1]) + abs(a[i] - 1) + abs(a[i + 1] - 1));
    109             }
    110             ans = min(ans, cur + mn + abs(a.back() - x));
    111             reverse(a.begin(), a.end());
    112         }
    113         printf("%lld\n", ans);
    114     }
    115     return 0;
    116 }
    117 ```
    118 
    119 [1671E - Preorder](/contest/1671/problem/E "Educational Codeforces Round 127 (Rated for Div. 2)")
    120 
    121 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
    122 
    123 **Tutorial**
    124 
    125 Tutorial is loading...
    126 
    127 **Solution (BledDest)**
    128 
    129 ```
    130 #include <bits/stdc++.h>
    131  
    132 using namespace std;
    133 
    134 mt19937 rnd(42);
    135 
    136 const int MOD = 998244353;
    137 const int K = 3;
    138 
    139 int add(int x, int y, int mod = MOD)
    140 {
    141     x += y;
    142     while(x >= mod) x -= mod;
    143     while(x < 0) x += mod;
    144     return x;
    145 }   
    146 
    147 int sub(int x, int y, int mod = MOD)
    148 {
    149     return add(x, -y, mod);
    150 }   
    151 
    152 int mul(int x, int y, int mod = MOD)
    153 {
    154     return (x * 1ll * y) % mod;
    155 }
    156 
    157 int binpow(int x, int y, int mod = MOD)
    158 {
    159     int z = 1;
    160     while(y > 0)
    161     {
    162         if(y % 2 == 1) z = mul(z, x, mod);
    163         y /= 2;
    164         x = mul(x, x, mod);
    165     }   
    166     return z;
    167 }
    168 
    169 bool prime(int x)
    170 {
    171     for(int i = 2; i * 1ll * i <= x; i++)
    172         if(x % i == 0)
    173             return false;
    174     return true;    
    175 }   
    176 
    177 int get_base()
    178 {
    179     int x = rnd() % 10000 + 4444;
    180     while(!prime(x)) x++;
    181     return x;
    182 }   
    183 
    184 int get_modulo()
    185 {
    186     int x = rnd() % int(1e9) + int(1e8);
    187     while(!prime(x)) x++;
    188     return x;
    189 }   
    190 
    191 typedef array<int, K> hs;
    192 
    193 hs base, modulo;
    194 
    195 void generate_hs()
    196 {
    197     for(int i = 0; i < K; i++)
    198     {
    199         base[i] = get_base();
    200         modulo[i] = get_modulo();
    201     }
    202 }   
    203 
    204 hs operator+(const hs& a, const hs& b)
    205 {
    206     hs c;
    207     for(int i = 0; i < K; i++)
    208     {
    209         c[i] = add(a[i], b[i], modulo[i]);    
    210     }
    211     return c;
    212 }
    213 
    214 hs operator-(const hs& a, const hs& b)
    215 {
    216     hs c;
    217     for(int i = 0; i < K; i++)
    218     {
    219         c[i] = sub(a[i], b[i], modulo[i]);    
    220     }
    221     return c;
    222 }
    223 
    224 hs operator*(const hs& a, const hs& b)
    225 {
    226     hs c;
    227     for(int i = 0; i < K; i++)
    228     {
    229         c[i] = mul(a[i], b[i], modulo[i]);    
    230     }
    231     return c;
    232 }
    233 
    234 hs operator^(const hs& a, const hs& b)
    235 {
    236     hs c; 
    237     for(int i = 0; i < K; i++)
    238     {
    239         c[i] = binpow(a[i], b[i], modulo[i]);    
    240     }
    241     return c;
    242 }
    243 
    244 hs char_hash(char c)
    245 {
    246     hs res;
    247     for(int i = 0; i < K; i++)
    248         res[i] = c - 'A' + 1;
    249     return res;
    250 }
    251 
    252 const int N = 18;
    253 const int V = 1 << N;
    254 string s;
    255 char buf[V + 43];
    256 int n;
    257 int ans[V + 43];
    258 hs vertex_hash[V + 43];
    259 
    260 bool is_leaf(int x)
    261 {
    262     return (x * 2 + 1) >= ((1 << n) - 1);
    263 }
    264 
    265 void rec(int x)
    266 {
    267     vertex_hash[x] = char_hash(s[x]);
    268     ans[x] = 1;
    269     if(is_leaf(x)) 
    270     {
    271         return;
    272     }
    273     rec(x * 2 + 1);
    274     rec(x * 2 + 2);
    275     vertex_hash[x] = vertex_hash[x] + (base ^ vertex_hash[2 * x + 1]) + (base ^ vertex_hash[2 * x + 2]);
    276     ans[x] = mul(ans[2 * x + 1], ans[2 * x + 2]);
    277     if(vertex_hash[2 * x + 1] != vertex_hash[2 * x + 2])
    278         ans[x] = mul(ans[x], 2);
    279 }
    280  
    281 int main() 
    282 {
    283     generate_hs();
    284     scanf("%d", &n);
    285     scanf("%s", buf);
    286     s = buf;
    287     rec(0);
    288     cout << ans[0] << endl;
    289 }
    290 ```
    291 
    292 [1671F - Permutation Counting](/contest/1671/problem/F "Educational Codeforces Round 127 (Rated for Div. 2)")
    293 
    294 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
    295 
    296 **Tutorial**
    297 
    298 Tutorial is loading...
    299 
    300 **Solution (BledDest)**
    301 
    302 ```
    303 #include <bits/stdc++.h>
    304  
    305 using namespace std;
    306 
    307 const int K = 13;
    308 const int MOD = 998244353;
    309 
    310 int n, k, x;
    311 
    312 int cnt[K][K][K];
    313 int dp[K][2 * K][K][K];
    314 
    315 int add(int x, int y)
    316 {
    317     x += y;
    318     while(x >= MOD) x -= MOD;
    319     while(x < 0) x += MOD;
    320     return x;
    321 }   
    322 
    323 int sub(int x, int y)
    324 {
    325     return add(x, -y);
    326 }   
    327 
    328 int mul(int x, int y)
    329 {
    330     return (x * 1ll * y) % MOD;
    331 }
    332 
    333 int binpow(int x, int y)
    334 {
    335     int z = 1;
    336     while(y > 0)
    337     {
    338         if(y % 2 == 1) z = mul(z, x);
    339         y /= 2;
    340         x = mul(x, x);
    341     }   
    342     return z;
    343 }
    344 
    345 void precalc()
    346 {
    347     cnt[2][1][1] = 1;
    348     cnt[3][1][2] = 2;
    349     cnt[3][2][3] = 1;
    350     cnt[4][1][3] = 3;
    351     cnt[4][1][4] = 1;
    352     cnt[4][2][3] = 1;
    353     cnt[4][2][4] = 4;
    354     cnt[4][2][5] = 3;
    355     cnt[4][3][6] = 1;
    356     cnt[5][1][4] = 4;
    357     cnt[5][1][5] = 2;
    358     cnt[5][1][6] = 2;
    359     cnt[5][2][4] = 4;
    360     cnt[5][2][5] = 12;
    361     cnt[5][2][6] = 12;
    362     cnt[5][2][7] = 9;
    363     cnt[5][2][8] = 3;
    364     cnt[5][3][5] = 2;
    365     cnt[5][3][6] = 4;
    366     cnt[5][3][7] = 6;
    367     cnt[5][3][8] = 6;
    368     cnt[5][3][9] = 4;
    369     cnt[5][4][10] = 1;
    370     cnt[6][1][5] = 5;
    371     cnt[6][1][6] = 3;
    372     cnt[6][1][7] = 4;
    373     cnt[6][1][8] = 3;
    374     cnt[6][1][9] = 1;
    375     cnt[6][2][5] = 10;
    376     cnt[6][2][6] = 28;
    377     cnt[6][2][7] = 35;
    378     cnt[6][2][8] = 35;
    379     cnt[6][2][9] = 30;
    380     cnt[6][2][10] = 17;
    381     cnt[6][2][11] = 8;
    382     cnt[6][3][5] = 1;
    383     cnt[6][3][6] = 13;
    384     cnt[6][3][7] = 29;
    385     cnt[6][3][8] = 41;
    386     cnt[6][3][9] = 44;
    387     cnt[6][3][10] = 45;
    388     cnt[6][3][11] = 30;
    389     cnt[6][4][7] = 1;
    390     cnt[6][4][8] = 4;
    391     cnt[6][4][9] = 7;
    392     cnt[6][4][10] = 7;
    393     cnt[6][4][11] = 11;
    394     cnt[7][1][6] = 6;
    395     cnt[7][1][7] = 4;
    396     cnt[7][1][8] = 6;
    397     cnt[7][1][9] = 6;
    398     cnt[7][1][10] = 6;
    399     cnt[7][1][11] = 2;
    400     cnt[7][2][6] = 20;
    401     cnt[7][2][7] = 55;
    402     cnt[7][2][8] = 80;
    403     cnt[7][2][9] = 95;
    404     cnt[7][2][10] = 101;
    405     cnt[7][2][11] = 94;
    406     cnt[7][3][6] = 6;
    407     cnt[7][3][7] = 50;
    408     cnt[7][3][8] = 118;
    409     cnt[7][3][9] = 186;
    410     cnt[7][3][10] = 230;
    411     cnt[7][3][11] = 260;
    412     cnt[7][4][7] = 3;
    413     cnt[7][4][8] = 18;
    414     cnt[7][4][9] = 48;
    415     cnt[7][4][10] = 85;
    416     cnt[7][4][11] = 113;
    417     cnt[7][5][10] = 2;
    418     cnt[7][5][11] = 4;
    419     cnt[8][1][7] = 7;
    420     cnt[8][1][8] = 5;
    421     cnt[8][1][9] = 8;
    422     cnt[8][1][10] = 9;
    423     cnt[8][1][11] = 11;
    424     cnt[8][2][7] = 35;
    425     cnt[8][2][8] = 96;
    426     cnt[8][2][9] = 155;
    427     cnt[8][2][10] = 207;
    428     cnt[8][2][11] = 250;
    429     cnt[8][3][7] = 21;
    430     cnt[8][3][8] = 145;
    431     cnt[8][3][9] = 358;
    432     cnt[8][3][10] = 616;
    433     cnt[8][3][11] = 859;
    434     cnt[8][4][7] = 1;
    435     cnt[8][4][8] = 26;
    436     cnt[8][4][9] = 124;
    437     cnt[8][4][10] = 313;
    438     cnt[8][4][11] = 567;
    439     cnt[8][5][9] = 3;
    440     cnt[8][5][10] = 16;
    441     cnt[8][5][11] = 53;
    442     cnt[9][1][8] = 8;
    443     cnt[9][1][9] = 6;
    444     cnt[9][1][10] = 10;
    445     cnt[9][1][11] = 12;
    446     cnt[9][2][8] = 56;
    447     cnt[9][2][9] = 154;
    448     cnt[9][2][10] = 268;
    449     cnt[9][2][11] = 389;
    450     cnt[9][3][8] = 56;
    451     cnt[9][3][9] = 350;
    452     cnt[9][3][10] = 898;
    453     cnt[9][3][11] = 1654;
    454     cnt[9][4][8] = 8;
    455     cnt[9][4][9] = 126;
    456     cnt[9][4][10] = 552;
    457     cnt[9][4][11] = 1404;
    458     cnt[9][5][9] = 4;
    459     cnt[9][5][10] = 48;
    460     cnt[9][5][11] = 204;
    461     cnt[9][6][11] = 1;
    462     cnt[10][1][9] = 9;
    463     cnt[10][1][10] = 7;
    464     cnt[10][1][11] = 12;
    465     cnt[10][2][9] = 84;
    466     cnt[10][2][10] = 232;
    467     cnt[10][2][11] = 427;
    468     cnt[10][3][9] = 126;
    469     cnt[10][3][10] = 742;
    470     cnt[10][3][11] = 1967;
    471     cnt[10][4][9] = 36;
    472     cnt[10][4][10] = 448;
    473     cnt[10][4][11] = 1887;
    474     cnt[10][5][9] = 1;
    475     cnt[10][5][10] = 43;
    476     cnt[10][5][11] = 357;
    477     cnt[10][6][11] = 6;
    478     cnt[11][1][10] = 10;
    479     cnt[11][1][11] = 8;
    480     cnt[11][2][10] = 120;
    481     cnt[11][2][11] = 333;
    482     cnt[11][3][10] = 252;
    483     cnt[11][3][11] = 1428;
    484     cnt[11][4][10] = 120;
    485     cnt[11][4][11] = 1302;
    486     cnt[11][5][10] = 10;
    487     cnt[11][5][11] = 252;
    488     cnt[11][6][11] = 5;
    489     cnt[12][1][11] = 11;
    490     cnt[12][2][11] = 165;
    491     cnt[12][3][11] = 462;
    492     cnt[12][4][11] = 330;
    493     cnt[12][5][11] = 55;
    494     cnt[12][6][11] = 1;    
    495 }
    496 
    497 int inv[K];
    498 
    499 int C(int n, int k)
    500 {
    501     if(n < 0 || n < k || k < 0) return 0;
    502     int res = 1;
    503     for(int i = n; i > n - k; i--)
    504         res = mul(res, i);
    505     for(int i = 1; i <= k; i++)
    506         res = mul(res, inv[i]);
    507     return res;
    508 }
    509 
    510 void prepare()
    511 {
    512     for(int i = 1; i < K; i++)
    513         inv[i] = binpow(i, MOD - 2);
    514     precalc();
    515     dp[0][0][0][0] = 1;
    516     for(int i = 0; i < K; i++)
    517         for(int j = 0; j < 2 * K; j++)
    518             for(int a = 0; a < K - 2; a++)
    519                 for(int b = 0; b < K - 2; b++)
    520                 {
    521                     if(dp[i][j][a][b] == 0) continue;
    522                     for(int add_cnt = 2; add_cnt < K; add_cnt++)
    523                         for(int add_desc = 1; add_desc <= K - 2; add_desc++)
    524                             for(int add_inv = 1; add_inv <= K - 2; add_inv++)
    525                             {
    526                                 if(j + add_cnt >= 2 * K || a + add_desc > K - 2 || b + add_inv > K - 2) continue;
    527                                 int& nw = dp[i + 1][j + add_cnt][a + add_desc][b + add_inv];
    528                                 nw = add(nw, mul(dp[i][j][a][b], cnt[add_cnt][add_desc][add_inv]));    
    529                             }
    530                 }       
    531 }
    532 
    533 void solve() 
    534 {
    535     scanf("%d %d %d", &n, &k, &x);
    536     if(k == 0 && x == 0)
    537     {
    538         puts("1");
    539         return;
    540     }
    541     int ans = 0;
    542     for(int i = 1; i < K; i++)
    543         for(int j = 1; j < 2 * K; j++)
    544             if(dp[i][j][x][k] != 0)
    545             {
    546                 ans = add(ans, mul(dp[i][j][x][k], C(n - j + i, i)));        
    547             }
    548     printf("%d\n", ans);
    549 }
    550 
    551 int main()
    552 {
    553     prepare();
    554     int t;
    555     scanf("%d", &t);
    556     for(int i = 0; i < t; i++)
    557         solve();
    558 }
    559 ```