1157.md (8935B)
1 Source: https://codeforces.com/blog/entry/66737 2 3 [1157A - Reachable Numbers](/contest/1157/problem/A "Codeforces Round 555 (Div. 3)") 4 5 Idea: [BledDest](/profile/BledDest "Grandmaster BledDest") 6 7 **Tutorial** 8 9 Tutorial is loading... 10 11 **Solution** 12 13 ``` 14 def f(x): 15 x += 1 16 while(x % 10 == 0): 17 x //= 10 18 return x 19 20 a = set() 21 n = int(input()) 22 23 while(not(n in a)): 24 a.add(n) 25 n = f(n) 26 27 print(len(a)) 28 ``` 29 30 [1157B - Long Number](/contest/1157/problem/B "Codeforces Round 555 (Div. 3)") 31 32 Idea: [BledDest](/profile/BledDest "Grandmaster BledDest") 33 34 **Tutorial** 35 36 Tutorial is loading... 37 38 **Solution** 39 40 ``` 41 #include<bits/stdc++.h> 42 43 using namespace std; 44 45 int f[10]; 46 string s; 47 48 int main() 49 { 50 int n; 51 cin >> n; 52 cin >> s; 53 for(int i = 1; i <= 9; i++) 54 cin >> f[i]; 55 vector<int> diff; 56 for(int i = 0; i < n; i++) 57 diff.push_back(f[s[i] - '0'] - (s[i] - '0')); 58 for(int i = 0; i < n; i++) 59 if(diff[i] > 0) 60 { 61 while(i < n && diff[i] >= 0) 62 { 63 s[i] = char(f[s[i] - '0'] + '0'); 64 i++; 65 } 66 break; 67 } 68 cout << s << endl; 69 } 70 ``` 71 72 [1157C1 - Increasing Subsequence (easy version)](/contest/1157/problem/C1 "Codeforces Round 555 (Div. 3)") 73 74 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov") 75 76 **Tutorial** 77 78 Tutorial is loading... 79 80 **Solution** 81 82 ``` 83 #include <bits/stdc++.h> 84 85 using namespace std; 86 87 int main() { 88 #ifdef _DEBUG 89 freopen("input.txt", "r", stdin); 90 // freopen("output.txt", "w", stdout); 91 #endif 92 93 int n; 94 cin >> n; 95 vector<int> a(n); 96 for (int i = 0; i < n; ++i) { 97 cin >> a[i]; 98 } 99 100 string res; 101 int l = 0, r = n - 1; 102 int lst = 0; 103 while (l <= r) { 104 vector<pair<int, char>> cur; 105 if (lst < a[l]) cur.push_back(make_pair(a[l], 'L')); 106 if (lst < a[r]) cur.push_back(make_pair(a[r], 'R')); 107 sort(cur.begin(), cur.end()); 108 if (int(cur.size()) == 2) { 109 cur.pop_back(); 110 } 111 if (int(cur.size()) == 1) { 112 if (cur[0].second == 'L') { 113 res += 'L'; 114 lst = a[l]; 115 ++l; 116 } else { 117 res += 'R'; 118 lst = a[r]; 119 --r; 120 } 121 } else { 122 break; 123 } 124 } 125 126 cout << res.size() << endl << res << endl; 127 128 return 0; 129 } 130 ``` 131 132 [1157C2 - Increasing Subsequence (hard version)](/contest/1157/problem/C2 "Codeforces Round 555 (Div. 3)") 133 134 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov") 135 136 **Tutorial** 137 138 Tutorial is loading... 139 140 **Solution** 141 142 ``` 143 #include <bits/stdc++.h> 144 145 using namespace std; 146 147 int main() { 148 #ifdef _DEBUG 149 freopen("input.txt", "r", stdin); 150 // freopen("output.txt", "w", stdout); 151 #endif 152 153 int n; 154 cin >> n; 155 vector<int> a(n); 156 for (int i = 0; i < n; ++i) { 157 cin >> a[i]; 158 } 159 160 string res; 161 int l = 0, r = n - 1; 162 int lst = 0; 163 while (l <= r) { 164 vector<pair<int, char>> cur; 165 if (lst < a[l]) cur.push_back(make_pair(a[l], 'L')); 166 if (lst < a[r]) cur.push_back(make_pair(a[r], 'R')); 167 sort(cur.begin(), cur.end()); 168 if (int(cur.size()) == 2 && cur[0].first != cur[1].first) { 169 cur.pop_back(); 170 } 171 if (int(cur.size()) == 1) { 172 if (cur[0].second == 'L') { 173 res += 'L'; 174 lst = a[l]; 175 ++l; 176 } else { 177 res += 'R'; 178 lst = a[r]; 179 --r; 180 } 181 } else if (int(cur.size()) == 2) { 182 int cl = 1, cr = 1; 183 while (l + cl <= r && a[l + cl] > a[l + cl - 1]) ++cl; 184 while (r - cr >= l && a[r - cr] > a[r - cr + 1]) ++cr; 185 if (cl > cr) { 186 res += string(cl, 'L'); 187 } else { 188 res += string(cr, 'R'); 189 } 190 break; 191 } else { 192 break; 193 } 194 } 195 196 cout << res.size() << endl << res << endl; 197 198 return 0; 199 } 200 ``` 201 202 [1157D - N Problems During K Days](/contest/1157/problem/D "Codeforces Round 555 (Div. 3)") 203 204 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov") 205 206 **Tutorial** 207 208 Tutorial is loading... 209 210 **Solution** 211 212 ``` 213 #include <bits/stdc++.h> 214 215 using namespace std; 216 217 int main() { 218 #ifdef _DEBUG 219 freopen("input.txt", "r", stdin); 220 // freopen("output.txt", "w", stdout); 221 #endif 222 223 int n, k; 224 cin >> n >> k; 225 if (n < k * 1ll * (k + 1) / 2) { 226 cout << "NO" << endl; 227 return 0; 228 } 229 230 int nn = n - k * (k + 1) / 2; 231 vector<int> a(k); 232 for (int i = 0; i < k; ++i) { 233 a[i] = i + 1 + (nn / k) + (i >= k - nn % k); 234 } 235 236 if (nn != k - 1) { 237 cout << "YES" << endl; 238 for (int i = 0; i < k; ++i) cout << a[i] << " "; 239 cout << endl; 240 } else { 241 if (k > 3) { 242 --a[1]; 243 ++a[k - 1]; 244 } 245 if (k == 2 || k == 3) { 246 cout << "NO" << endl; 247 } else { 248 cout << "YES" << endl; 249 for (int i = 0; i < k; ++i) cout << a[i] << " "; 250 cout << endl; 251 } 252 } 253 254 return 0; 255 } 256 ``` 257 258 [1157E - Minimum Array](/contest/1157/problem/E "Codeforces Round 555 (Div. 3)") 259 260 Idea: [vovuh](/profile/vovuh "Candidate Master vovuh") 261 262 **Tutorial** 263 264 Tutorial is loading... 265 266 **Solution** 267 268 ``` 269 #include <bits/stdc++.h> 270 271 using namespace std; 272 273 int main() { 274 #ifdef _DEBUG 275 freopen("input.txt", "r", stdin); 276 // freopen("output.txt", "w", stdout); 277 #endif 278 279 int n; 280 cin >> n; 281 vector<int> a(n); 282 multiset<int> b; 283 for (int i = 0; i < n; ++i) { 284 cin >> a[i]; 285 } 286 for (int i = 0; i < n; ++i) { 287 int x; 288 cin >> x; 289 b.insert(x); 290 } 291 292 for (int i = 0; i < n; ++i) { 293 auto it = b.lower_bound(n - a[i]); 294 if (it == b.end()) it = b.begin(); 295 cout << (a[i] + *it) % n << " "; 296 b.erase(it); 297 } 298 cout << endl; 299 300 return 0; 301 } 302 ``` 303 304 [1157F - Maximum Balanced Circle](/contest/1157/problem/F "Codeforces Round 555 (Div. 3)") 305 306 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov") 307 308 **Tutorial** 309 310 Tutorial is loading... 311 312 **Solution** 313 314 ``` 315 #include <bits/stdc++.h> 316 317 using namespace std; 318 319 int main() { 320 #ifdef _DEBUG 321 freopen("input.txt", "r", stdin); 322 // freopen("output.txt", "w", stdout); 323 #endif 324 325 int n; 326 cin >> n; 327 vector<int> a(n); 328 vector<int> cnt(200 * 1000 + 1); 329 for (int i = 0; i < n; ++i) { 330 cin >> a[i]; 331 ++cnt[a[i]]; 332 } 333 334 sort(a.begin(), a.end()); 335 a.resize(unique(a.begin(), a.end()) - a.begin()); 336 337 int l = 0, r = 0; 338 int ans = cnt[a[0]]; 339 for (int i = 0; i < int(a.size()); ++i) { 340 int j = i + 1; 341 int sum = cnt[a[i]]; 342 while (a[j] - a[j - 1] == 1 && cnt[a[j]] > 1) { 343 sum += cnt[a[j]]; 344 ++j; 345 } 346 int cr = j - 1; 347 if (j < n && a[j] - a[j - 1] == 1) { 348 sum += cnt[a[j]]; 349 cr = j; 350 } 351 if (ans < sum) { 352 ans = sum; 353 l = i; 354 r = cr; 355 } 356 i = j - 1; 357 } 358 359 cout << ans << endl; 360 for (int c = 0; c < cnt[a[l]]; ++c) cout << a[l] << " "; 361 for (int i = l + 1; i < r; ++i) { 362 for (int c = 0; c < cnt[a[i]] - 1; ++c) cout << a[i] << " "; 363 } 364 for (int c = 0; l != r && c < cnt[a[r]]; ++c) cout << a[r] << " "; 365 for (int i = r - 1; i > l; --i) cout << a[i] << " "; 366 cout << endl; 367 368 return 0; 369 } 370 ``` 371 372 [1157G - Inverse of Rows and Columns](/contest/1157/problem/G "Codeforces Round 555 (Div. 3)") 373 374 Idea: [vovuh](/profile/vovuh "Candidate Master vovuh") 375 376 [This](https://codeforces.com/blog/entry/66703?#comment-508037) is the comment about the quadratic solution. Thank you so much for mentioning this fact, [STommydx](/profile/STommydx "Candidate Master STommydx")! 377 378 **Tutorial** 379 380 Tutorial is loading... 381 382 **Solution** 383 384 ``` 385 #include <bits/stdc++.h> 386 387 using namespace std; 388 389 int n, m; 390 391 void invRow(vector<vector<int>> &a, int idx) { 392 for (int pos = 0; pos < m; ++pos) { 393 a[idx][pos] ^= 1; 394 } 395 } 396 397 void invCol(vector<vector<int>> &a, int idx) { 398 for (int pos = 0; pos < n; ++pos) { 399 a[pos][idx] ^= 1; 400 } 401 } 402 403 int main() { 404 #ifdef _DEBUG 405 freopen("input.txt", "r", stdin); 406 // freopen("output.txt", "w", stdout); 407 #endif 408 409 cin >> n >> m; 410 vector<vector<int>> a(n, vector<int>(m)); 411 for (int i = 0; i < n; ++i) { 412 for (int j = 0; j < m; ++j) { 413 cin >> a[i][j]; 414 } 415 } 416 417 for (int cnt0 = 0; cnt0 <= m; ++cnt0) { 418 string r(n, '0'); 419 string c(m, '0'); 420 vector<vector<int>> b = a; 421 for (int j = 0; j < m; ++j) { 422 if ((j < cnt0 && b[0][j] == 1) || (j >= cnt0 && b[0][j] == 0)) { 423 invCol(b, j); 424 c[j] = '1'; 425 } 426 } 427 bool ok = true; 428 if (cnt0 < m) { 429 for (int i = 1; i < n; ++i) { 430 int sum = accumulate(b[i].begin(), b[i].end(), 0); 431 if (sum != 0 && sum != m) { 432 ok = false; 433 } else if (sum == 0) { 434 invRow(b, i); 435 r[i] = '1'; 436 } 437 } 438 } else { 439 int idx = -1; 440 for (int i = 1; i < n; ++i) { 441 int sum = accumulate(b[i].begin(), b[i].end(), 0); 442 if (sum != 0 && sum != m) { 443 if (idx != -1) ok = false; 444 else idx = i; 445 } 446 } 447 if (idx == -1) { 448 for (int i = 1; i < n; ++i) { 449 int sum = accumulate(b[i].begin(), b[i].end(), 0); 450 if (sum == 0) { 451 invRow(b, i); 452 r[i] = '1'; 453 } 454 } 455 } else { 456 for (int i = 1; i < idx; ++i) { 457 int sum = accumulate(b[i].begin(), b[i].end(), 0); 458 if (sum == m) { 459 invRow(b, i); 460 r[i] = '1'; 461 } 462 } 463 if (b[idx][0] == 1) { 464 invRow(b, idx); 465 r[idx] = '1'; 466 } 467 for (int j = 1; j < m; ++j) { 468 if (b[idx][j] < b[idx][j - 1]) { 469 ok = false; 470 } 471 } 472 for (int i = idx + 1; i < n; ++i) { 473 int sum = accumulate(b[i].begin(), b[i].end(), 0); 474 if (sum == 0) { 475 invRow(b, i); 476 r[i] = '1'; 477 } 478 } 479 } 480 } 481 if (ok) { 482 cout << "YES" << endl << r << endl << c << endl; 483 return 0; 484 } 485 } 486 487 cout << "NO" << endl; 488 489 return 0; 490 } 491 ```