2232.md (23412B)
1 Source: https://codeforces.com/blog/entry/154128 2 3 [Problem A — Convergence](https://codeforces.com/contest/2232/problem/A) 4 5 Problem Idea: [36champ](/profile/36champ "International Master 36champ") 6 Solution Idea: [36champ](/profile/36champ "International Master 36champ") 7 8 **Hint 1** 9 10 What if the meeting location is fixed? 11 12 **Solution** 13 14 If the meeting location is fixed, the answer is max(the number of people to the left of that position, the number of people to the right of that position. 15 16 This can be solved in $O(n^2)$ by iterating through all position that has at least one person on it. This problem can also be solved in $O(n\log n)$ by sorting and setting the meeting position to the median of all positions. 17 18 **Code** 19 20 ``` 21 #include <bits/stdc++.h> 22 #define pb push_back 23 24 using namespace std; 25 26 typedef long long ll; 27 typedef vector<int> vi; 28 typedef vector<vi> vvi; 29 typedef vector<ll> vll; 30 typedef vector<vll> vvll; 31 typedef pair<int, int> pii; 32 typedef pair<ll, ll> pll; 33 34 int main() 35 { 36 ios_base::sync_with_stdio(false); 37 cin.tie(nullptr); 38 cout.tie(nullptr); 39 40 int t = 1; 41 cin >> t; 42 while(t-->0) 43 { 44 int n; 45 cin >> n; 46 47 vi a(n); 48 for(int i=0; i<n; i++) cin >> a[i]; 49 50 sort(a.begin(), a.end()); 51 52 int cnt = 0; 53 for(int i=0; i<n; i++) if(a[i] != a[n-1-i]) cnt++; 54 55 cout << cnt / 2 << "\n"; 56 } 57 } 58 ``` 59 60 **Rate The Problem!** 61 62 * Good Problem 63 * Okay Problem 64 * Bad Problem 65 * Didn't Solve 66 67 [Problem B — Cake Leveling](https://codeforces.com/contest/2232/problem/B) 68 69 Problem Idea: [36champ](/profile/36champ "International Master 36champ"), [Proof_by_QED](/profile/Proof_by_QED "Master Proof_by_QED") 70 Solution Idea: [Proof_by_QED](/profile/Proof_by_QED "Master Proof_by_QED") 71 72 **Hint 1** 73 74 If we know the answer to the $i$-th position, what can we say about the answer to the $(i + 1)$-th position? 75 76 **Hint 2** 77 78 Suppose that we can just move the frosting freely. What is the maximum height the frosting can be while keeping it leveled? 79 80 **Solution** 81 82 Using the first two hints, we hypothesize that the answer for the first $i$ position of the cake is min(prefix average). Now, we will show that this is true by induction. 83 84 Base Case ($i = 1$): Since there is only one position, the answer is $a_1$. 85 86 Inductive Step: Suppose that the answer for the $i$ position is correct, now consider the first $i + 1$ positions. Since we have $\sum_{j=1}^{i+1} a_j$ units of frosting, the maximum height is $\frac{\sum_{j=1}^{i+1} a_j}{i + 1}$. Combining this with hint 1 and the inductive hypothesis, the answer is $\min_{k=1}^{i+1} \frac{\sum_{j=1}^{k+1} a_j}{k + 1}$. 87 88 This problem can be solved in $O(n)$. 89 90 **Code** 91 92 ``` 93 #include <bits/stdc++.h> 94 #define pb push_back 95 96 using namespace std; 97 98 typedef long long ll; 99 typedef vector<int> vi; 100 typedef vector<vi> vvi; 101 typedef vector<ll> vll; 102 typedef vector<vll> vvll; 103 typedef pair<int, int> pii; 104 typedef pair<ll, ll> pll; 105 106 int main() 107 { 108 ios_base::sync_with_stdio(false); 109 cin.tie(nullptr); 110 cout.tie(nullptr); 111 112 int t = 1; 113 cin >> t; 114 while(t-->0) 115 { 116 int n; 117 cin >> n; 118 119 vll a(n); 120 for(int i=0; i<n; i++) cin >> a[i]; 121 122 ll ans = 1e9, sum = 0; 123 124 for(int i=0; i<n; i++) 125 { 126 sum += a[i]; 127 ans = min(ans, sum / (i + 1)); 128 129 cout << ans << " "; 130 } 131 132 cout << "\n"; 133 } 134 } 135 ``` 136 137 **Rate The Problem!** 138 139 * Good Problem 140 * Okay Problem 141 * Bad Problem 142 * Didn't Solve 143 144 Problem [C1](https://codeforces.com/contest/2232/problem/C1), [C2](https://codeforces.com/contest/2232/problem/C2) — Seating Arragement 145 146 Problem Idea: [36champ](/profile/36champ "International Master 36champ") 147 Solution Idea: [36champ](/profile/36champ "International Master 36champ"), [Proof_by_QED](/profile/Proof_by_QED "Master Proof_by_QED") 148 149 There are two solutions to this problem presented below. 150 151 **Hint 1** 152 153 If we fixed the number of ambiverts that behave as introverts, what is the best way to assign who is introverted/extroverted? 154 155 **Solution (C1)** 156 157 It is always better to assign the prefix of ambiverts as introverts and the rest as extroverts, because if the number of introverts is fixed, then it is better to have introverts as early as possible. 158 159 For this subtask, it is possible to brute-force the number of ambiverts acting as introverts and find the answer in $O(n^2)$. 160 161 **Code (C1)** 162 163 ``` 164 #include <bits/stdc++.h> 165 #define pb push_back 166 167 using namespace std; 168 169 typedef long long ll; 170 typedef vector<int> vi; 171 typedef vector<vi> vvi; 172 typedef vector<ll> vll; 173 typedef vector<vll> vvll; 174 typedef pair<int, int> pii; 175 typedef pair<ll, ll> pll; 176 177 ll s, t; 178 179 ll eval(string &S, int m) 180 { 181 ll T = 0, ans = 0; 182 183 for(char c: S) 184 { 185 if(c == 'I') 186 { 187 if(T < t) 188 { 189 T++; 190 ans++; 191 } 192 } 193 else if(c == 'E') 194 { 195 if(ans < T * s) ans++; 196 } 197 else 198 { 199 if(m-->0) 200 { 201 if(T < t) 202 { 203 T++; 204 ans++; 205 } 206 } 207 else 208 { 209 if(ans < T * s) ans++; 210 } 211 } 212 } 213 214 return ans; 215 } 216 217 int main() 218 { 219 ios_base::sync_with_stdio(false); 220 cin.tie(nullptr); 221 cout.tie(nullptr); 222 223 int T = 1; 224 cin >> T; 225 while(T-->0) 226 { 227 int n; 228 cin >> n >> t >> s; 229 230 string S; 231 cin >> S; 232 233 int l = 0, r = 0; 234 for(char c: S) if(c == 'A') r++; 235 236 ll ans = 0; 237 for(int i=l; i<=r; i++) ans = max(ans, eval(S, i)); 238 239 cout << ans << "\n"; 240 } 241 } 242 ``` 243 244 **Rate The Problem! (C1)** 245 246 * Good Problem 247 * Okay Problem 248 * Bad Problem 249 * Didn't Solve 250 251 **Hint 2** 252 253 Assigning more ambiverts as introverts has a diminishing return. 254 255 **Hint 3** 256 257 Let $f(i)$ be the maximum number of people seated if the first $i$ ambiverts act as introverts. If $f(i + 1) \lt f(i + 2)$, what is the relation ship between $f(i)$ and $f(i + 1)$. 258 259 **Solution (C2)** 260 261 Let $f(i)$ be the maximum number of people seated if the first $i$ ambiverts act as introverts. We will first prove that if $f(i + 1) \lt f(i + 2)$, then $f(i) \lt f(i + 1)$. 262 263 Consider the situation where everyone is either an introvert or an extrovert, then we can simply use the greedy algorithm to solve this situation. 264 265 Suppose that $f(i + 1) \lt f(i + 2)$, then there are two possible scenarios: 266 267 Case 1: The $(i + 2)$-th ambivert is not seated when they are extroverted, but is seated when they are introverted. 268 269 Thus, when the first $i$ or $i + 1$ ambiverts are introverted, only $i$ or $i + 1$ tables are all seated, and the rest of the tables are empty. Thus, $f(i) \lt f(i + 1)$. 270 271 Case 2: The $(i + 2)$-th ambivert is seated when they are extroverted, and is still seated when they are introverted. 272 273 Since $f(i + 1) \lt f(i + 2)$, we know that someone previously unseated has to take the $(i+2)$-th ambivert's original seat, and since this person is originally unseated, this means the first $i + 1$ tables have to be fully seated. Therefore, $f(i) \lt f(i + 1)$. 274 275 Next, since we know that $f$ is strictly increasing before it plateaus/decreases. We can find the peak by finding the least $i$ that has $f(i) \geq f(i + 1)$. 276 277 Using binary search to find the optimal number of ambiverts acting as introverts reduces the time complexity of this problem down to $O(n \log n)$. 278 279 **Code (C2)** 280 281 ``` 282 #include <bits/stdc++.h> 283 #define pb push_back 284 285 using namespace std; 286 287 typedef long long ll; 288 typedef vector<int> vi; 289 typedef vector<vi> vvi; 290 typedef vector<ll> vll; 291 typedef vector<vll> vvll; 292 typedef pair<int, int> pii; 293 typedef pair<ll, ll> pll; 294 295 ll s, t; 296 297 ll eval(string &S, int m) 298 { 299 ll T = 0, ans = 0; 300 301 for(char c: S) 302 { 303 if(c == 'I') 304 { 305 if(T < t) 306 { 307 T++; 308 ans++; 309 } 310 } 311 else if(c == 'E') 312 { 313 if(ans < T * s) ans++; 314 } 315 else 316 { 317 if(m-->0) 318 { 319 if(T < t) 320 { 321 T++; 322 ans++; 323 } 324 } 325 else 326 { 327 if(ans < T * s) ans++; 328 } 329 } 330 } 331 332 return ans; 333 } 334 335 int main() 336 { 337 ios_base::sync_with_stdio(false); 338 cin.tie(nullptr); 339 cout.tie(nullptr); 340 341 int T = 1; 342 cin >> T; 343 while(T-->0) 344 { 345 int n; 346 cin >> n >> t >> s; 347 348 string S; 349 cin >> S; 350 351 int l = 0, r = 0; 352 for(char c: S) if(c == 'A') r++; 353 354 while(l < r) 355 { 356 int m = (l + r) / 2; 357 358 int x = eval(S, m), y = eval(S, m + 1); 359 360 if(x < y) l = m + 1; 361 else r = m; 362 } 363 364 cout << eval(S, l) << "\n"; 365 } 366 } 367 ``` 368 369 **Alternate Hint 1** 370 371 If we fixed the number of ambiverts that behave as introverts, what is the best way to assign who is introverted/extroverted? 372 373 **Alternate Hint 2** 374 375 If there are no ambiverts, we can solve this problem greedily. How can we use the greedy algorithm here? 376 377 **Alternate Solution** 378 379 We will process each person one by one and keep track of the minimum and maximum number of tables occupied. 380 381 Let $l$, $r$, and $ans$ be the minimum, maximum number of tables occupied, and the maximum number of people seated, respectively. 382 383 If we encounter an introvert, we want to assign them an empty table. Therefore, if $l \lt t$, we increase $l, r$ by $1$ capping at $t$ and increase $ans$ by $1$. 384 385 If we encounter an extrovert, we want to assign them a non-empty table. Therefore, we can increase $ans$ by $1$ if there is an empty seat ($r * s \gt ans$). You also need to make sure that after this person is seated, $l$ is updated accordingly (increased by $1$ if $l * s \lt ans$ now). 386 387 If we encounter an ambivert, we have to execute both strategies above. 388 389 This solution only takes $O(n)$. 390 391 **Alternate Code** 392 393 ``` 394 #include <bits/stdc++.h> 395 #define pb push_back 396 397 using namespace std; 398 399 typedef long long ll; 400 typedef vector<int> vi; 401 typedef vector<vi> vvi; 402 typedef vector<ll> vll; 403 typedef vector<vll> vvll; 404 typedef pair<int, int> pii; 405 typedef pair<ll, ll> pll; 406 407 int main() 408 { 409 ios_base::sync_with_stdio(false); 410 cin.tie(nullptr); 411 cout.tie(nullptr); 412 413 int T = 1; 414 cin >> T; 415 while(T-->0) 416 { 417 ll n, s, t; 418 cin >> n >> t >> s; 419 420 string S; 421 cin >> S; 422 423 ll l = 0, r = 0, ans = 0; 424 for(char c: S) 425 { 426 if(c == 'A') 427 { 428 if(t * s == ans) continue; 429 430 ans++; 431 if(ans > l * s) l++; 432 r = min(t, r + 1); 433 } 434 else if(c == 'I') 435 { 436 if(l == t) continue; 437 438 ans++; 439 l++; 440 r = min(t, r + 1); 441 } 442 else if(c == 'E') 443 { 444 if(ans == r * s) continue; 445 446 ans++; 447 if(ans > l * s) l++; 448 } 449 } 450 451 cout << ans << "\n"; 452 } 453 } 454 ``` 455 456 **Rate The Problem! (C2)** 457 458 * Good Problem 459 * Okay Problem 460 * Bad Problem 461 * Didn't Solve 462 463 [Problem D — Magical Tiered Cake](https://codeforces.com/contest/2232/problem/D) 464 465 Problem Idea: [36champ](/profile/36champ "International Master 36champ") 466 Solution Idea: [36champ](/profile/36champ "International Master 36champ") 467 468 **Hint 1** 469 470 Can you solve the Tower of Hanoi? 471 472 **Hint 2** 473 474 If $a_i \geq i$, then it is impossible because there cannot be at least $i$ rings on the $i$-th smallest ring in the first place. 475 476 **Hint 3** 477 478 If $a_i \lt i$ for all $i$, it is always possible. 479 480 **Solution** 481 482 If possible, we can move the cake in at most $2^n - 1$ moves with a recursive algorithm similar to the classic Tower of Hanoi. 483 484 Base Case ($1$ layer): Perform one move to move it from location $1$ to $3$. 485 486 Inductive step ($k$ layers): Let $f(i)$ be the number of moves to solve the first $i$ layers. By strong induction, $f(i) \leq 2 ^ i - 1$. 487 488 Case 1: $a_k = 0$ 489 490 This takes $f(k - 1)$ moves to move the first $k - 1$ layers to location $2$, $1$ move to move the $k$-th layer to location $3$, and another $f(k - 1)$ moves to move the first $k-1$ layers to location $3$. 491 492 Total: $2 * f(k - 1) + 1 \leq 2 ^ k - 1$ moves 493 494 Case 2: $a_k \geq 1$ 495 496 This takes $f(k - 1 - a_k)$ moves to move the first $k - 1 - a_k$ layers to location $2$, $1$ move to move the $k$-th layer to location $3$, $f(k - 1 - a_k)$ moves to move the first $k - 1 - a_k$ layers back to location $1$, and another $f(k - 1)$ moves to move the first $k - 1$ layers to location $3$. 497 498 Total: $2 * f(k - 1 - a_k) + f(k - 1) + 1 \leq 2 * f(k - 2) + f(k - 1) + 1 \leq 2 ^ k - 2 \leq 2 ^ k - 1$ moves. 499 500 Therefore, this problem can be solved in $O(2^n)$ 501 502 **Code** 503 504 ``` 505 #include <bits/stdc++.h> 506 #define pb push_back 507 508 using namespace std; 509 510 typedef long long ll; 511 typedef vector<int> vi; 512 typedef vector<vi> vvi; 513 typedef vector<ll> vll; 514 typedef vector<vll> vvll; 515 typedef pair<int, int> pii; 516 typedef pair<ll, ll> pll; 517 518 int n; 519 vi a(20); 520 vvi op; 521 522 void moveall(int k, int s, int t) 523 { 524 if(k <= 0) return; 525 int u = 6 - s - t; 526 527 if(a[k - 1] == 0) 528 { 529 moveall(k - 1, s, u); 530 op.pb({k, s, t}); 531 moveall(k - 1, u, t); 532 } 533 else 534 { 535 moveall(k - 1 - a[k - 1], s, u); 536 op.pb({k, s, t}); 537 moveall(k - 1 - a[k - 1], u, s); 538 moveall(k - 1, s, t); 539 } 540 } 541 542 int main() 543 { 544 ios_base::sync_with_stdio(false); 545 cin.tie(nullptr); 546 cout.tie(nullptr); 547 548 int t; 549 cin >> t; 550 551 while(t-->0) 552 { 553 cin >> n; 554 555 for(int i=0; i<n; i++) cin >> a[i]; 556 557 bool ok = true; 558 for(int i=0; i<n; i++) if(a[i] > i) ok = false; 559 560 if(!ok) 561 { 562 cout << "NO\n"; 563 continue; 564 } 565 566 cout << "YES\n"; 567 568 moveall(n, 1, 3); 569 570 cout << op.size() << "\n"; 571 for(vi p: op) cout << p[0] << " " << p[1] << " " << p[2] << "\n"; 572 op.clear(); 573 } 574 } 575 ``` 576 577 **Rate The Problem!** 578 579 * Good Problem 580 * Okay Problem 581 * Bad Problem 582 * Didn't Solve 583 584 [Problem E — Snaking Arrangement](https://codeforces.com/contest/2232/problem/E) 585 586 Problem Idea: [36champ](/profile/36champ "International Master 36champ") 587 Solution Idea: [36champ](/profile/36champ "International Master 36champ") 588 589 **Hint 1** 590 591 Look at the anti-diagonals (bottom left -> top right). 592 593 **Hint 2** 594 595 There is a bijection between the snaking arrangement and the permutation of $[1, 2, \dots, n]$. 596 597 **Solution** 598 599 By looking at anti-diagonals of the grid, we can observe that the first anti-diagonal (just the top-left cell) only contains the snake of length $n$. Then, the next anti-diagonal contains the snake of length $n-1$ and $n$, and so on. Therefore, by looking at the $i$-th and $(i+1)$-th anti-diagonals, we know the relative position between the $(n - i)$-th snake and all snakes longer than it. 600 601 For example, 602 603 3 3 ? 604 ? 3 3 605 ? ? 3 606 607 has alternate diagonals 3, ? 3, ? 3 ?. 608 609 3 -> ? 3. Know that 2 is to the left of 3. ? 3 -> ? 3 ?. Know that 1 is to the right of 3. 610 611 This can now be solved comfortably in $O(n^2)$ or in $O(n)$ with more optimization. 612 613 **Code** 614 615 ``` 616 #include <bits/stdc++.h> 617 #define pb push_back 618 619 using namespace std; 620 621 typedef long long ll; 622 typedef vector<int> vi; 623 typedef vector<vi> vvi; 624 typedef vector<ll> vll; 625 typedef vector<vll> vvll; 626 typedef pair<int, int> pii; 627 typedef pair<ll, ll> pll; 628 629 const ll N = 1000000007; 630 #define MAX_N 200005 631 632 vll fac(MAX_N, 1); 633 634 int main() 635 { 636 ios_base::sync_with_stdio(false); 637 cin.tie(nullptr); 638 cout.tie(nullptr); 639 640 for(int i=2; i<MAX_N; i++) fac[i] = (i * fac[i - 1]) % N; 641 642 int t = 1; 643 cin >> t; 644 while(t-->0) 645 { 646 ll n, k; 647 cin >> n >> k; 648 649 vvi D; vi d; 650 bool ok = true; 651 652 for(int i=0; i<k; i++) 653 { 654 ll s, r, c; 655 cin >> s >> r >> c; 656 657 //Starting Point Check 658 if(s / 2 + r + c != n + 1) ok = false; 659 660 vector<pii> V; 661 V.pb({r, c}); 662 663 if(s != 1) 664 { 665 string S; 666 cin >> S; 667 668 for(char C: S) 669 { 670 if(C == 'R') 671 { 672 c++; 673 V.pb({r, c}); 674 } 675 else 676 { 677 r++; 678 V.pb({r, c}); 679 } 680 } 681 682 //Symmetry Check 683 for(int i=0; i<s/2; i++) if(V[i].second - V[i].first != V[s - i - 1].second - V[s - i - 1].first) ok = false; 684 } 685 686 //Info Handling 687 if(!ok) continue; 688 689 if(D.size() < s / 2 + 1) 690 { 691 D.resize(s / 2 + 1); 692 d.resize(s / 2 + 1); 693 } 694 695 for(int i=0; i<s/2+1; i++) D[i].pb(V[s/2-i].second); 696 d[s / 2] = V[0].second; 697 } 698 699 if(!ok) 700 { 701 cout << "0\n"; 702 continue; 703 } 704 705 int x = D.size(); 706 for(int i=0; i<x; i++) sort(D[i].begin(), D[i].end()); 707 708 D.pb({}); 709 710 ll ans = 1; 711 for(int i=0; i<x; i++) 712 { 713 if(!ok) 714 { 715 ans = 0; 716 continue; 717 } 718 719 bool dec = false; 720 721 int l = 0, k = 0; 722 723 while(l + k < D[i].size()) 724 { 725 if(D[i][l + k] == d[i]) 726 { 727 k++; 728 continue; 729 } 730 731 if(D[i][l + k] == D[i + 1][l]) 732 { 733 if(dec) 734 { 735 ok = false; 736 break; 737 } 738 } 739 else if(D[i][l + k] - 1 == D[i + 1][l]) 740 { 741 if(!dec) 742 { 743 if(l + k == 0 && d[i] == 0) ans *= D[i][l + k] - 1; 744 else if(l + k != 0 && d[i] == 0) ans *= D[i][l + k] - D[i][l + k - 1] - 1; 745 ans %= N; 746 } 747 748 dec = true; 749 } 750 else 751 { 752 ok = false; 753 break; 754 } 755 756 l++; 757 } 758 759 if(!dec) 760 { 761 if(d[i] == 0) ans *= n - i - D[i][l + k - 1]; 762 ans %= N; 763 } 764 } 765 766 ans *= fac[n - x]; 767 ans %= N; 768 769 cout << ans << "\n"; 770 } 771 } 772 ``` 773 774 **Rate The Problem!** 775 776 * Good Problem 777 * Okay Problem 778 * Bad Problem 779 * Didn't Solve 780 781 [Problem F — The Cake Is a Lie](https://codeforces.com/contest/2232/problem/F) 782 783 Problem Idea: [36champ](/profile/36champ "International Master 36champ") 784 Solution Idea: [36champ](/profile/36champ "International Master 36champ") 785 786 **Hint 1** 787 788 Extended Euclidean Algorithm 789 790 **Solution** 791 792 Formally, we have the system of equations: 793 794 $a * x_1 = k$ 795 796 $a * x_2 + b * x_1 = k$ 797 798 $a * x_3 + b * x_2 = k \dots$ 799 800 where $x_i$ are non-negative integers. 801 802 If $k$ is not divisible by $gcd(a, b)$, then the answer is $0$. 803 804 Now, let's assume that $gcd(a, b) = 1$ since you can divide $a$, $b$, and $k$ by $gcd(a, b)$. If $a = b = 1$, then the answer is $n$. 805 806 Otherwise, we will compute $x_1$, $x_2$, ... until $x_i$ becomes negative or non-integer. ($x_{m+1}$ is not a non-negative integer). 807 808 So, we know that $a * x_{m + 1} + b * x_m$ can't be equal to $k$. Therefore, $x_{m + 1}$ is independent from $x_m$. 809 810 Next, we want to maximize the number of equations in the following form that you can solve all at the same time. $a * x_{m + 2} + b * x_{m + 1} = k$ 811 812 $a * x_{m + 3} + b * x_{m + 2} = k$ 813 814 $a * x_{m + 4} + b * x_{m + 3} = k \dots$ 815 816 Looking at the first $2$ equations, if you can solve both of them, then $a * x_{m + 3} + b * x_{m + 2} = a * x_{m + 2} + b * x_{m + 1}$ or $a * (x_{m + 3} - x_{m + 2}) = b * (x_{m + 1} - x_{m + 2})$ 817 818 Therefore, $b | x_{m + 3} - x_{m + 2}$ and $a | x_{m + 2} - x_{m + 1}$ Furthermore, $b | x_{m + 4} - x_{m + 3}$ and $a | x_{m + 3} - x_{m + 2}$ So, $b^2 | x_{m + 4} - x_{m + 3}$, $ab | x_{m + 3} - x_{m + 2}$ and $a^2 | x_{m + 2} - x_{m + 1}$. This can be extended further using induction. 819 820 Suppose $a \gt b$, consider $(a + b) * x_{m + 2} + b * (x_{m + 1} - x_{m + 2}) = (a + b) * x_{m + 2} + b * (a ^ v) * y$. If this can be equal to k when both $x_{m + 2}$ and $x_{m + 1} = a^v * y + x_{m + 2}$ are non-negative integers, then we can solve $v + 1$ equations at once. 821 822 If $k$ is divisible by $a + b$, then $v$ is infinite. Otherwise, $y$ is positive, so you can Binary Search for $v$. (Linear search should be fine too) 823 824 The $a \lt b$ case can be handled similarly. 825 826 After you have $m$ and $v$, you can use them to maximize your score. 827 828 **Code** 829 830 ``` 831 #include <bits/stdc++.h> 832 #define pb push_back 833 834 using namespace std; 835 836 typedef long long ll; 837 typedef vector<int> vi; 838 typedef vector<vi> vvi; 839 typedef vector<ll> vll; 840 typedef vector<vll> vvll; 841 typedef pair<int, int> pii; 842 typedef pair<ll, ll> pll; 843 844 // function to find the solution 845 ll gcd(ll a, ll b, ll &x, ll &y){ 846 if(b == 0){ 847 x= 1; y = 0; 848 return a; 849 } 850 ll x1, y1; 851 ll d = gcd(b, a%b, x1, y1); 852 x = y1; 853 y = x1 - y1*(a/b); 854 return d; 855 } 856 857 int main() 858 { 859 ios_base::sync_with_stdio(false); 860 cin.tie(nullptr); 861 cout.tie(nullptr); 862 863 int t = 1; 864 cin >> t; 865 while(t-->0) 866 { 867 ll n, a, b, k; 868 cin >> n >> a >> b >> k; 869 870 ll g = __gcd(a, b); 871 872 if(k % g != 0) 873 { 874 cout << "0\n"; 875 continue; 876 } 877 878 a /= g; b /= g; k /= g; 879 880 if(a == 1 && b == 1) 881 { 882 cout << n << "\n"; 883 continue; 884 } 885 886 /// STEP 1 887 ll ans = 0; 888 if(k % a == 0) 889 { 890 ans++; n--; 891 ll x = k / a; 892 while(n > 0) 893 { 894 if(k - (x * b) < 0 || (k - x * b) % a != 0) break; 895 896 x = (k - x * b) / a; 897 ans++; 898 n--; 899 } 900 } 901 902 /// STEP 2 903 ll v = 0; 904 if(k % (a + b) == 0) v = 1e9; 905 else 906 { 907 if(a < b) swap(a, b); 908 /// SOLVE (a + b) x + b * a^v y = k 909 ll m = b; 910 while(true) 911 { 912 ll x, y; 913 gcd(a + b, m, x, y); 914 915 if(x < 0) {x += m; y -= a + b;} 916 x *= k; y *= k; 917 ll d = x / m; 918 x -= d * m; y += d * (a + b); 919 //cout << x << " " << y << "\n"; 920 //getchar(); 921 922 if(m / b * y + x < 0) break; 923 924 /// Secondary Check 925 bool ok = true; 926 ll x1 = x, x2 = m / b * y + x; 927 for(int _=0; _<v; _++) 928 { 929 if(a * x1 + b * x2 != k) ok = false; 930 931 if((k - b * x1) % a) 932 { 933 ok = false; 934 break; 935 } 936 937 x2 = x1; 938 x1 = (k - b * x1) / a; 939 } 940 941 if(!ok) break; 942 943 v++; 944 945 if(a > k / m) break; 946 m *= a; 947 } 948 } 949 950 //cout << "! " << v << "\n"; 951 952 cout << ans + (n - (n + v) / (v + 1)) << "\n"; 953 } 954 } 955 ``` 956 957 **Rate The Problem!** 958 959 * Good Problem 960 * Okay Problem 961 * Bad Problem 962 * Didn't Solve