codeforces-scrape

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

1823.md (12278B)


      1 Source: https://codeforces.com/blog/entry/115465
      2 
      3 [1823A - A-characteristic](/contest/1823/problem/A "Codeforces Round 868 (Div. 2)")
      4 
      5 **Editorial**
      6 
      7 Tutorial is loading...
      8 
      9 **Solution C++**
     10 
     11 ```
     12 #include <bits/stdc++.h>
     13 
     14 using namespace std;
     15 
     16 int main() {
     17     int tt;
     18     cin >> tt;
     19     while (tt--) {
     20         int n, k, x = -1;
     21         cin >> n >> k;
     22         for (int i = 0; i <= n; i++) {
     23             if (i * (i - 1) / 2 + (n - i) * (n - i - 1) / 2 == k) {
     24                 x = i;
     25             }
     26         }
     27         if (x == -1)
     28             cout << "NO\n";
     29         else {
     30             cout << "YES\n";
     31             for (int i = 0; i < n; i++) {
     32                 if (i < x)
     33                     cout << 1 << ' ';
     34                 else
     35                     cout << -1 << ' ';
     36             }
     37             cout << '\n';
     38         }
     39     }
     40 
     41     return 0;
     42 }
     43 ```
     44 
     45 **Solution Python**
     46 
     47 ```
     48 for tt in range(int(input())):
     49     n, k = map(int, input().split())
     50     x = -1
     51 
     52     for i in range(0, n + 1):
     53         if i * (i - 1) / 2 + (n - i) * (n - i - 1) / 2 == k:
     54             x = i
     55 
     56     if x == -1:
     57         print("NO")
     58     else:
     59         print("YES")
     60         for i in range(0, n):
     61             if i < x:
     62                 print("1 ", end = '')
     63             else:
     64                 print("-1 ", end = '')
     65         print("")
     66 ```
     67 
     68 [1823B - Sort with Step](/contest/1823/problem/B "Codeforces Round 868 (Div. 2)")
     69 
     70 **Editorial**
     71 
     72 Tutorial is loading...
     73 
     74 **Solution C++**
     75 
     76 ```
     77 #include <bits/stdc++.h>
     78 
     79 using namespace std;
     80 
     81 int main() {
     82     int tt;
     83     cin >> tt;
     84     while (tt--) {
     85         int n, k;
     86         cin >> n >> k;
     87         vector <int> p(n);
     88         for (int i = 0; i < n; i++) {
     89             cin >> p[i];
     90             p[i]--;
     91         }
     92 
     93         int bad = 0;
     94         for (int i=0; i<n; i++) {
     95             if (p[i] % k != i % k) {
     96                 bad++;
     97             }
     98         }
     99 
    100         if(bad == 0)
    101             cout << 0 << '\n';
    102         else if(bad == 2)
    103             cout << 1 << '\n';
    104         else
    105             cout << -1 << '\n';
    106     }
    107 
    108     return 0;
    109 }
    110 ```
    111 
    112 **Solution Python**
    113 
    114 ```
    115 for tt in range(int(input())):
    116     n, k = map(int, input().split())
    117     p = list(map(int, input().split()))
    118     for i in range(0, n):
    119         p[i] -= 1
    120 
    121     bad = 0
    122     for i in range(0, n):
    123         if p[i] % k != i % k:
    124             bad += 1
    125 
    126     if bad == 0:
    127         print(0)
    128     elif bad == 2:
    129         print(1)
    130     else:
    131         print(-1)
    132 ```
    133 
    134 [1823C - Strongly Composite](/contest/1823/problem/C "Codeforces Round 868 (Div. 2)")
    135 
    136 **Editorial**
    137 
    138 Tutorial is loading...
    139 
    140 **Solution C++**
    141 
    142 ```
    143 #include <bits/stdc++.h>
    144 
    145 using namespace std;
    146 
    147 int main() {
    148     int tt;
    149     cin >> tt;
    150     while (tt--) {
    151         int n;
    152         cin >> n;
    153         map <int,int> a;
    154         for (int i = 0; i < n; i++) {
    155             int x;
    156             cin >> x;
    157             for (int j = 2; j * j <= x; j++) {
    158                 while (x % j == 0) {
    159                     x /= j;
    160                     a[j]++;
    161                 }
    162             }
    163             if (x != 1) {
    164                 a[x]++;
    165             }
    166         }
    167 
    168         int res = 0, rem = 0;
    169 
    170         for (pair <int, int> p : a) {
    171             int num = p.first;
    172             int cnt = p.second;
    173             res += cnt / 2;
    174             rem += cnt % 2;
    175         }
    176 
    177         res += rem / 3;
    178         cout << res << '\n';
    179     }
    180 
    181     return 0;
    182 }
    183 ```
    184 
    185 **Solution Python**
    186 
    187 ```
    188 def is_prime(x):
    189     i = 2
    190     while i * i <= x:
    191         if x % i == 0:
    192             return False
    193         i += 1
    194     return True
    195 
    196 def is_strongly_composite(x):
    197     m = []
    198     i = 2
    199     while i * i <= x:
    200         while x % i == 0:
    201             x = x // i
    202             m.append(i)
    203         i += 1
    204     if not x == 1:
    205         m.append(i)
    206     return (len(m) >= 3 or (len(m) == 2 and m[0] == m[1]))
    207 
    208 for tt in range(int(input())):
    209     n = int(input())
    210     lst = list(map(int, input().split()))
    211     a = {}
    212     for x in lst:
    213         i = 2
    214         while i * i <= x:
    215             while x % i == 0:
    216                 x = x // i
    217                 if i in a:
    218                     a[i] += 1
    219                 else:
    220                     a[i] = 1
    221             i += 1
    222         if x != 1:
    223             if x in a:
    224                 a[x] += 1
    225             else:
    226                 a[x] = 1
    227 
    228     res, rem = 0, 0
    229 
    230     for num in a:
    231         cnt = a[num]
    232         res += cnt // 2
    233         rem += cnt % 2
    234 
    235     res += rem // 3
    236     print(res)
    237 ```
    238 
    239 **Notes**
    240 
    241 There were initially more complex version of this task. Can you solve it?
    242 
    243 You are given $n$ integers $a_1, a_2, \dots, a_n$ ($a_i \gt 1$). You can perform the following operation with array $a$ any number of times:
    244 
    245 1. choose two indices $i$ and $j$ ($i \lt j$);
    246 2. erase elements $a_i$ and $a_j$ from $a$;
    247 3. insert element $a_i \cdot a_j$ in $a$.
    248 
    249 After performing one such operation, the length of $a$ decreases by one.
    250 
    251 Let's say that array $a$ is good, if it contains only strongly composite numbers.
    252 
    253 What is the minimum number of operation you need to perform to make array $a$ good?
    254 
    255 [1823D - Unique Palindromes](/contest/1823/problem/D "Codeforces Round 868 (Div. 2)")
    256 
    257 **Editorial**
    258 
    259 Tutorial is loading...
    260 
    261 **Solution C++**
    262 
    263 ```
    264 #include <bits/stdc++.h>
    265 
    266 using namespace std;
    267 
    268 int main() {
    269     int tt;
    270     cin >> tt;
    271     while (tt--) {
    272         int n, k;
    273         cin >> n >> k;
    274         vector <int> x(k), c(k);
    275         for (int i = 0; i < k; i++)
    276             cin >> x[i];
    277         for (int i = 0; i < k; i++)
    278             cin >> c[i];
    279 
    280         if (c[0] < 3 || c[0] > x[0]) {
    281             cout << "NO\n";
    282             continue;
    283         }
    284 
    285         string s;
    286 
    287         char cur = 'a';
    288         for (int i = 0; i < c[0] - 3; i++)
    289             s.push_back('a');
    290 
    291         for (int i = c[0] - 3; i < x[0]; i++) {
    292             s.push_back(cur);
    293             cur++;
    294             if (cur == 'd') cur = 'a';
    295         }
    296 
    297         bool good = true;
    298         for (int j = 1; j < k; j++) {
    299             int dx = x[j] - x[j - 1];
    300             int dc = c[j] - c[j - 1];
    301             if (dc > dx) {
    302                 good = false;
    303                 break;
    304             }
    305 
    306             for (int i = 0; i < dc; i++)
    307                 s.push_back('c' + j);
    308             for (int i = dc; i < dx; i++) {
    309                 s.push_back(cur);
    310                 cur++;
    311                 if (cur == 'd') cur = 'a';
    312             }
    313         }
    314 
    315         if (good)
    316             cout << "YES" << endl << s << endl;
    317         else
    318             cout << "NO" << endl;
    319     }
    320 
    321     return 0;
    322 }
    323 ```
    324 
    325 **Solution Python**
    326 
    327 ```
    328 for tt in range(int(input())):
    329     n, k = map(int, input().split())
    330     x = list(map(int, input().split()))
    331     c = list(map(int, input().split()))
    332 
    333     if c[0] < 3 or c[0] > x[0]:
    334         print("NO")
    335         continue
    336 
    337     s = ""
    338     cur = 'a'
    339 
    340     for i in range(0, c[0] - 3):
    341         s += "a"
    342 
    343     for i in range(c[0] - 3, x[0]):
    344         s += cur
    345         cur = chr(ord(cur) + 1)
    346         if cur == 'd':
    347             cur = 'a'
    348 
    349     good = True
    350     for j in range(1, k):
    351         dx = x[j] - x[j - 1]
    352         dc = c[j] - c[j - 1]
    353         if dc > dx:
    354             good = False
    355             break
    356 
    357         for i in range(0, dc):
    358             s += chr(ord('c') + j)
    359         for i in range(dc, dx):
    360             s += cur
    361             cur = chr(ord(cur) + 1)
    362             if cur == 'd':
    363                 cur = 'a'
    364 
    365     if good:
    366         print("YES")
    367         print(s)
    368     else:
    369         print("NO")
    370 ```
    371 
    372 **Notes**
    373 
    374 There were initially simpler version of this problem with $k = 1$, but it coincided with other problem.
    375 
    376 Also, how does checker in this problem works?
    377 
    378 [1823E - Removing Graph](/contest/1823/problem/E "Codeforces Round 868 (Div. 2)")
    379 
    380 **Editorial**
    381 
    382 Tutorial is loading...
    383 
    384 **Solution C++**
    385 
    386 ```
    387 #include <bits/stdc++.h>
    388 
    389 using namespace std;
    390 
    391 int main() {
    392     int n, l, r;
    393     cin >> n >> l >> r;
    394     vector < vector <int> > g(n);
    395     for (int i = 0; i < n; i++) {
    396         int a, b;
    397         cin >> a >> b;
    398         a--, b--;
    399         g[a].push_back(b);
    400         g[b].push_back(a);
    401     }
    402 
    403     int res=0, size;
    404     vector <int> used(n);
    405 
    406     function <void(int)> dfs = [&] (int v) {
    407         used[v] = true;
    408         size++;
    409         for (int to : g[v]) {
    410             if (!used[to])
    411                 dfs(to);
    412         }
    413     };
    414 
    415     for (int i = 0; i < n; i++) {
    416         if (!used[i]) {
    417             size = 0;
    418             dfs(i);
    419             if (size <= l + r - 1) {
    420                 res ^= size / l;
    421             }
    422         }
    423     }
    424 
    425     if (res)
    426         cout << "Alice\n";
    427     else
    428         cout << "Bob\n";
    429 
    430     return 0;
    431 }
    432 ```
    433 
    434 **Solution Python**
    435 
    436 ```
    437 from sys import setrecursionlimit
    438 import threading
    439 
    440 def main():
    441     n, l, r = map(int, input().split())
    442 
    443     g = [[] for i in range(0, n)]
    444     for i in range(0, n):
    445         a, b = map(int, input().split())
    446         a -= 1
    447         b -= 1
    448         g[a].append(b)
    449         g[b].append(a)
    450 
    451     res = 0
    452     used = [False for i in range(0, n)]
    453 
    454     def dfs(v):
    455         used[v] = True
    456         size = 1
    457         for to in g[v]:
    458             if not used[to]:
    459                 size += dfs(to)
    460         return size
    461 
    462     for i in range(0, n):
    463         if not used[i]:
    464             size = dfs(i)
    465             if size <= l + r - 1:
    466                 res ^= size // l
    467 
    468     if res:
    469         print("Alice")
    470     else:
    471         print("Bob")
    472 
    473 setrecursionlimit(10 ** 9)
    474 threading.stack_size(2 ** 27)
    475 thread = threading.Thread(target=main)
    476 thread.start()
    477 ```
    478 
    479 [1823F - Random Walk](/contest/1823/problem/F "Codeforces Round 868 (Div. 2)")
    480 
    481 **Editorial**
    482 
    483 Tutorial is loading...
    484 
    485 **Solution C++**
    486 
    487 ```
    488 #include <bits/stdc++.h>
    489  
    490 using namespace std;
    491  
    492 const int mod = 998244353;
    493  
    494 int main(){
    495     int n, s, t;
    496     cin >> n >> s >> t;
    497     s--, t--;
    498  
    499     vector < vector <int> > g(n);
    500     vector <int> previous(n, -1);
    501     vector <int> inPath(n);
    502     vector <long long> res(n);
    503  
    504     for (int i = 0; i < n - 1; i++) {
    505         int a, b;
    506         cin >> a >> b;
    507         a--, b--;
    508         g[a].push_back(b);
    509         g[b].push_back(a);
    510     }
    511  
    512     function <void (int, int)> dfs = [&] (int v, int p) {
    513         for (int to : g[v]) {
    514             if (to == p) continue;
    515             previous[to] = v;
    516             dfs(to, v);
    517         }
    518     };
    519  
    520     function <void (int, int, long long)> dfs2 = [&] (int v, int p, long long k) {
    521         res[v] = k * (long long)g[v].size();
    522         for (int to : g[v]) {
    523             if (to == p) continue;
    524             dfs2(to, v, k);
    525         }
    526     };
    527  
    528     dfs(s, -1);
    529  
    530     int ptr = t;
    531     inPath[t] = true;
    532  
    533     while (ptr != s) {
    534         res[previous[ptr]] = res[ptr] + 2;
    535         ptr = previous[ptr];
    536         inPath[ptr] = true;
    537     }
    538  
    539     for (int v = 0; v < n; v++) {
    540         if (inPath[v]) {
    541             res[v] = res[v] / 2 * (long long)g[v].size();
    542             for (int to : g[v]) {
    543                 if (!inPath[to]) {
    544                     dfs2(to, v, res[v] / (int)g[v].size());
    545                 }
    546             }
    547         }
    548     }
    549  
    550     res[t]++;
    551  
    552     for (long long i : res)
    553         cout << i % mod << ' ';
    554     cout<<'\n';
    555  
    556     return 0;
    557 }
    558 ```
    559 
    560 **Solution Python**
    561 
    562 ```
    563 from sys import setrecursionlimit
    564 import threading
    565  
    566 mod = 998244353
    567  
    568 def main():
    569     n, s, t = map(int, input().split())
    570     s -= 1
    571     t -= 1
    572     
    573     g = [[] for i in range(0, n)]
    574     previous = [-1 for i in range(0, n)]
    575     inPath = [False for i in range(0, n)]
    576     res = [0 for i in range(0, n)]
    577     
    578     for i in range(0, n - 1):
    579         a, b = map(int, input().split())
    580         a -= 1
    581         b -= 1
    582         g[a].append(b)
    583         g[b].append(a)
    584     
    585     def dfs(v, p):
    586         for to in g[v]:
    587             if to == p:
    588                 continue
    589             previous[to] = v
    590             dfs(to, v)
    591     
    592     def dfs2(v, p, k):
    593         res[v] = k * len(g[v])
    594         for to in g[v]:
    595             if to == p:
    596                 continue
    597             dfs2(to, v, k)
    598     
    599     dfs(s, -1)
    600     
    601     ptr = t
    602     inPath[t] = True
    603     
    604     while ptr != s:
    605         res[previous[ptr]] = res[ptr] + 2
    606         ptr = previous[ptr]
    607         inPath[ptr] = True
    608     
    609     for v in range(0, n):
    610         if inPath[v]:
    611             res[v] = res[v] // 2 * len(g[v])
    612             for to in g[v]:
    613                 if not inPath[to]:
    614                     dfs2(to, v, res[v] // len(g[v]))
    615     
    616     res[t] += 1
    617     
    618     for i in res:
    619         print(i % mod, end = ' ')
    620     print("")
    621  
    622 setrecursionlimit(10 ** 9)
    623 threading.stack_size(2 ** 27)
    624 thread = threading.Thread(target=main)
    625 thread.start()
    626 ```