codeforces-scrape

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

1312.md (10895B)


      1 Source: https://codeforces.com/blog/entry/74640
      2 
      3 [1312A - Two Regular Polygons](/contest/1312/problem/A "Educational Codeforces Round 83 (Rated for Div. 2)")
      4 
      5 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
      6 
      7 **Tutorial**
      8 
      9 Tutorial is loading...
     10 
     11 **Solution (vovuh)**
     12 
     13 ```
     14 for i in range(int(input())):
     15     n, m = map(int, input().split())
     16     print('YES' if n % m == 0 else 'NO')
     17 ```
     18 
     19 [1312B - Bogosort](/contest/1312/problem/B "Educational Codeforces Round 83 (Rated for Div. 2)")
     20 
     21 Idea: [Roms](/profile/Roms "Master Roms")
     22 
     23 **Tutorial**
     24 
     25 Tutorial is loading...
     26 
     27 **Solution (Roms)**
     28 
     29 ```
     30 for t in range(int(input())):
     31     n = input()
     32     print(*sorted(map(int, input().split()))[::-1])
     33 ```
     34 
     35 [1312C - Adding Powers](/contest/1312/problem/C "Educational Codeforces Round 83 (Rated for Div. 2)")
     36 
     37 Idea: [adedalic](/profile/adedalic "International Master adedalic")
     38 
     39 **Tutorial**
     40 
     41 Tutorial is loading...
     42 
     43 **Solution 1 (adedalic)**
     44 
     45 ```
     46 fun main() {
     47     val T = readLine()!!.toInt()
     48     testCases@for (tc in 1..T) {
     49         val (_, k) = readLine()!!.split(' ').map { it.toLong() }
     50         val a = readLine()!!.split(' ').map { it.toLong() }.toLongArray()
     51 
     52         var maxPower = 1L
     53         while (maxPower < 1e16.toLong())
     54             maxPower *= k
     55 
     56         while (maxPower > 0) {
     57             val positions = a.withIndex().filter { it.value >= maxPower }.map { it.index }
     58             if (positions.isNotEmpty()) {
     59                 if (positions.size > 1) {
     60                     println("NO")
     61                     continue@testCases
     62                 }
     63                 a[positions[0]] -= maxPower
     64             }
     65             maxPower /= k
     66         }
     67         if (a.max()!! > 0L) {
     68             println("NO")
     69             continue@testCases
     70         }
     71         println("YES")
     72     }
     73 }
     74 ```
     75 
     76 **Solution 2 (adedalic)**
     77 
     78 ```
     79 fun getMask(a: Long, k: Long): Long? {
     80     var (tmp, res) = listOf(a, 0L)
     81     var cnt = 0
     82     while (tmp > 0) {
     83         if (tmp % k > 1)
     84             return null
     85         res = res or ((tmp % k) shl cnt)
     86         tmp /= k
     87         cnt++
     88     }
     89     return res
     90 }
     91 
     92 fun main() {
     93     val T = readLine()!!.toInt()
     94     for (tc in 1..T) {
     95         val (n, k) = readLine()!!.split(' ').map { it.toLong() }
     96         val a = readLine()!!.split(' ').map { getMask(it.toLong(), k) }
     97         val b = a.filterNotNull()
     98         if (b.size < n) {
     99             println("NO")
    100             continue
    101         } else {
    102             val res = b.reduce { acc, l -> if (acc < 0 || (acc and l) > 0) -1 else acc or l }
    103             println(if (res < 0) "NO" else "YES")
    104         }
    105     }
    106 }
    107 ```
    108 
    109 [1312D - Count the Arrays](/contest/1312/problem/D "Educational Codeforces Round 83 (Rated for Div. 2)")
    110 
    111 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
    112 
    113 **Tutorial**
    114 
    115 Tutorial is loading...
    116 
    117 **Solution (BledDest)**
    118 
    119 ```
    120 #include <bits/stdc++.h>
    121 
    122 using namespace std;
    123 
    124 const int N = 200043;
    125 const int MOD = 998244353;
    126 
    127 int add(int x, int y)
    128 {
    129     x += y;
    130     while(x >= MOD) x -= MOD;
    131     while(x < 0) x += MOD;
    132     return x;
    133 }
    134 
    135 int mul(int x, int y)
    136 {
    137     return (x * 1ll * y) % MOD;
    138 }
    139 
    140 int binpow(int x, int y)
    141 {
    142     int z = 1;
    143     while(y)
    144     {
    145         if(y & 1) z = mul(z, x);
    146         x = mul(x, x);
    147         y >>= 1;
    148     }
    149     return z;
    150 }
    151 
    152 int inv(int x)
    153 {
    154     return binpow(x, MOD - 2);
    155 }
    156 
    157 int divide(int x, int y)
    158 {
    159     return mul(x, inv(y));
    160 }
    161 
    162 int fact[N];
    163 
    164 void precalc()
    165 {
    166     fact[0] = 1;
    167     for(int i = 1; i < N; i++)
    168         fact[i] = mul(fact[i - 1], i);
    169 }
    170 
    171 int C(int n, int k)
    172 {
    173     return divide(fact[n], mul(fact[k], fact[n - k]));
    174 }
    175 
    176 int main() 
    177 {
    178     precalc();
    179     int n, m;
    180     cin >> n >> m;
    181     int ans = 0;
    182     if(n > 2)
    183         ans = mul(C(m, n - 1), mul(n - 2, binpow(2, n - 3)));
    184     cout << ans << endl;
    185 }
    186 ```
    187 
    188 [1312E - Array Shrinking](/contest/1312/problem/E "Educational Codeforces Round 83 (Rated for Div. 2)")
    189 
    190 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov")
    191 
    192 **Tutorial**
    193 
    194 Tutorial is loading...
    195 
    196 **Solution (adedalic)**
    197 
    198 ```
    199 #include<bits/stdc++.h>
    200 
    201 using namespace std;
    202 
    203 #define fore(i, l, r) for(int i = int(l); i < int(r); i++)
    204 #define sz(a) int((a).size())
    205 
    206 #define x first
    207 #define y second
    208 
    209 typedef long long li;
    210 typedef long double ld;
    211 typedef pair<int, int> pt;
    212 
    213 template<class A, class B> ostream& operator <<(ostream& out, const pair<A, B> &p) {
    214     return out << "(" << p.x << ", " << p.y << ")";
    215 }
    216 template<class A> ostream& operator <<(ostream& out, const vector<A> &v) {
    217     out << "[";
    218     fore(i, 0, sz(v)) {
    219         if(i) out << ", ";
    220         out << v[i];
    221     }
    222     return out << "]";
    223 }
    224 
    225 const int INF = int(1e9);
    226 const li INF64 = li(1e18);
    227 const ld EPS = 1e-9;
    228 
    229 const int N = 555;
    230 int n, a[N];
    231 
    232 inline bool read() {
    233     if(!(cin >> n))
    234         return false;
    235     fore(i, 0, n)
    236         cin >> a[i];
    237     return true;
    238 }
    239 
    240 int dp[N][N];
    241 
    242 int calcDP(int l, int r) {
    243     assert(l < r);
    244     if(l + 1 == r)
    245         return dp[l][r] = a[l];
    246     if(dp[l][r] != 0)
    247         return dp[l][r];
    248     
    249     dp[l][r] = -1;
    250     fore(mid, l + 1, r) {
    251         int lf = calcDP(l, mid);
    252         int rg = calcDP(mid, r);
    253         if(lf > 0 && lf == rg)
    254             return dp[l][r] = lf + 1;
    255     }
    256     return dp[l][r];
    257 }
    258 
    259 int dp2[N];
    260 
    261 inline void solve() {
    262     fore(i, 0, N)
    263         dp2[i] = INF;
    264     
    265     dp2[0] = 0;
    266     fore(i, 0, n) {
    267         fore(j, i + 1, n + 1) {
    268             if(calcDP(i, j) > 0)
    269                 dp2[j] = min(dp2[j], dp2[i] + 1);
    270         }
    271     }
    272     cout << dp2[n] << endl;
    273 }
    274 
    275 int main() {
    276 #ifdef _DEBUG
    277     freopen("input.txt", "r", stdin);
    278     int tt = clock();
    279 #endif
    280     ios_base::sync_with_stdio(false);
    281     cin.tie(0), cout.tie(0);
    282     cout << fixed << setprecision(15);
    283     
    284     if(read()) {
    285         solve();
    286         
    287 #ifdef _DEBUG
    288         cerr << "TIME = " << clock() - tt << endl;
    289         tt = clock();
    290 #endif
    291     }
    292     return 0;
    293 }
    294 ```
    295 
    296 [1312F - Attack on Red Kingdom](/contest/1312/problem/F "Educational Codeforces Round 83 (Rated for Div. 2)")
    297 
    298 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
    299 
    300 **Tutorial**
    301 
    302 Tutorial is loading...
    303 
    304 **Solution (BledDest)**
    305 
    306 ```
    307 #include<bits/stdc++.h>
    308 
    309 using namespace std;
    310 
    311 const int N = 300043;
    312 const int K = 5;
    313 
    314 int x, y, z, n;
    315 long long a[N];
    316 
    317 typedef vector<vector<int> > state;
    318 map<state, int> d;
    319 int cnt;
    320 int p;
    321 vector<vector<int> > state_log;
    322 
    323 int mex(const vector<int>& a)
    324 {
    325     for(int i = 0; i < a.size(); i++)
    326     {
    327         bool f = false;
    328         for(auto x : a)
    329             if(x == i)
    330                 f = true;
    331         if(!f)
    332             return i;
    333     }
    334     return a.size();
    335 }
    336 
    337 state go(state s)
    338 {
    339     int f1 = mex({s[0][K - x], s[1][K - y], s[2][K - z]});
    340     int f2 = mex({s[0][K - x], s[2][K - z]});
    341     int f3 = mex({s[0][K - x], s[1][K - y]});
    342     state nw = s;
    343     nw[0].push_back(f1);
    344     nw[1].push_back(f2);
    345     nw[2].push_back(f3);
    346     for(int i = 0; i < 3; i++)
    347         nw[i].erase(nw[i].begin());
    348     return nw;
    349 }
    350 
    351 void precalc()
    352 {
    353     d.clear();
    354     state cur(3, vector<int>(K, 0));
    355     cnt = 0;
    356     state_log.clear();
    357     while(!d.count(cur))
    358     {
    359         d[cur] = cnt;
    360         state_log.push_back({cur[0].back(), cur[1].back(), cur[2].back()});
    361         cur = go(cur);
    362         cnt++;
    363     }                   
    364     p = cnt - d[cur];
    365 }
    366 
    367 int get_grundy(long long x, int t)
    368 {
    369     if(x < cnt)
    370         return state_log[x][t];
    371     else
    372     {
    373         int pp = cnt - p;
    374         x -= pp;
    375         return state_log[pp + (x % p)][t];
    376     }
    377 }
    378 
    379 void read()
    380 {
    381     scanf("%d %d %d %d", &n, &x, &y, &z);
    382     for(int i = 0; i < n; i++)
    383         scanf("%lld", &a[i]);
    384 }                    
    385 
    386 int check(int x, int y)
    387 {
    388     return x == y ? 1 : 0;
    389 }
    390 
    391 void solve()
    392 {
    393     precalc();
    394     int ans = 0;
    395     for(int i = 0; i < n; i++)
    396         ans ^= get_grundy(a[i], 0);
    397     int res = 0;
    398     for(int i = 0; i < n; i++)
    399     {
    400         ans ^= get_grundy(a[i], 0);
    401         res += check(ans, get_grundy(max(0ll, a[i] - x), 0));
    402         res += check(ans, get_grundy(max(0ll, a[i] - y), 1));
    403         res += check(ans, get_grundy(max(0ll, a[i] - z), 2));
    404         ans ^= get_grundy(a[i], 0);
    405     }
    406     printf("%d\n", res);
    407 }
    408 
    409 int main()
    410 {
    411     int t;
    412     scanf("%d", &t);
    413     for(int i = 0; i < t; i++)
    414     {
    415         read();
    416         solve();
    417     }
    418 }
    419 ```
    420 
    421 [1312G - Autocompletion](/contest/1312/problem/G "Educational Codeforces Round 83 (Rated for Div. 2)")
    422 
    423 Idea: [adedalic](/profile/adedalic "International Master adedalic") and [BledDest](/profile/BledDest "International Grandmaster BledDest")
    424 
    425 **Tutorial**
    426 
    427 Tutorial is loading...
    428 
    429 **Solution (BledDest)**
    430 
    431 ```
    432 #include<bits/stdc++.h>
    433 
    434 using namespace std;
    435 
    436 const int N = 1000043;
    437 
    438 map<char, int> nxt[N];
    439 bool term[N];
    440 int n, k;
    441 char buf[3];
    442 int dp[N];
    443 int dict[N];
    444 
    445 int T[4 * N];
    446 int f[4 * N];
    447 
    448 void build(int v, int l, int r)
    449 {
    450     T[v] = int(1e9);
    451     if(l != r - 1)
    452     {
    453         int m = (l + r) / 2;
    454         build(v * 2 + 1, l, m);
    455         build(v * 2 + 2, m, r);
    456     }
    457 }
    458 
    459 int getVal(int v)
    460 {
    461     return T[v] + f[v];
    462 }
    463 
    464 void push(int v, int l, int r)
    465 {
    466     T[v] += f[v];
    467     if(l != r - 1)
    468     {
    469         f[v * 2 + 1] += f[v];
    470         f[v * 2 + 2] += f[v];
    471     }
    472     f[v] = 0;
    473 }
    474 
    475 void upd(int v, int l, int r)
    476 {
    477     if(l != r - 1)
    478     {
    479         T[v] = min(getVal(v * 2 + 1), getVal(v * 2 + 2));
    480     }
    481 }
    482 
    483 int get(int v, int l, int r, int L, int R)
    484 {
    485     if(L >= R)
    486         return int(1e9);
    487     if(l == L && r == R)
    488         return getVal(v);
    489     push(v, l, r);
    490     int m = (l + r) / 2;
    491     int ans = min(get(v * 2 + 1, l, m, L, min(m, R)), get(v * 2 + 2, m, r, max(L, m), R));
    492     upd(v, l, r);
    493     return ans;
    494 }
    495 
    496 void add(int v, int l, int r, int L, int R, int val)
    497 {
    498     if(L >= R)
    499         return;
    500     if(l == L && r == R)
    501     {
    502         f[v] += val;
    503         return;
    504     }
    505     push(v, l, r);
    506     int m = (l + r) / 2;
    507     add(v * 2 + 1, l, m, L, min(m, R), val);
    508     add(v * 2 + 2, m, r, max(L, m), R, val);
    509     upd(v, l, r);
    510 }
    511 
    512 void setVal(int v, int l, int r, int pos, int val)
    513 {
    514     if(l == r - 1)
    515     {
    516         f[v] = 0;
    517         T[v] = val;
    518         return;
    519     }
    520     push(v, l, r);
    521     int m = (l + r) / 2;
    522     if(pos < m)
    523         setVal(v * 2 + 1, l, m, pos, val);
    524     else
    525         setVal(v * 2 + 2, m, r, pos, val);
    526     upd(v, l, r);
    527 }
    528 
    529 void dfs(int v, int d, int last)
    530 {
    531     dp[v] = last + 1;
    532     if(term[v])
    533         dp[v] = min(dp[v], get(0, 0, n + 1, 0, d));
    534     setVal(0, 0, n + 1, d, dp[v] + 1);
    535     if(term[v])
    536         add(0, 0, n + 1, 0, d + 1, 1);
    537     for(auto x : nxt[v])
    538         dfs(x.second, d + 1, dp[v]);
    539     setVal(0, 0, n + 1, d, int(1e9));
    540 }
    541 
    542 int main()
    543 {
    544     scanf("%d", &n);
    545     for(int i = 0; i < n; i++)
    546     {
    547         int p;
    548         scanf("%d %s", &p, buf);
    549         char c = buf[0];
    550         nxt[p][c] = i + 1;
    551     }
    552     scanf("%d", &k);
    553     for(int i = 0; i < k; i++)
    554     {
    555         scanf("%d", &dict[i]);
    556         term[dict[i]] = true;
    557     }
    558 
    559     build(0, 0, n + 1);
    560     dfs(0, 0, -1);
    561     for(int i = 0; i < k; i++)
    562         printf("%d ", dp[dict[i]]);
    563     puts("");
    564 }
    565 ```