1873.md (8025B)
1 Source: https://codeforces.com/blog/entry/120634 2 3 Thank you for participating! 4 5 [1873A - Short Sort](/contest/1873/problem/A "Codeforces Round 898 (Div. 4)") 6 7 Idea: [flamestorm](/profile/flamestorm "Candidate Master flamestorm") 8 9 **Tutorial** 10 11 Tutorial is loading... 12 13 **Solution** 14 15 ``` 16 #include <bits/stdc++.h> 17 18 using namespace std; 19 20 const int MAX = 200007; 21 const int MOD = 1000000007; 22 23 string alph = "abc"; 24 25 void solve() { 26 string s; 27 cin >> s; 28 int cnt = 0; 29 for (int i = 0; i < 3; i++) { 30 cnt += (s[i] != alph[i]); 31 } 32 cout << (cnt <= 2 ? "YES\n" : "NO\n"); 33 } 34 35 int main() { 36 ios::sync_with_stdio(false); 37 cin.tie(nullptr); 38 int tt; cin >> tt; for (int i = 1; i <= tt; i++) {solve();} 39 // solve(); 40 } 41 ``` 42 43 [1873B - Good Kid](/contest/1873/problem/B "Codeforces Round 898 (Div. 4)") 44 45 Idea: [mesanu](/profile/mesanu "Candidate Master mesanu") 46 47 **Tutorial** 48 49 Tutorial is loading... 50 51 **Solution** 52 53 ``` 54 #include <bits/stdc++.h> 55 using namespace std; 56 57 void solve() 58 { 59 int n; 60 cin >> n; 61 vector<int> a(n); 62 int ans = 1; 63 for(int i = 0; i < n; i++) 64 { 65 cin >> a[i]; 66 } 67 sort(a.begin(), a.end()); 68 a[0]++; 69 for(int i = 0; i < n; i++) 70 { 71 ans*=a[i]; 72 } 73 cout << ans << endl; 74 } 75 76 int32_t main(){ 77 int t = 1; 78 cin >> t; 79 while (t--) { 80 solve(); 81 } 82 } 83 ``` 84 85 [1873C - Target Practice](/contest/1873/problem/C "Codeforces Round 898 (Div. 4)") 86 87 Idea: [flamestorm](/profile/flamestorm "Candidate Master flamestorm") 88 89 **Tutorial** 90 91 Tutorial is loading... 92 93 **Solution** 94 95 ``` 96 #include <bits/stdc++.h> 97 98 using namespace std; 99 100 const int MAX = 200007; 101 const int MOD = 1000000007; 102 103 int score[10][10] = { 104 {1,1,1,1,1,1,1,1,1,1}, 105 {1,2,2,2,2,2,2,2,2,1}, 106 {1,2,3,3,3,3,3,3,2,1}, 107 {1,2,3,4,4,4,4,3,2,1}, 108 {1,2,3,4,5,5,4,3,2,1}, 109 {1,2,3,4,5,5,4,3,2,1}, 110 {1,2,3,4,4,4,4,3,2,1}, 111 {1,2,3,3,3,3,3,3,2,1}, 112 {1,2,2,2,2,2,2,2,2,1}, 113 {1,1,1,1,1,1,1,1,1,1} 114 }; 115 116 void solve() { 117 int ans = 0; 118 for (int i = 0; i < 10; i++) { 119 for (int j = 0; j < 10; j++) { 120 char c; 121 cin >> c; 122 if (c == 'X') {ans += score[i][j];} 123 } 124 } 125 cout << ans << '\n'; 126 } 127 128 int main() { 129 ios::sync_with_stdio(false); 130 cin.tie(nullptr); 131 int tt; cin >> tt; for (int i = 1; i <= tt; i++) {solve();} 132 // solve(); 133 } 134 ``` 135 136 [1873D - 1D Eraser](/contest/1873/problem/D "Codeforces Round 898 (Div. 4)") 137 138 Idea: [flamestorm](/profile/flamestorm "Candidate Master flamestorm") 139 140 **Tutorial** 141 142 Tutorial is loading... 143 144 **Solution** 145 146 ``` 147 #include <bits/stdc++.h> 148 149 using namespace std; 150 151 const int MAX = 200'007; 152 const int MOD = 1'000'000'007; 153 154 void solve() { 155 int n, k; 156 cin >> n >> k; 157 string s; 158 cin >> s; 159 int res = 0; 160 for (int i = 0; i < n; i++) { 161 if (s[i] == 'B') { 162 res++; i += k - 1; 163 } 164 } 165 cout << res << '\n'; 166 } 167 168 int main() { 169 ios::sync_with_stdio(false); 170 cin.tie(nullptr); 171 int tt; cin >> tt; for (int i = 1; i <= tt; i++) {solve();} 172 // solve(); 173 } 174 ``` 175 176 [1873E - Building an Aquarium](/contest/1873/problem/E "Codeforces Round 898 (Div. 4)") 177 178 Idea: [flamestorm](/profile/flamestorm "Candidate Master flamestorm") 179 180 **Tutorial** 181 182 Tutorial is loading... 183 184 **Solution** 185 186 ``` 187 #include <bits/stdc++.h> 188 189 using namespace std; 190 191 const int MAX = 200'007; 192 const int MOD = 1'000'000'007; 193 194 void solve() { 195 int n; 196 long long x; 197 cin >> n >> x; 198 long long a[n]; 199 for (int i = 0; i < n; i++) { 200 cin >> a[i]; 201 } 202 long long lo = 0, hi = 2'000'000'007; 203 while (lo < hi) { 204 long long mid = lo + (hi - lo + 1) / 2; 205 long long tot = 0; 206 for (int i = 0; i < n; i++) { 207 tot += max(mid - a[i], 0LL); 208 } 209 if (tot <= x) {lo = mid;} 210 else {hi = mid - 1;} 211 } 212 cout << lo << endl; 213 } 214 215 int main() { 216 ios::sync_with_stdio(false); 217 cin.tie(nullptr); 218 int tt; cin >> tt; for (int i = 1; i <= tt; i++) {solve();} 219 // solve(); 220 } 221 ``` 222 223 [1873F - Money Trees](/contest/1873/problem/F "Codeforces Round 898 (Div. 4)") 224 225 Idea: [mesanu](/profile/mesanu "Candidate Master mesanu") 226 227 **Tutorial** 228 229 Tutorial is loading... 230 231 **Solution** 232 233 ``` 234 #include <bits/stdc++.h> 235 using namespace std; 236 237 const int N = 200'000; 238 239 int n, k; 240 int a[N+5], h[N+5], pref[N+5], length[N+5]; 241 242 bool get(int dist) 243 { 244 bool found = false; 245 for(int i = 0; i < n-dist+1; i++) 246 { 247 if(length[i] < dist){continue;} 248 int sum = pref[i+dist]-pref[i]; 249 if(sum <= k) 250 { 251 found = true; 252 break; 253 } 254 } 255 return found; 256 } 257 258 void solve() 259 { 260 pref[0] = 0; 261 cin >> n >> k; 262 for(int i = 0; i < n; i++) 263 { 264 cin >> a[i]; 265 pref[i+1] = pref[i]+a[i]; 266 } 267 for(int i = 0; i < n; i++) 268 { 269 cin >> h[i]; 270 } 271 length[n-1] = 1; 272 for(int i = n-2; i >= 0; i--) 273 { 274 if(h[i]%h[i+1] == 0) 275 { 276 length[i] = length[i+1]+1; 277 } 278 else 279 { 280 length[i] = 1; 281 } 282 } 283 int l = 1, r = N; 284 while(l <= r) 285 { 286 int mid = (l+r)/2; 287 if(get(mid)) 288 { 289 l = mid+1; 290 } 291 else 292 { 293 r = mid-1; 294 } 295 } 296 cout << r << endl; 297 } 298 299 int main() { 300 int t = 1; 301 cin >> t; 302 while (t--) 303 { 304 solve(); 305 } 306 } 307 ``` 308 309 [1873G - ABBC or BACB](/contest/1873/problem/G "Codeforces Round 898 (Div. 4)") 310 311 Idea: [flamestorm](/profile/flamestorm "Candidate Master flamestorm") 312 313 **Tutorial** 314 315 Tutorial is loading... 316 317 **Solution** 318 319 ``` 320 #include <bits/stdc++.h> 321 322 using namespace std; 323 324 const int MAX = 200'007; 325 const int MOD = 1'000'000'007; 326 327 void solve() { 328 string s; 329 cin >> s; 330 int n = s.length(), cnt = 0; 331 bool all = (s[0] == 'B' || s[n - 1] == 'B'); 332 for (int i = 0; i < n - 1; i++) { 333 if (s[i] == s[i + 1] && s[i] == 'B') {all = true;} 334 } 335 vector<int> lens; 336 int curr = 0; 337 for (int i = 0; i < n; i++) { 338 if (s[i] == 'A') {curr++;} 339 else { 340 if (curr != 0) {lens.push_back(curr);} 341 curr = 0; 342 } 343 } 344 if (curr != 0) {lens.push_back(curr);} 345 sort(lens.begin(), lens.end()); 346 347 if (lens.empty()) {cout << 0 << '\n'; return;} 348 349 int tot = 0; 350 if (all) {tot += lens[0];} 351 for (int i = 1; i < lens.size(); i++) { 352 tot += lens[i]; 353 } 354 cout << tot << '\n'; 355 } 356 357 int main() { 358 ios::sync_with_stdio(false); 359 cin.tie(nullptr); 360 int tt; cin >> tt; for (int i = 1; i <= tt; i++) {solve();} 361 // solve(); 362 } 363 ``` 364 365 [1873H - Mad City](/contest/1873/problem/H "Codeforces Round 898 (Div. 4)") 366 367 Idea: [mesanu](/profile/mesanu "Candidate Master mesanu") 368 369 **Tutorial** 370 371 Tutorial is loading... 372 373 **Solution** 374 375 ``` 376 #include <bits/stdc++.h> 377 378 using namespace std; 379 380 const int N = 200005; 381 382 vector<int> adj[N]; 383 vector<bool> vis(N); 384 385 int entry_node = -1; 386 vector<int> path; 387 388 bool dfs1(int u, int p) 389 { 390 vis[u] = true; 391 for(auto v : adj[u]) 392 { 393 if(v != p && vis[v]) 394 { 395 entry_node = v; 396 return true; 397 } 398 else if(v != p && !vis[v]) 399 { 400 if(dfs1(v, u)) 401 { 402 return true; 403 } 404 } 405 } 406 return false; 407 } 408 409 int dfs2(int u) 410 { 411 vis[u] = true; 412 int distbruh = N; 413 for(auto v : adj[u]) 414 { 415 if(v == entry_node) 416 { 417 return 1; 418 } 419 if(!vis[v]) 420 { 421 int dist = dfs2(v)+1; 422 distbruh = min(dist, distbruh); 423 } 424 } 425 return distbruh; 426 } 427 428 void solve() 429 { 430 int n, a, b; 431 cin >> n >> a >> b; 432 for(int i = 0; i < n; i++) 433 { 434 int u, v; 435 cin >> u >> v; 436 adj[u].push_back(v); 437 adj[v].push_back(u); 438 } 439 dfs1(b, -1); 440 vis.assign(n+1, false); 441 int distMarcel = N, distValeriu = 0; 442 if(entry_node == a) 443 { 444 distMarcel = 0; 445 } 446 else 447 { 448 distMarcel = dfs2(a); 449 } 450 vis.assign(n+1, false); 451 if(entry_node == b) 452 { 453 distValeriu = 0; 454 } 455 else 456 { 457 distValeriu = dfs2(b); 458 } 459 if(distValeriu < distMarcel) 460 { 461 cout << "YES" << endl; 462 } 463 else 464 { 465 cout << "NO" << endl; 466 } 467 for(int i = 1; i <= n; i++) 468 { 469 adj[i].clear(); 470 vis[i] = false; 471 } 472 } 473 474 int32_t main(){ 475 int t = 1; 476 cin >> t; 477 while (t--) { 478 solve(); 479 } 480 } 481 ```