1065.md (9805B)
1 Source: https://codeforces.com/blog/entry/62411 2 3 [1065A - Vasya and Chocolate](/contest/1065/problem/A "Educational Codeforces Round 52 (Rated for Div. 2)") 4 5 **Tutorial** 6 7 Tutorial is loading... 8 9 **Solution (Ajosteen)** 10 11 ``` 12 #include <bits/stdc++.h> 13 14 using namespace std; 15 16 int main() { 17 int s, a, b, c; 18 int t; 19 cin >> t; 20 for(int i = 0; i < t; ++i){ 21 cin >> s >> a >> b >> c; 22 23 s /= c; 24 int x = s / a; 25 s %= a; 26 long long res = x * 1LL * (a + b); 27 res += s; 28 29 cout << res << endl; 30 } 31 return 0; 32 } 33 ``` 34 35 [1065B - Vasya and Isolated Vertices](/contest/1065/problem/B "Educational Codeforces Round 52 (Rated for Div. 2)") 36 37 **Tutorial** 38 39 Tutorial is loading... 40 41 **Solution (Ajosteen)** 42 43 ``` 44 #include <bits/stdc++.h> 45 46 using namespace std; 47 48 int main() { 49 int n; 50 long long m; 51 cin >> n >> m; 52 long long cur = 1; 53 long long rem = m; 54 while(rem > 0){ 55 long long d = min(cur, rem); 56 rem -= d; 57 ++cur; 58 } 59 assert(rem == 0); 60 61 long long res = n; 62 if(cur > 1) res = n - cur; 63 64 cout << max(0ll, n - m * 2) << ' ' << res << endl; 65 return 0; 66 } 67 ``` 68 69 [1065C - Make It Equal](/contest/1065/problem/C "Educational Codeforces Round 52 (Rated for Div. 2)") 70 71 **Tutorial** 72 73 Tutorial is loading... 74 75 **Solution (Ajosteen)** 76 77 ``` 78 #include <bits/stdc++.h> 79 80 using namespace std; 81 82 const int N = int(2e5) + 9; 83 84 int n, k, h; 85 int need = int(1e9); 86 int cnt[N]; 87 88 int main() { 89 scanf("%d %d", &n, &k); 90 for(int i = 0; i < n; ++i){ 91 int x; 92 scanf("%d", &x); 93 h = max(h, x); 94 need = min(need, x); 95 ++cnt[x]; 96 } 97 98 int pos = N - 1; 99 int res = 0; 100 long long sum = 0; 101 int c = 0; 102 while(true){ 103 long long x = sum - c * 1LL * (pos - 1); 104 if(x > k){ 105 ++res; 106 h = pos; 107 sum = pos * 1LL * c; 108 } 109 110 --pos; 111 if(pos == need) break; 112 c += cnt[pos]; 113 sum += cnt[pos] * 1LL * pos; 114 } 115 116 if(h != need) ++res; 117 118 cout << res << endl; 119 } 120 ``` 121 122 [1065D - Three Pieces](/contest/1065/problem/D "Educational Codeforces Round 52 (Rated for Div. 2)") 123 124 **Tutorial** 125 126 Tutorial is loading... 127 128 **Solution (PikMike)** 129 130 ``` 131 #include <bits/stdc++.h> 132 133 #define forn(i, n) for (int i = 0; i < int(n); i++) 134 #define mp make_pair 135 #define x first 136 #define y second 137 138 using namespace std; 139 140 typedef pair<int, int> pt; 141 142 const int N = 12; 143 const int M = 305; 144 const int INF = 1e9; 145 146 int n; 147 int a[N][N]; 148 pt pos[N * N]; 149 pt dist[M][M]; 150 151 pt operator +(const pt &a, const pt &b){ 152 return mp(a.x + b.x, a.y + b.y); 153 } 154 155 int dx[] = {-2, -1, 1, 2, 2, 1, -1, -2}; 156 int dy[] = { 1, 2, 2, 1, -1, -2, -2, -1}; 157 158 bool in(int x, int y){ 159 return (0 <= x && x < n && 0 <= y && y < n); 160 } 161 162 int get(int x, int y, int p){ 163 return x * n * 3 + y * 3 + p; 164 } 165 166 pt dp[N * N][3]; 167 168 int main() { 169 scanf("%d", &n); 170 forn(i, n) forn(j, n){ 171 scanf("%d", &a[i][j]); 172 --a[i][j]; 173 pos[a[i][j]] = mp(i, j); 174 } 175 176 forn(i, M) forn(j, M) dist[i][j] = mp(INF, INF); 177 forn(i, M) dist[i][i] = mp(0, 0); 178 179 forn(x, n) forn(y, n){ 180 forn(i, 8){ 181 int nx = x + dx[i]; 182 int ny = y + dy[i]; 183 if (in(nx, ny)) 184 dist[get(x, y, 0)][get(nx, ny, 0)] = mp(1, 0); 185 } 186 187 for (int i = -n + 1; i <= n - 1; ++i){ 188 int nx = x + i; 189 int ny = y + i; 190 if (in(nx, ny)) 191 dist[get(x, y, 1)][get(nx, ny, 1)] = mp(1, 0); 192 ny = y - i; 193 if (in(nx, ny)) 194 dist[get(x, y, 1)][get(nx, ny, 1)] = mp(1, 0); 195 } 196 197 forn(i, n){ 198 int nx = x; 199 int ny = i; 200 dist[get(x, y, 2)][get(nx, ny, 2)] = mp(1, 0); 201 nx = i; 202 ny = y; 203 dist[get(x, y, 2)][get(nx, ny, 2)] = mp(1, 0); 204 } 205 206 forn(i, 3) forn(j, 3){ 207 if (i != j){ 208 dist[get(x, y, i)][get(x, y, j)] = mp(1, 1); 209 } 210 } 211 } 212 213 forn(k, M) forn(i, M) forn(j, M) 214 dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]); 215 216 forn(i, N * N) forn(j, 3) dp[i][j] = mp(INF, INF); 217 dp[0][0] = dp[0][1] = dp[0][2] = mp(0, 0); 218 forn(i, n * n - 1) forn(j, 3) forn(k, 3) 219 dp[i + 1][k] = min(dp[i + 1][k], dp[i][j] + dist[get(pos[i].x, pos[i].y, j)][get(pos[i + 1].x, pos[i + 1].y, k)]); 220 221 pt ans = mp(INF, INF); 222 ans = min(ans, dp[n * n - 1][0]); 223 ans = min(ans, dp[n * n - 1][1]); 224 ans = min(ans, dp[n * n - 1][2]); 225 226 printf("%d %d\n", ans.x, ans.y); 227 return 0; 228 } 229 ``` 230 231 [1065E - Side Transmutations](/contest/1065/problem/E "Educational Codeforces Round 52 (Rated for Div. 2)") 232 233 **Tutorial** 234 235 Tutorial is loading... 236 237 **Solution (PikMike)** 238 239 ``` 240 #include <bits/stdc++.h> 241 242 #define forn(i, n) for (int i = 0; i < int(n); i++) 243 244 using namespace std; 245 246 const int N = 200 * 1000 + 13; 247 const int MOD = 998244353; 248 249 int n, m, A; 250 int b[N]; 251 252 int add(int a, int b){ 253 a += b; 254 if (a >= MOD) 255 a -= MOD; 256 return a; 257 } 258 259 int mul(int a, int b){ 260 return (a * 1ll * b) % MOD; 261 } 262 263 int binpow(int a, int b){ 264 int res = 1; 265 while (b){ 266 if (b & 1) 267 res = mul(res, a); 268 a = mul(a, a); 269 b >>= 1; 270 } 271 return res; 272 } 273 274 int cnt(int x){ 275 int base = binpow(A, x); 276 return mul(add(mul(base, base), base), (MOD + 1) / 2); 277 } 278 279 int main() { 280 scanf("%d%d%d", &n, &m, &A); 281 forn(i, m) 282 scanf("%d", &b[i]); 283 284 int ans = binpow(A, n - b[m - 1] * 2); 285 ans = mul(ans, cnt(b[0])); 286 forn(i, m - 1) 287 ans = mul(ans, cnt(b[i + 1] - b[i])); 288 289 printf("%d\n", ans); 290 return 0; 291 } 292 ``` 293 294 [1065F - Up and Down the Tree](/contest/1065/problem/F "Educational Codeforces Round 52 (Rated for Div. 2)") 295 296 **Tutorial** 297 298 Tutorial is loading... 299 300 **Solution (adedalic)** 301 302 ``` 303 #include<bits/stdc++.h> 304 305 using namespace std; 306 307 #define fore(i, l, r) for(int i = int(l); i < int(r); i++) 308 #define sz(a) int((a).size()) 309 310 #define x first 311 #define y second 312 313 typedef long long li; 314 typedef pair<int, int> pt; 315 316 template<class A, class B> ostream& operator <<(ostream& out, const pair<A, B> &p) { 317 return out << "(" << p.x << ", " << p.y << ")"; 318 } 319 320 template<class A> ostream& operator <<(ostream& out, const vector<A> &v) { 321 out << "["; 322 fore(i, 0, v.size()) { 323 if(i) out << ", "; 324 out << v[i]; 325 } 326 return out << "]"; 327 } 328 329 const int INF = int(1e9); 330 const li INF64 = li(1e18); 331 332 const int N = 1000 * 1000 + 555; 333 334 int n, k; 335 vector<int> g[N]; 336 337 inline bool read() { 338 if(!(cin >> n >> k)) 339 return false; 340 fore(i, 1, n) { 341 int p; assert(scanf("%d", &p) == 1); 342 p--; 343 344 g[p].push_back(i); 345 g[i].push_back(p); 346 } 347 return true; 348 } 349 350 int h[N]; 351 pt drev[N]; 352 353 void calcRev(int v, int p) { 354 drev[v] = pt(INF, 0); 355 for(int to : g[v]) { 356 if(to == p) continue; 357 358 h[to] = h[v] + 1; 359 calcRev(to, v); 360 361 if(drev[to].x <= h[v]) { 362 drev[v].x = min(drev[v].x, drev[to].x); 363 drev[v].y += drev[to].y; 364 } 365 } 366 367 if(p >= 0 && g[v].size() == 1) 368 drev[v] = pt(h[v] - k, 1); 369 } 370 371 int d[N]; 372 373 void calcAns(int v, int p) { 374 d[v] = (p >= 0 && g[v].size() == 1); 375 for(int to : g[v]) { 376 if(to == p) continue; 377 calcAns(to, v); 378 379 int tmp = drev[v].y; 380 if(drev[to].x <= h[v]) 381 tmp -= drev[to].y; 382 383 d[v] = max(d[v], tmp + d[to]); 384 } 385 } 386 387 inline void solve() { 388 h[0] = 0; 389 calcRev(0, -1); 390 calcAns(0, -1); 391 cout << d[0] << endl; 392 } 393 394 int main() { 395 #ifdef _DEBUG 396 freopen("input.txt", "r", stdin); 397 int tt = clock(); 398 #endif 399 cout << fixed << setprecision(15); 400 401 if(read()) { 402 solve(); 403 404 #ifdef _DEBUG 405 cerr << "TIME = " << clock() - tt << endl; 406 tt = clock(); 407 #endif 408 } 409 return 0; 410 } 411 ``` 412 413 [1065G - Fibonacci Suffix](/contest/1065/problem/G "Educational Codeforces Round 52 (Rated for Div. 2)") 414 415 **Tutorial** 416 417 Tutorial is loading... 418 419 **Solution (BledDest)** 420 421 ``` 422 #include <bits/stdc++.h> 423 424 using namespace std; 425 426 typedef long long li; 427 428 const li INF64 = li(1e18); 429 430 li add(li x, li y) 431 { 432 return min(x + y, INF64); 433 } 434 435 const int N = 243; 436 437 int A1[N][2]; 438 li A2[N][N]; 439 int A3[N][N]; 440 int n, m; 441 li k; 442 int z; 443 int p[N]; 444 445 void build(const string& s) 446 { 447 z = (int)(s.size()); 448 p[0] = 0; 449 for(int i = 1; i < z; i++) 450 { 451 int j = p[i - 1]; 452 while(j > 0 && s[j] != s[i]) 453 j = p[j - 1]; 454 if(s[j] == s[i]) 455 j++; 456 p[i] = j; 457 } 458 for(int i = 0; i <= z; i++) 459 for(int j = 0; j < 2; j++) 460 { 461 if(i < z && s[i] == char('0' + j)) 462 A1[i][j] = i + 1; 463 else if(i == 0) 464 A1[i][j] = 0; 465 else 466 A1[i][j] = A1[p[i - 1]][j]; 467 } 468 for(int i = 0; i <= z; i++) 469 for(int j = 0; j < 2; j++) 470 { 471 A3[i][j] = A1[i][j]; 472 A2[i][j] = (A3[i][j] == z ? 1 : 0); 473 } 474 for(int i = 2; i <= n; i++) 475 for(int j = 0; j <= z; j++) 476 { 477 A3[j][i] = A3[A3[j][i - 2]][i - 1]; 478 A2[j][i] = add(A2[j][i - 2], A2[A3[j][i - 2]][i - 1]); 479 } 480 } 481 482 int main() 483 { 484 cin >> n >> k >> m; 485 string cur = ""; 486 for(int i = 0; i < m; i++) 487 { 488 if(cur != "") build(cur); 489 li x = 0; 490 if(cur != "" && A3[0][n] == i) 491 x = 1; 492 if(k == 1 && x == 1) 493 break; 494 k -= x; 495 build(cur + '0'); 496 li x1 = A2[0][n]; 497 if(k > x1) 498 { 499 cur += '1'; 500 k -= x1; 501 } 502 else 503 cur += '0'; 504 } 505 cout << cur << endl; 506 return 0; 507 } 508 ```