1862.md (8790B)
1 Source: https://codeforces.com/blog/entry/119715 2 3 **We would like to thank all the participants who helped us and Codeforces to overcome the 40.000 registered users for the first time** 4 5 [1862A - Gift Carpet](/contest/1862/problem/A "Codeforces Round 894 (Div. 3)") 6 7 Idea: [diskoteka](/profile/diskoteka "Candidate Master diskoteka") 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 #define int long long 21 22 int32_t main() { 23 int q; 24 cin >> q; 25 while (q--) { 26 int n, m; 27 cin >> n >> m; 28 vector<string> carpet(n); 29 for (int i = 0; i < n; ++i) { 30 cin >> carpet[i]; 31 } 32 string vika = "vika"; 33 int fnd = 0; 34 for (int i = 0; i < m; ++i) { 35 bool check = false; 36 for (int j = 0; j < n; ++j) { 37 if (carpet[j][i] == vika[fnd]) { 38 check = true; 39 } 40 } 41 if (check) { 42 ++fnd; 43 if (fnd == 4) { 44 break; 45 } 46 } 47 } 48 if (fnd == 4) { 49 cout << "YES\n"; 50 } else { 51 cout << "NO\n"; 52 } 53 } 54 return 0; 55 } 56 ``` 57 58 **Rate the problem** 59 60 * Didn't solve 61 * Good task 62 * Average task 63 * Bad task 64 65 [1862B - Sequence Game](/contest/1862/problem/B "Codeforces Round 894 (Div. 3)") 66 67 Idea: [diskoteka](/profile/diskoteka "Candidate Master diskoteka") 68 69 **Tutorial** 70 71 Tutorial is loading... 72 73 **Solution** 74 75 ``` 76 #include <bits/stdc++.h> 77 78 using namespace std; 79 80 #define int long long 81 82 int32_t main() { 83 int q; 84 cin >> q; 85 while (q--) { 86 int n; 87 cin >> n; 88 vector<int> a; 89 for (int i = 0; i < n; ++i) { 90 int x; 91 cin >> x; 92 if (i && a.back() > x) { 93 a.push_back(1); 94 } 95 a.push_back(x); 96 } 97 cout << a.size() << "\n"; 98 for (int el : a) 99 cout << el << " "; 100 cout << "\n"; 101 } 102 return 0; 103 } 104 ``` 105 106 **Rate the problem** 107 108 * Didn't solve 109 * Good task 110 * Average task 111 * Bad task 112 113 [1862C - Flower City Fence](/contest/1862/problem/C "Codeforces Round 894 (Div. 3)") 114 115 Idea: [playerr17](/profile/playerr17 "Expert playerr17") 116 117 **Tutorial** 118 119 Tutorial is loading... 120 121 **Solution** 122 123 ``` 124 #include <iostream> 125 #include <vector> 126 127 using namespace std; 128 129 int main() { 130 int t; 131 cin >> t; 132 while (t--) { 133 int n; 134 cin >> n; 135 vector<int> a(n + 1); 136 for (int i = 1; i <= n; i++) { 137 cin >> a[i]; 138 } 139 if (a[1] != n) { 140 cout << "NO" << '\n'; 141 continue; 142 } 143 vector<int> b; 144 for (int i = n; i >= 1; i--) { 145 while (b.size() < a[i]) { 146 b.push_back(i); 147 } 148 } 149 bool meow = true; 150 for (int i = 1; i <= n; i++) { 151 if (a[i] != b[i - 1]) { 152 cout << "NO" << '\n'; 153 meow = false; 154 break; 155 } 156 } 157 if (meow) { 158 cout << "YES" << '\n'; 159 } 160 } 161 return 0; 162 } 163 ``` 164 165 **Rate the problem** 166 167 * Didn't solve 168 * Good task 169 * Average task 170 * Bad task 171 172 [1862D - Ice Cream Balls](/contest/1862/problem/D "Codeforces Round 894 (Div. 3)") 173 174 Idea: [diskoteka](/profile/diskoteka "Candidate Master diskoteka"), [Ivang](/profile/Ivang "Master Ivang") 175 176 **Tutorial** 177 178 Tutorial is loading... 179 180 **Solution** 181 182 ``` 183 #include <bits/stdc++.h> 184 185 using namespace std; 186 187 #define int long long 188 189 int32_t main() { 190 int q; 191 cin >> q; 192 while (q--) { 193 int n; 194 cin >> n; 195 int l = 0, r = min<int>(2e9, 2 * n); 196 while (r - l > 1) { 197 int m = (l + r) >> 1; 198 // m = x + y, answer = x + 2 * y 199 if (m * (m - 1) / 2 + m < n) { 200 l = m; 201 } else { 202 r = m; 203 } 204 } 205 int y = n - r * (r - 1) / 2; 206 if ((r + 1) * r / 2 <= n) { 207 cout << min(r + y, r + 1 + n - (r + 1) * r / 2) << "\n"; 208 } else { 209 cout << r + y << "\n"; 210 } 211 } 212 return 0; 213 } 214 ``` 215 216 **Rate the problem** 217 218 * Didn't solve 219 * Good task 220 * Average task 221 * Bad task 222 223 [1862E - Kolya and Movie Theatre](/contest/1862/problem/E "Codeforces Round 894 (Div. 3)") 224 225 Idea: [pavlekn](/profile/pavlekn "Master pavlekn") 226 227 **Tutorial** 228 229 Tutorial is loading... 230 231 **Solution** 232 233 ``` 234 #include <bits/stdc++.h> 235 236 using namespace std; 237 238 #define int long long 239 240 int32_t main() { 241 int t; 242 cin >> t; 243 for (int _ = 0; _ < t; ++_) { 244 int n, m, d; 245 cin >> n >> m >> d; 246 vector<int> a(n); 247 for (int i = 0; i < n; ++i) { 248 cin >> a[i]; 249 } 250 int ans = 0; 251 set<pair<int, int>> s; 252 int sum = 0; 253 for (int i = 0; i < n; ++i) { 254 int cur = sum + a[i] - d * (i + 1); 255 ans = max(ans, cur); 256 if (a[i] > 0) { 257 s.insert({a[i], i}); 258 sum += a[i]; 259 if (s.size() >= m) { 260 sum -= (s.begin()->first); 261 s.erase(s.begin()); 262 } 263 } 264 } 265 cout << ans << endl; 266 } 267 return 0; 268 } 269 ``` 270 271 **Rate the problem** 272 273 * Didn't solve 274 * Good task 275 * Average task 276 * Bad task 277 278 [1862F - Magic Will Save the World](/contest/1862/problem/F "Codeforces Round 894 (Div. 3)") 279 280 Idea: [diskoteka](/profile/diskoteka "Candidate Master diskoteka") 281 282 **Tutorial** 283 284 Tutorial is loading... 285 286 **Solution** 287 288 ``` 289 #include <bits/stdc++.h> 290 291 using namespace std; 292 293 #define int long long 294 295 int32_t main() { 296 int q; 297 cin >> q; 298 while (q--) { 299 int w, f, n; 300 cin >> w >> f >> n; 301 vector<int> s(n); 302 int sum_s = 0; 303 for (int i = 0; i < n; ++i) { 304 cin >> s[i]; 305 sum_s += s[i]; 306 } 307 vector<bool> dp(sum_s + 1); 308 dp[0] = true; 309 for (int i = 0; i < n; ++i) { 310 for (int w = sum_s; w - s[i] >= 0; --w) { 311 dp[w] = dp[w] || dp[w - s[i]]; 312 } 313 } 314 int ans = 2e9; 315 for (int i = 0; i <= sum_s; ++i) { 316 if (dp[i]) { 317 ans = min(ans, max((i + w - 1) / w, (sum_s - i + f - 1) / f)); 318 } 319 } 320 cout << ans << "\n"; 321 } 322 return 0; 323 } 324 ``` 325 326 **Rate the problem** 327 328 * Didn't solve 329 * Good task 330 * Average task 331 * Bad task 332 333 [1862G - The Great Equalizer](/contest/1862/problem/G "Codeforces Round 894 (Div. 3)") 334 335 Idea: [diskoteka](/profile/diskoteka "Candidate Master diskoteka") 336 337 **Tutorial** 338 339 Tutorial is loading... 340 341 **Solution** 342 343 ``` 344 #include <bits/stdc++.h> 345 346 using namespace std; 347 348 int main() { 349 int t; 350 cin >> t; 351 while (t--) { 352 int n; 353 scanf("%d", &n); 354 vector<int> a(n); 355 for (int i = 0; i < n; ++i) { 356 scanf("%d", &a[i]); 357 } 358 if (n == 1) { 359 int q; 360 scanf("%d", &q); 361 while (q--) { 362 int pos, val; 363 scanf("%d %d", &pos, &val); 364 cout << val << " "; 365 } 366 cout << "\n"; 367 continue; 368 } 369 multiset<int> aset; 370 for (int i = 0; i < n; ++i) { 371 aset.insert(a[i]); 372 } 373 multiset<int> deltas; 374 for (auto it = ++aset.begin(); it != aset.end(); ++it) { 375 auto prev = it; 376 --prev; 377 deltas.insert(*it - *prev); 378 } 379 int q; 380 scanf("%d", &q); 381 while (q--) { 382 int pos, val; 383 scanf("%d %d", &pos, &val); 384 auto it = aset.find(a[pos - 1]); 385 auto nxt = it, prev = it; 386 ++nxt; --prev; 387 if (it == aset.begin()) { 388 deltas.erase(deltas.find(*nxt - *it)); 389 } else if (it == --aset.end()) { 390 deltas.erase(deltas.find(*it - *prev)); 391 } else { 392 deltas.erase(deltas.find(*nxt - *it)); 393 deltas.erase(deltas.find(*it - *prev)); 394 deltas.insert(*nxt - *prev); 395 } 396 aset.erase(it); 397 aset.insert(val); 398 it = aset.find(val); 399 nxt = it, prev = it; 400 ++nxt; --prev; 401 if (it == aset.begin()) { 402 deltas.insert(*nxt - *it); 403 } else if (it == --aset.end()) { 404 deltas.insert(*it - *prev); 405 } else { 406 deltas.insert(*nxt - *it); 407 deltas.insert(*it - *prev); 408 deltas.erase(deltas.find(*nxt - *prev)); 409 } 410 a[pos - 1] = val; 411 cout << *--aset.end() + *--deltas.end() << " "; 412 } 413 cout << "\n"; 414 } 415 return 0; 416 } 417 ``` 418 419 **Rate the problem** 420 421 * Didn't solve 422 * Good task 423 * Average task 424 * Bad task