1455.md (11299B)
1 Source: https://codeforces.com/blog/entry/85186 2 3 [1455A - Странные функции](/contest/1455/problem/A "Educational Codeforces Round 99 (рейтинговый для Див. 2)") 4 5 Idea: [BledDest](/profile/BledDest "Международный гроссмейстер BledDest") 6 7 **Tutorial** 8 9 Tutorial is loading... 10 11 **Solution (Ne0n25)** 12 13 ``` 14 for i in range(int(input())): 15 print(len(input())) 16 ``` 17 18 [1455B - Прыжки](/contest/1455/problem/B "Educational Codeforces Round 99 (рейтинговый для Див. 2)") 19 20 Idea: [adedalic](/profile/adedalic "Международный мастер adedalic") 21 22 **Tutorial** 23 24 Tutorial is loading... 25 26 **Solution (adedalic)** 27 28 ``` 29 #include<bits/stdc++.h> 30 31 using namespace std; 32 33 int main() { 34 int t; cin >> t; 35 while (t--) { 36 int x; cin >> x; 37 38 int steps = 0; 39 while (steps * (steps + 1) < 2 * x) 40 steps++; 41 42 if (steps * (steps + 1) / 2 == x + 1) 43 steps++; 44 cout << steps << endl; 45 } 46 } 47 ``` 48 49 [1455C - Пинг-понг](/contest/1455/problem/C "Educational Codeforces Round 99 (рейтинговый для Див. 2)") 50 51 Idea: [Neon](/profile/Neon "Кандидат в мастера Neon") 52 53 **Tutorial** 54 55 Tutorial is loading... 56 57 **Solution (Ne0n25)** 58 59 ``` 60 #include <bits/stdc++.h> 61 62 using namespace std; 63 64 void solve() { 65 int x, y; 66 cin >> x >> y; 67 cout << x - 1 << " " << y << endl; 68 } 69 70 int main() { 71 int t; 72 cin >> t; 73 while (t--) solve(); 74 } 75 ``` 76 77 [1455D - Последовательность и обмены](/contest/1455/problem/D "Educational Codeforces Round 99 (рейтинговый для Див. 2)") 78 79 Idea: [BledDest](/profile/BledDest "Международный гроссмейстер BledDest") 80 81 **Tutorial** 82 83 Tutorial is loading... 84 85 **Solution 1 (BledDest)** 86 87 ``` 88 #include<bits/stdc++.h> 89 90 using namespace std; 91 92 int main() 93 { 94 int t; 95 cin >> t; 96 for(int i = 0; i < t; i++) 97 { 98 int n, x; 99 cin >> n >> x; 100 vector<int> a(n); 101 for(int i = 0; i < n; i++) 102 cin >> a[i]; 103 if(is_sorted(a.begin(), a.end())) 104 { 105 cout << 0 << endl; 106 continue; 107 } 108 vector<vector<int>> dp(n, vector<int>(501, int(1e9))); 109 for(int i = 0; i < n; i++) 110 { 111 if(a[i] > x && (i == 0 || a[i - 1] <= x)) 112 dp[i][x] = 1; 113 if(i < n - 1 && a[i] > a[i + 1]) 114 break; 115 } 116 int ans = int(1e9); 117 for(int i = 0; i < n; i++) 118 for(int j = 0; j <= 500; j++) 119 { 120 if(dp[i][j] == int(1e9)) 121 continue; 122 if(i == n || (j <= a[i + 1] && is_sorted(a.begin() + i + 1, a.end()))) 123 ans = min(ans, dp[i][j]); 124 bool good = true; 125 for(int k = i + 1; k < n; k++) 126 { 127 int pr = k == i + 1 ? j : a[k - 1]; 128 if(good && a[i] >= pr && a[i] < a[k]) 129 dp[k][a[i]] = min(dp[k][a[i]], dp[i][j] + 1); 130 good &= a[k] >= pr; 131 } 132 } 133 if(ans == int(1e9)) 134 ans = -1; 135 cout << ans << endl; 136 137 } 138 } 139 ``` 140 141 **Solution 2 (adedalic)** 142 143 ``` 144 #include<bits/stdc++.h> 145 146 using namespace std; 147 148 #define fore(i, l, r) for(int i = int(l); i < int(r); i++) 149 #define sz(a) int((a).size()) 150 151 #define x first 152 #define y second 153 154 typedef long long li; 155 typedef long double ld; 156 typedef pair<int, int> pt; 157 158 template<class A, class B> ostream& operator <<(ostream& out, const pair<A, B> &p) { 159 return out << "(" << p.x << ", " << p.y << ")"; 160 } 161 template<class A> ostream& operator <<(ostream& out, const vector<A> &v) { 162 out << "["; 163 fore(i, 0, sz(v)) { 164 if(i) out << ", "; 165 out << v[i]; 166 } 167 return out << "]"; 168 } 169 170 const int INF = int(1e9); 171 const li INF64 = li(1e18); 172 const ld EPS = 1e-9; 173 174 int n, x; 175 vector<int> a; 176 177 inline bool read() { 178 if(!(cin >> n >> x)) 179 return false; 180 a.resize(n); 181 fore (i, 0, n) 182 cin >> a[i]; 183 return true; 184 } 185 186 inline void solve() { 187 vector<int> sf(n + 1, 0); 188 sf[n] = sf[n - 1] = 1; 189 for (int i = n - 2; i >= 0; i--) { 190 if (a[i] <= a[i + 1]) 191 sf[i] = sf[i + 1]; 192 } 193 194 int ans = 0; 195 int uk = 0; 196 while (true) { 197 int np = uk; 198 while (np < n && a[np] <= x) 199 np++; 200 fore (i, uk, np) { 201 if (i == 0) continue; 202 if (a[i - 1] > a[i]) { 203 cout << -1 << endl; 204 return; 205 } 206 } 207 if (sf[np]) 208 break; 209 210 assert(a[np] > x); 211 swap(a[np], x); 212 ans++; 213 uk = np; 214 } 215 cout << ans << endl; 216 } 217 218 int main() { 219 #ifdef _DEBUG 220 freopen("input.txt", "r", stdin); 221 int tt = clock(); 222 #endif 223 ios_base::sync_with_stdio(false); 224 cin.tie(0), cout.tie(0); 225 cout << fixed << setprecision(15); 226 227 int t; cin >> t; 228 229 while(t--) { 230 read(); 231 solve(); 232 233 #ifdef _DEBUG 234 cerr << "TIME = " << clock() - tt << endl; 235 tt = clock(); 236 #endif 237 } 238 return 0; 239 } 240 ``` 241 242 [1455E - Четыре точки](/contest/1455/problem/E "Educational Codeforces Round 99 (рейтинговый для Див. 2)") 243 244 Idea: [adedalic](/profile/adedalic "Международный мастер adedalic") 245 246 **Tutorial** 247 248 Tutorial is loading... 249 250 **Solution 1 (adedalic)** 251 252 ``` 253 #include<bits/stdc++.h> 254 255 using namespace std; 256 257 #define fore(i, l, r) for(int i = int(l); i < int(r); i++) 258 #define sz(a) int((a).size()) 259 260 #define x first 261 #define y second 262 263 typedef long long li; 264 typedef pair<li, li> pt; 265 266 const li INF64 = li(1e18); 267 268 pt p[4]; 269 270 inline bool read() { 271 fore (i, 0, 4) { 272 if(!(cin >> p[i].x >> p[i].y)) 273 return false; 274 } 275 return true; 276 } 277 278 inline void solve() { 279 li ans = INF64; 280 fore (st, 0, 2) { 281 fore (idx1, 0, 4) fore (idx2, 0, 4) fore (idy1, 0, 4) { 282 li x1 = p[idx1].x; 283 li x2 = p[idx2].x; 284 li y1 = p[idy1].y; 285 286 if (x1 > x2) 287 continue; 288 289 for (int k = -1; k <= 1; k += 2) { 290 li y2 = y1 + k * abs(x1 - x2); 291 292 vector<pt> fp = { {x1, y1}, {x2, y1}, {x2, y2}, {x1, y2} }; 293 sort(fp.begin(), fp.end()); 294 295 do { 296 li cur = 0; 297 fore (i, 0, 4) 298 cur += abs(fp[i].x - p[i].x) + abs(fp[i].y - p[i].y); 299 300 ans = min(ans, cur); 301 } while(next_permutation(fp.begin(), fp.end())); 302 } 303 } 304 305 fore (i, 0, 4) 306 swap(p[i].x, p[i].y); 307 } 308 cout << ans << endl; 309 } 310 311 int main() { 312 #ifdef _DEBUG 313 freopen("input.txt", "r", stdin); 314 int tt = clock(); 315 #endif 316 ios_base::sync_with_stdio(false); 317 cin.tie(0), cout.tie(0); 318 cout << fixed << setprecision(15); 319 320 int t; 321 cin >> t; 322 323 while(t--) { 324 assert(read()); 325 solve(); 326 327 #ifdef _DEBUG 328 cerr << "TIME = " << clock() - tt << endl; 329 tt = clock(); 330 #endif 331 } 332 return 0; 333 } 334 ``` 335 336 **Solution 2 (adedalic)** 337 338 ``` 339 #include<bits/stdc++.h> 340 341 using namespace std; 342 343 #define fore(i, l, r) for(int i = int(l); i < int(r); i++) 344 #define sz(a) int((a).size()) 345 346 #define x first 347 #define y second 348 349 typedef long long li; 350 typedef pair<li, li> pt; 351 352 const li INF64 = li(1e18); 353 354 pt p[4]; 355 356 inline bool read() { 357 fore (i, 0, 4) { 358 if(!(cin >> p[i].x >> p[i].y)) 359 return false; 360 } 361 return true; 362 } 363 364 li len(const pt &a) { 365 assert(a.y >= a.x); 366 return a.y - a.x; 367 } 368 pt getSeg(li a, li b) { 369 return { min(a, b), max(a, b) }; 370 } 371 pt getOpt(const pt &a, const pt &b) { 372 return { 373 max({ a.x - b.y, b.x - a.y, 0LL }), 374 max({ b.y - a.x, a.y - b.x, 0LL }) 375 }; 376 } 377 378 inline void solve() { 379 li ans = INF64; 380 381 vector<int> id = { 0, 1, 2, 3 }; 382 do { 383 li cur = 0; 384 auto x1 = getSeg(p[id[0]].x, p[id[3]].x); 385 auto x2 = getSeg(p[id[1]].x, p[id[2]].x); 386 387 cur += len(x1) + len(x2); 388 pt xSeg = getOpt(x1, x2); 389 390 auto y1 = getSeg(p[id[0]].y, p[id[1]].y); 391 auto y2 = getSeg(p[id[2]].y, p[id[3]].y); 392 393 cur += len(y1) + len(y2); 394 pt ySeg = getOpt(y1, y2); 395 396 li is = min(xSeg.y, ySeg.y) - max(xSeg.x, ySeg.x); 397 cur += 2 * max(0LL, -is); 398 399 ans = min(ans, cur); 400 } 401 while (next_permutation(id.begin(), id.end())); 402 403 cout << ans << endl; 404 } 405 406 int main() { 407 #ifdef _DEBUG 408 freopen("input.txt", "r", stdin); 409 int tt = clock(); 410 #endif 411 ios_base::sync_with_stdio(false); 412 cin.tie(0), cout.tie(0); 413 cout << fixed << setprecision(15); 414 415 int t; 416 cin >> t; 417 418 while(t--) { 419 assert(read()); 420 solve(); 421 422 #ifdef _DEBUG 423 cerr << "TIME = " << clock() - tt << endl; 424 tt = clock(); 425 #endif 426 } 427 return 0; 428 } 429 ``` 430 431 [1455F - Строка и операции](/contest/1455/problem/F "Educational Codeforces Round 99 (рейтинговый для Див. 2)") 432 433 Idea: [Neon](/profile/Neon "Кандидат в мастера Neon") 434 435 **Tutorial** 436 437 Tutorial is loading... 438 439 **Solution (Ne0n25)** 440 441 ``` 442 #include <bits/stdc++.h> 443 444 using namespace std; 445 446 const int N = 505; 447 448 int n, k; 449 string s; 450 string dp[N]; 451 452 void solve() { 453 cin >> n >> k >> s; 454 for (int i = 1; i <= n; i++) 455 dp[i] = char('z' + 1); 456 for (int i = 0; i < n; i++) { 457 int c = s[i] - 'a'; 458 int nc = min({c, (c + 1) % k, (c + k - 1) % k}); 459 dp[i + 1] = min(dp[i + 1], dp[i] + char('a' + nc)); 460 if (i > 0) { 461 dp[i + 1] = min(dp[i + 1], dp[i - 1] + char('a' + nc) + s[i - 1]); 462 dp[i + 1] = min(dp[i + 1], dp[i].substr(0, i - 1) + s[i] + dp[i].back()); 463 } 464 if (i > 1) { 465 dp[i + 1] = min(dp[i + 1], dp[i - 1].substr(0, i - 2) + s[i] + dp[i - 1].back() + s[i - 1]); 466 } 467 } 468 cout << dp[n] << endl; 469 } 470 471 int main() { 472 int t; 473 cin >> t; 474 while (t--) solve(); 475 } 476 ``` 477 478 [1455G - Запрещенное значение](/contest/1455/problem/G "Educational Codeforces Round 99 (рейтинговый для Див. 2)") 479 480 Idea: [MrPaul_TUser](/profile/MrPaul_TUser "Кандидат в мастера MrPaul_TUser") и [BledDest](/profile/BledDest "Международный гроссмейстер BledDest") 481 482 **Tutorial** 483 484 Tutorial is loading... 485 486 **Solution (pikmike)** 487 488 ``` 489 #include <bits/stdc++.h> 490 491 #define forn(i, n) for (int i = 0; i < int(n); i++) 492 #define x first 493 #define y second 494 495 using namespace std; 496 497 const long long INF = 1e18; 498 499 struct op{ 500 string tp; 501 int y, v, to; 502 }; 503 504 struct addmap{ 505 long long add; 506 map<int, long long> val; 507 multiset<long long> mn; 508 }; 509 510 void reset(addmap &a, int x, long long val){ 511 if (a.val.count(x)) 512 a.mn.erase(a.mn.find(a.val[x])); 513 a.val[x] = val - a.add; 514 a.mn.insert(val - a.add); 515 } 516 517 int main() { 518 int n, s; 519 scanf("%d%d", &n, &s); 520 static char buf[10]; 521 op a; 522 vector<addmap> st; 523 st.push_back({}); 524 st.back().val[0] = 0; 525 st.back().add = 0; 526 st.back().mn.insert(0); 527 forn(i, n){ 528 scanf("%s", buf); 529 a.tp = buf; 530 if (a.tp == "set"){ 531 scanf("%d%d", &a.y, &a.v); 532 assert(!st.back().mn.empty()); 533 long long mn = st.back().add + *st.back().mn.begin(); 534 st.back().add += a.v; 535 if (a.y != s) reset(st.back(), a.y, mn); 536 } 537 else if (a.tp == "if"){ 538 scanf("%d", &a.y); 539 long long val = INF; 540 if (st.back().val.count(a.y)){ 541 val = st.back().val[a.y] + st.back().add; 542 st.back().mn.erase(st.back().mn.find(st.back().val[a.y])); 543 st.back().val.erase(a.y); 544 } 545 st.push_back({}); 546 reset(st.back(), a.y, val); 547 st.back().add = 0; 548 } 549 else{ 550 if (st[int(st.size()) - 1].val.size() > st[int(st.size()) - 2].val.size()) 551 swap(st[int(st.size()) - 1], st[int(st.size()) - 2]); 552 addmap& v = st[int(st.size()) - 2]; 553 for (auto it : st.back().val){ 554 if (!v.val.count(it.x) || v.val[it.x] + v.add > it.y + st.back().add){ 555 if (v.val.count(it.x)) 556 v.mn.erase(v.mn.find(v.val[it.x])); 557 v.val[it.x] = it.y + st.back().add - v.add; 558 v.mn.insert(it.y + st.back().add - v.add); 559 } 560 } 561 st.pop_back(); 562 } 563 } 564 printf("%lld\n", *st.back().mn.begin() + st.back().add); 565 return 0; 566 } 567 ```