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 ```