1647.md (18796B)
1 Source: https://codeforces.com/blog/entry/100780 2 3 Task A. Idea [FairyWinx](/profile/FairyWinx "Master FairyWinx") 4 5 **Hint 1** 6 7 The optimal answer has the maximum number of digits, so you only need to use the digits $1,2$. 8 9 **Hint 2** 10 11 Alternate these numbers so that there are no adjacent identical numbers. 12 13 **Solution** 14 15 Since we want to maximize the number we need, we will first find the longest suitable number. Obviously, it is better to use only the numbers $1$ and $2$ for this. Therefore, the answer always looks like $2121\ldots$ or $1212\ldots$. The first option is optimal when $n$ has a remainder of $2$ or $0$ modulo $3$, otherwise the second option is optimal. 16 17 Below is an example of a neat implementation. 18 19 **Code** 20 21 ``` 22 #include <bits/stdc++.h> 23 24 using namespace std; 25 26 void solve() { 27 int n; 28 cin >> n; 29 int type; 30 if (n % 3 == 1) 31 type = 1; 32 else 33 type = 2; 34 int sum = 0; 35 while (sum != n) { 36 cout << type; 37 sum += type; 38 type = 3 - type; 39 } 40 cout << '\n'; 41 } 42 43 int main() { 44 ios_base::sync_with_stdio(0); 45 cin.tie(0); 46 47 int t; 48 cin >> t; 49 while (t--) 50 solve(); 51 } 52 ``` 53 54 --- 55 56 Задача B. Idea [FairyWinx](/profile/FairyWinx "Master FairyWinx") 57 58 **Hint 1** 59 60 What is a picture if the answer to the problem is "YES". 61 62 **Hint 2** 63 64 Think about a square of size $2\times 2$. 65 66 **Solution** 67 68 Note that the answer to the problem is "YES" if and only if the picture is a certain number of disjoint rectangles. Now, in this case, let's look at all squares of size $2\times 2$, note that there cannot be exactly $3$ filled cells in each of them. 69 70 It is also clear that if there are $3$ such cells, then there will be two intersecting rectangles. Therefore, you just need to check if there is a $2\times 2$ square in which there are exactly $3$ colored cells. 71 72 **Code** 73 74 ``` 75 #include <bits/stdc++.h> 76 77 using namespace std; 78 79 void solve() { 80 int n, m; 81 cin >> n >> m; 82 vector<vector<int>> a(n, vector<int> (m)); 83 for (int i = 0; i < n; ++i) { 84 string s; 85 cin >> s; 86 for (int j = 0; j < m; ++j) { 87 a[i][j] = s[j] - '0'; 88 } 89 } 90 for (int i = 0; i < n - 1; ++i) { 91 for (int j = 0; j < m - 1; ++j) { 92 int sum = a[i][j] + a[i][j + 1] + a[i + 1][j] + a[i + 1][j + 1]; 93 if (sum == 3) { 94 cout << "NO\n"; 95 return; 96 } 97 } 98 } 99 cout << "YES\n"; 100 } 101 102 int main() { 103 ios_base::sync_with_stdio(0); 104 cin.tie(0); 105 106 int t; 107 cin >> t; 108 while (t--) 109 solve(); 110 } 111 ``` 112 113 --- 114 115 Задача C. Idea [FairyWinx](/profile/FairyWinx "Master FairyWinx") 116 117 **Hint 1** 118 119 There is always an answer when the upper right cell is painted white. 120 121 **Hint 1** 122 123 Imagine that you have only rectangles of size $1\times 2$. 124 125 **Hint 2** 126 127 Paint over the cells from the "end". 128 129 **Solution** 130 131 According to the condition, if the upper left cell is painted black, then we cannot paint it that way. Otherwise it is possible. Let's colour the cells in the following order: $(n,m), (n,m - 1), \ldots, (n, 1), (n - 1, m), \ldots (1, 1)$. 132 133 Let the cell $(i, j)$ be colored black, then if $j \gt 1$, then just paint the rectangle $(i, j - 1)$, $(i, j)$. Otherwise, if $j = 1$, then we will color the rectangle $(i - 1, j)$. 134 135 After such an operation, no cells that we painted before will be repainted, since they have one coordinate larger than ours, and the cell itself will be painted black. 136 137 Thus, we are able to paint the table for a maximum of $n\cdot m - 1$ operations. 138 139 **Code** 140 141 ``` 142 #include <bits/stdc++.h> 143 144 using namespace std; 145 146 void solve() { 147 int n, m; 148 cin >> n >> m; 149 vector<vector<int>> a(n, vector<int> (m)); 150 for (int i = 0; i < n; ++i) { 151 string s; 152 cin >> s; 153 for (int j = 0; j < m; ++j) 154 a[i][j] = s[j] - '0'; 155 } 156 vector<array<int, 4>> ans; 157 if (a[0][0] == 1) { 158 cout << -1<< '\n'; 159 return; 160 } 161 162 for (int j = m - 1; j >= 0; --j) { 163 for (int i = n - 1; i >= 0; --i) { 164 if (a[i][j]) { 165 if (i != 0) { 166 ans.push_back({i, j + 1, i + 1, j + 1}); 167 } else { 168 ans.push_back({i + 1, j, i + 1, j + 1}); 169 } 170 } 171 } 172 } 173 cout << ans.size() << '\n'; 174 for (auto i : ans) { 175 cout << i[0] << ' ' << i[1] << ' ' << i[2] << ' ' << i[3] << '\n'; 176 } 177 } 178 179 int main() { 180 ios_base::sync_with_stdio(0); 181 cin.tie(0); 182 183 int t; 184 cin >> t; 185 while (t--) 186 solve(); 187 } 188 ``` 189 190 --- 191 192 Задача D. Idea [FairyWinx](/profile/FairyWinx "Master FairyWinx") 193 194 **An important fact** 195 196 A number is beautiful only if it is a multiple of $d$, but not a multiple of $d^2$ 197 198 **Hint 1.1** 199 200 Let's solve a more general problem: count the number of such partitions. 201 202 **Hint 1.2** 203 204 This problem is solved by dynamic programming. 205 206 **Hint 1.3** 207 208 Keep the remaining number in dynamics, as well as the last divisor. 209 210 **Solution 1** 211 212 Let's solve a more complex problem: calculate the number of partitions into such multipliers. 213 214 This is easily solved by dynamic programming. Let $dp_{n, d}$ be the number of factorizations, if we have a number left to decompose the number $n$, and before that we divided by the number $d$. Let's go through all such beautiful numbers $i\geq d$ that divide $n$, then $dp_{n /i, i} += dp_{n, d}$. 215 216 Note that in this case, we took into account each option exactly once, since we count the divisors in the order of their increase. 217 218 Let $C$ be the number of divisors of the number $x$, and $V$ be the number of beautiful divisors of the number $x$. Then it works for $O(C\cdot V)$ or $O(C\cdot V^2\cdot log)$ depending on the implementation (since $n$ is always a divisor of the number $x$), but it all comes easily, since $V$ is no more $700$. 219 220 **Code** 221 222 ``` 223 #include <bits/stdc++.h> 224 225 using namespace std; 226 227 bool good(int i, int d) { 228 return i % d == 0 && i % (1ll * d * d) != 0; 229 } 230 231 void solve() { 232 int x, d; 233 cin >> x >> d; 234 map<pair<int, int>, int> dp; 235 dp[{x, 1}] = 1; 236 int res = 0; 237 vector<int> del; 238 for (int i = 1; i * i <= x; ++i) { 239 if (x % i == 0) { 240 if (good(i, d)) 241 del.push_back(i); 242 if (x != i * i && good(x / i, d)) 243 del.push_back(x / i); 244 } 245 } 246 while (dp.size()) { 247 auto z = *dp.rbegin(); 248 if (z.first.first == 1) { 249 res += z.second; 250 } 251 for (auto i : del) { 252 if (z.first.first % i == 0 && i >= z.first.second) { 253 dp[{z.first.first / i, i}] = min(dp[{z.first.first / i, i}] + z.second, 2); 254 } 255 } 256 dp.erase(z.first); 257 } 258 if (res == 1) 259 cout << "NO\n"; 260 else 261 cout << "YES\n"; 262 } 263 264 int main() { 265 ios_base::sync_with_stdio(0); 266 cin.tie(0); 267 268 int t; 269 cin >> t; 270 while (t--) 271 solve(); 272 } 273 ``` 274 275 **Hint 2.1** 276 277 Consider the case  278 279 **Solution 2 (which almost everyone wrote)** 280 281 Let $x = d^a\cdot b$. Where $b$ is not a multiple of $d$. 282 283 Then consider a few cases: 284 285 * $a = 1$. Then $a$ is a beautiful number, since any number multiple of $d^2$ can be decomposed into $d\cdot(a/d)$, each of which is colored, and a number multiple of only $d$, obviously, cannot be decomposed. So in this case there is exactly one option. 286 * $b$ is composite, then obviously we can decompose in several ways if $a\neq 1$. 287 * $d$ is simple. If $b$ is prime, then the statement — we have only one option to decompose the number. Since every beautiful multiplier of the form $d\cdot k$. But since $d$ is simple, there are no other ways to decompose it, except to add a multiplier from $b$, and since $b$ is simple, then all these options will be equal before the permutation. 288 * $d$ is composite and is not a power of prime. If $a\leq 2$, then this case is no different from the past, since we still have to get two beautiful multipliers and they will all just be equal to $d$. Otherwise, let $d = p\cdot q$, where $gcd(p, q) = 1$. Then we can make the number $p\cdot q^{b - 1}$ and $p^{b - 1}\cdot q$. And also $q\cdot p, q\cdot p, \ldots , q\cdot p$, in this case we have a different number of divisors, so these options will be different, which means we have several options in this case. 289 * $d$ is the power of a prime number. Then $d = p^k$. The statement, if $d = p^2$, and $x =p^7$, then it cannot be decomposed in several ways, otherwise, if $a \gt 2$ and $k \gt 1$, then let's look at the partition of $p^{2k - 1}, p^{k+1}, p^k, \ldots , p^k$, it is clear that if $k \gt 2$, then even if $b = p$, then the multiplier of $p^{k+ 2}$ will still be beautiful, so it does not differ from the composite $d$ in last case. Otherwise, if $k = 2$, then if $a = 3$ and $b = p$, then nothing can be added, otherwise we will have the opportunity to choose $3$ of the multiplier $p^k$, and somehow decompose the rest (since in this case $a \gt 3$, then at least one more multiplier will be) and add $b$ there. And we can decompose these 3 multipliers into $2$ or $3$ multipliers, as written above. Therefore, the only unique case when $d$ is the degree of a prime is $d = p^2, x = p^7$. 290 291 **Реализация** 292 293 ``` 294 #include <bits/stdc++.h> 295 296 using namespace std; 297 298 int prime(int x) { 299 for (int i = 2; i * i <= x; ++i) { 300 if (x % i == 0) 301 return i; 302 } 303 return -1; 304 } 305 306 void solve() { 307 int x, d; 308 cin >> x >> d; 309 int cnt = 0; 310 while (x % d == 0) { 311 ++cnt; 312 x /= d; 313 } 314 if (cnt == 1) { 315 cout << "NO\n"; 316 return; 317 } 318 if (prime(x) != -1) { 319 cout << "YES\n"; 320 return; 321 } 322 if (prime(d) != -1 && d == prime(d) * prime(d)) { 323 if (x == prime(d) && cnt == 3) { 324 cout << "NO\n"; 325 return; 326 } 327 } 328 if (cnt > 2 && prime(d) != -1) { 329 cout << "YES\n"; 330 return; 331 } 332 cout << "NO\n"; 333 } 334 335 int main() { 336 ios_base::sync_with_stdio(0); 337 cin.tie(0); 338 339 int t; 340 cin >> t; 341 while (t--) 342 solve(); 343 } 344 ``` 345 346 --- 347 348 Задача E. Idea [FairyWinx](/profile/FairyWinx "Master FairyWinx") 349 350 **Hint 1** 351 352 After each operation, the maximum number is always increased by a specific number. 353 354 **Hint 2** 355 356 Students with a number greater than $n$ are not interested in us. 357 358 **Hint 3** 359 360 Imagine that schoolchildren are not expelled, but at any given time we are just interested in a student with a minimum number. Obviously, the answer in this case will not change in any way. 361 362 **Hint 4** 363 364 Understand that every student will move to one particular desk after all the operations. 365 366 **Hint 5** 367 368 Write a greedy  369 370 **Solution** 371 372 After each lesson, the person's number increases from the maximum number by the number of desks where no one goes. Therefore, it is easy to calculate how much time has passed since the very beginning, let it be the number $k$. 373 374 Then let's imagine that schoolchildren are not expelled, but at any given time we are simply interested in a student with a minimum number. Obviously, the answer in this case will not change in any way. 375 376 Let $to_i$ be the desk to which the student will move after $k$ transfers, who originally sat at $i$ desk. This is a standard problem that can be solved using binary lifts or not the most pleasant dfs with cycle allocation and the like. (but we do not recommend you to write the latter), we define the set $V_i$ as the set of all numbers $j$, where $to_j = i$. 377 378 Let the starting placement of the student be a permutation of $b$, then we will understand that if someone is transferred to the $i$ desk after $k$ operations, then the value in it is the minimum value in $V_i$. And if no one changes seats for it, then a student with the same number will always sit in it, regardless of the initial seating arrangement. After that, it is not difficult to guess the optimal starting seating of schoolchildren. 379 380 Let $s$ be a lot of schoolchildren for whom we have not yet chosen the desk at which they are sitting. We will iterate over $i$ from $1$ to $n$ in ascending order. Then you need to understand who should sit at the $i$ desk. 381 382 If we know that there is a desk for which $min(V_i) = i$ must be performed, then we must put a student with the minimum number of $V_i$ at $i$, and we can put the remaining people at any desks with a number greater than $i$, so we will add all the other students to the set $s$. Otherwise, we just need to take a person from $s$ with the minimum number and put him in a place under the number $i$, and then just remove him from the set of $s$. 383 384 **Реализация** 385 386 ``` 387 #include <bits/stdc++.h> 388 389 using namespace std; 390 391 const int K = 30; 392 393 int main() { 394 ios_base::sync_with_stdio(0); 395 cin.tie(0); 396 397 int n; 398 cin >> n; 399 vector<int> cnt(n); 400 vector<vector<int>> up(n, vector<int> (K)); 401 for (int i = 0; i < n; ++i) { 402 int a; 403 cin >> a; 404 --a; 405 ++cnt[a]; 406 up[i][0] = a; 407 } 408 for (int k = 1; k < K; ++k) { 409 for (int i = 0; i < n; ++i) { 410 up[i][k] = up[up[i][k - 1]][k - 1]; 411 } 412 } 413 vector<int> a(n); 414 int cnt_bad = 0; 415 for (int i = 0; i < n; ++i) { 416 cin >> a[i]; 417 if (!cnt[i]) { 418 ++cnt_bad; 419 } 420 } 421 int k = (*max_element(a.begin(), a.end()) - n) / cnt_bad; 422 vector<vector<int>> add(n); 423 424 for (int i = 0; i < n; ++i) { 425 int v = i, level = k; 426 for (int j = K - 1; j >= 0; --j) { 427 if (level >= (1 << j)) { 428 level -= (1 << j); 429 v = up[v][j]; 430 } 431 } 432 add[a[v] - 1].push_back(i); 433 } 434 set<int> now; 435 vector<int> ans(n); 436 for (int i = 0; i < n; ++i) { 437 if (add[i].size()) { 438 int res = *min_element(add[i].begin(), add[i].end()); 439 for (int j : add[i]) { 440 if (j != res) { 441 now.emplace(j); 442 } 443 } 444 ans[res] = i + 1; 445 } else { 446 ans[*now.begin()] = i + 1; 447 now.erase(*now.begin()); 448 } 449 } 450 for (int i : ans) 451 cout << i << ' '; 452 cout << '\n'; 453 } 454 ``` 455 456 --- 457 458 Задача F. Idea [Igorbunov](/profile/Igorbunov "Grandmaster Igorbunov") 459 460 **Hint 1** 461 462 Realize that the maximum element is always an "inflection" of the first sequence. 463 464 **Hint 2** 465 466 It can be assumed that the "inflection" of the second subsequence will always be to the left of the maximum element (if anything, you can then simply expand the array). 467 468 **Hint 3** 469 470 In total, we have $3$ points in time — both subsequences increase, the first decreases, and the second increases, or both subsequences decrease. 471 472 **Hint 4** 473 474 The first and third cases are solved by obvious greed. 475 476 **Hint 5** 477 478 For the second one, you can simply write the dynamics. 479 480 **Solution** 481 482 The inflection of the sequence is the maximum number in the subsequence. Then note that in the first subsequence, the inflection will be the maximum number in our array, let its position in the array be $ind$. 483 484 Then let's say for convenience that the inflection of the second subsequence will be to the right of the maximum element. (then expand the array and run the solution one more time). 485 486 In this case, we will have $3$ states: both subsequences increase, the first decreases, and the second increases, or both subsequences decrease. 487 488 Let's solve the first case first: 489 490 Let $dp1_i$ be the minimum possible maximum element in a subsequence that does not contain an $i$ element. It is considered not difficult. If $dp1_{i - 1} \lt a_{i}$, then $dp1_{i} = min(dp1_{i}, a_{i - 1})$, since in this case we can add an $i$ element to a subsequence that does not contain an element of $i - 1$. Similarly, if $a_{i - 1} \lt a_{i}$, then $dp1_{i} = min(dp1_{i}, dp1_{i - 1})$. 491 492 The third case is considered anologically, but only it needs to be counted from the end. (This array will be $dp3$) 493 494 Now let's deal with the second case: 495 496 Let $dp2_{i, 0}$ be the minimum possible last element in the second subsequence if the $i$ element belongs to the first subsequence. And $dp2_{i, 1}$ is the maximum possible last element in the first subsequence if the $i$ element belongs to the second subsequence. There are several options. If $i$ and $i - 1$ lie in the same and different subsequences. And we will count for $i\leq ind$, since before this section both sub-sequences increase, and this is another calculated case. And then it is not difficult to get the conversion formulas: 497 498 * $dp2_{ind, 0} = dp1_{ind}$, by definition $dp2_{ind, 0}$ 499 * If $a_{i - 1} \gt a_i$, then $dp2_{i, 0} = min(dp2_{i, 0}, dp2_{i - 1, 0})$. 500 * If $dp2_{i - 1, 1} \gt a_i$, then $dp2_{i, 0} = min(dp2_{i, 0}, a_{i - 1})$. 501 * If $a_{i - 1} \lt a_{i}$, then $dp2_{i, 1} = max(dp2_{i, 1}, dp3_{i - 1, 1})$. 502 * If $dp2_{i - 1, 0} \lt a_i$, then $dp2_{i, 1} = max(dp2_{i, 1}, a_{i - 1})$. 503 504 Now let's understand that the element with the number $i$ can be an inflection of the second subsequence if $i \gt ind$, as well as $dp2_{i, 1} \gt dp3_{i}$. That is, we can move from the second state to the third. 505 506 **Реализация** 507 508 ``` 509 #include <bits/stdc++.h> 510 511 using namespace std; 512 513 const int inf = 1e9 + 228; 514 515 int solve (int n, vector<int> a) { 516 int ind = max_element(a.begin(), a.end()) - a.begin(); 517 vector<int> dp1(n, inf); 518 dp1[0] = -1; 519 for (int i = 1; i <= ind; ++i) { 520 if (a[i] > dp1[i - 1]) 521 dp1[i] = min(dp1[i], a[i - 1]); 522 if (a[i] > a[i - 1]) 523 dp1[i] = min(dp1[i], dp1[i - 1]); 524 } 525 526 vector<int> dp2(n, inf); 527 dp2[n - 1] = -1; 528 for (int i = n - 2; i >= ind; --i) { 529 if (a[i] > dp2[i + 1]) 530 dp2[i] = min(dp2[i], a[i + 1]); 531 if (a[i] > a[i + 1]) 532 dp2[i] = min(dp2[i], dp2[i + 1]); 533 } 534 535 vector<array<int, 2>> dp3(n, {inf, -inf}); 536 dp3[ind][0] = dp1[ind]; 537 int ans = 0; 538 for (int i = ind + 1; i < n; ++i) { 539 if (a[i - 1] > a[i]) 540 dp3[i][0] = min(dp3[i][0], dp3[i - 1][0]); 541 if (dp3[i - 1][1] > a[i]) 542 dp3[i][0] = min(dp3[i][0], a[i - 1]); 543 544 if (a[i - 1] < a[i]) 545 dp3[i][1] = max(dp3[i][1], dp3[i - 1][1]); 546 if (dp3[i - 1][0] < a[i]) 547 dp3[i][1] = max(dp3[i][1], a[i - 1]); 548 549 if (dp3[i][1] > dp2[i]) 550 ++ans; 551 } 552 return ans; 553 } 554 555 signed main() { 556 ios_base::sync_with_stdio(0); 557 cin.tie(0); 558 559 int n; 560 cin >> n; 561 vector<int> a(n); 562 for (int i = 0; i < n; ++i) 563 cin >> a[i]; 564 int ans = solve(n, a); 565 reverse(a.begin(), a.end()); 566 cout << ans + solve(n, a) << '\n'; 567 } 568 ```