codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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