codeforces-scrape

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

2179.md (19003B)


      1 Source: https://codeforces.com/blog/entry/149406
      2 
      3 # [2179A - Blackslex and Password](/contest/2179/problem/A "Codeforces Round 1071 (Div. 3)")
      4 
      5 Author: [IceBorworntat](/profile/IceBorworntat "Candidate Master IceBorworntat")
      6 
      7 **Hint 1**
      8 
      9 Think about the indices that have the same remainder after division by $x$.
     10 
     11 **Solution**
     12 
     13 Consider the subsequence formed from the indices that have the same remainder after division by $x$. There are $x$ such subsequences. Each subsequence contains distinct characters, so the maximum length of such subsequences is $k$. As such, the minimum string length that cannot be constructed is $n = kx+1$.
     14 
     15 Time complexity: $\mathcal{O}(1)$
     16 
     17 **Implementation (Python)**
     18 
     19 ```
     20 t = int(input())
     21 for _ in range(t):
     22     k, x = [int(i) for i in input().split()]
     23     print(k*x+1)
     24 ```
     25 
     26 # [2179B - Blackslex and Showering](/contest/2179/problem/B "Codeforces Round 1071 (Div. 3)")
     27 
     28 Author: [spycoderyt](/profile/spycoderyt "Expert spycoderyt")
     29 
     30 **Hint 1**
     31 
     32 First observe that it is always helpful to remove a floor. Now the question becomes which floor to remove.
     33 
     34 **Solution**
     35 
     36 You can simply simulate the process of removing any possible floor. To do this efficiently, compute the current time taken and consider the change to the time taken if a floor is removed. If we remove floor $i$ where $i \neq 1$ and $i \neq n$, then the differences $|a[i] - a[i-1]|$ and $|a[i+1] - a[i]|$ are removed and the difference $|a[i-1] - a[i+1]|$ is added. If $i = 1$ or $i = n$, only the adjacent difference is removed.
     37 
     38 Time complexity: $\mathcal{O}(n)$
     39 
     40 **Implementation (C++)**
     41 
     42 ```
     43 #include <bits/stdc++.h>
     44  
     45 using namespace std;
     46 typedef long long ll;
     47  
     48 void test_case_run() {
     49     int n;
     50     cin >> n;
     51     
     52     ll a[n+1];
     53     for (int i = 1; i <= n; i++) cin >> a[i];
     54     
     55     ll sum = 0;
     56     for (int i = 2; i <= n; i++) sum += abs(a[i]-a[i-1]);
     57     
     58     ll ans = min(sum - abs(a[2]-a[1]), sum - abs(a[n]-a[n-1]));
     59     for (int i = 2; i < n; i++) {
     60         ans = min(ans, sum - abs(a[i+1]-a[i]) - abs(a[i]-a[i-1]) + abs(a[i+1]-a[i-1]));
     61     }
     62     
     63     cout << ans << "\n";
     64 }
     65  
     66 int main() {
     67     ios_base::sync_with_stdio(false);
     68     cin.tie(NULL);
     69     
     70     int t;
     71     cin >> t;
     72     while (t--) test_case_run();
     73     
     74     return 0;
     75 }
     76 ```
     77 
     78 # [2179C - Blackslex and Number Theory](/contest/2179/problem/C "Codeforces Round 1071 (Div. 3)")
     79 
     80 Author: [omsincoconut](/profile/omsincoconut "Master omsincoconut")
     81 
     82 **Hint 1**
     83 
     84 Making everying zeros works often.
     85 
     86 **Hint 2**
     87 
     88 Sometimes, it's better to make all numbers something else that's not zero.
     89 
     90 **Hint 3**
     91 
     92 Following Hint 2, if we don't make everything zero, then what's our target number?
     93 
     94 **Solution**
     95 
     96 Sort the array from small to large.
     97 
     98 We can mod every number in the array by itself, and this would require $k = a_1$.
     99 
    100 For a larger value of $k$, we cannot modify the value of $a_1$, so every number must be made into $a_1$. We can mod $a_i$ with $a_i - a_1$, using $k = a_2 - a_1$.
    101 
    102 The answer is thus $\max(a_1, a_2 - a_1)$.
    103 
    104 Time complexity: $\mathcal{O}(n)$ or $\mathcal{O}(n \log n)$ depending on implementation.
    105 
    106 **Implementation (Python)**
    107 
    108 ```
    109 for test_case in range(int(input())):
    110     n = int(input())
    111     a = sorted([int(_) for _ in input().split()])
    112     print(max(a[0], a[1]-a[0]))
    113 ```
    114 
    115 # [2179D - Blackslex and Penguin Civilization](/contest/2179/problem/D "Codeforces Round 1071 (Div. 3)")
    116 
    117 Author: [omsincoconut](/profile/omsincoconut "Master omsincoconut")
    118 
    119 **Hint 1**
    120 
    121 Ignore the lexicographically minimum condition first. Can you find any permutation that maximizes $S(p)$? Can you explain why the permutation maximizes $S(p)$?
    122 
    123 **Hint 2**
    124 
    125 There's an easy permutation that maximizes $S(p)$.
    126 
    127 **The permutation**
    128 
    129 $p_i = 2^n-i-1$
    130 
    131 **Hint 3**
    132 
    133 There are at most $2^{n-i}$ prefixes of the permutation that has the popcount of the bitwise AND be at least $i$.
    134 
    135 **Why?**
    136 
    137 For a popcount of a prefix to exceed $i$, you'll need to fix $i$ bits to be all ones, so there are only $n-i$ bits left to do other things to.
    138 
    139 **Solution**
    140 
    141 Read all hints. Now, look at this sentence in Hint 3.
    142 
    143 "For a popcount of a prefix to exceed $i$, you'll need to fix $i$ bits to be all ones."
    144 
    145 We will fix the $i$ lowest-value bits, and iterate the other bits lexicographically minimally.
    146 
    147 Here's an example for $n=3$:
    148 
    149 **1 1 1** = 7
    150 
    151 0 **1 1** = 3
    152 
    153 0 0 **1** = 1
    154 
    155 1 0 **1** = 5
    156 
    157 0 0 0 = 0
    158 
    159 0 1 0 = 2
    160 
    161 1 0 0 = 4
    162 
    163 1 1 0 = 6
    164 
    165 For a clean implementation, note that iterating the unfixed bits is basically iterating even numbers.
    166 
    167 Time complexity: $\mathcal{O}(2^n)$.
    168 
    169 **Implementation (Python)**
    170 
    171 ```
    172 t = int(input())
    173 for _ in range(t):
    174     n = int(input())
    175     print(2**n - 1, end = ' ')
    176     for i in range(1, n+1):
    177         for j in range(0, 2**i, 2):
    178             print(j*2**(n-i) + 2**(n-i) - 1, end = ' ')
    179     print()
    180 ```
    181 
    182 # [2179E - Blackslex and Girls](/contest/2179/problem/E "Codeforces Round 1071 (Div. 3)")
    183 
    184 Author: [spycoderyt](/profile/spycoderyt "Expert spycoderyt")
    185 
    186 **Hint 1**
    187 
    188 Denote the party that is supposed to win a district as the 'designated winner.' A minimum population $p_i$ for each district and a strict majority condition creates a lower bound on the number of votes from the designated winner. What is this lower bound?
    189 
    190 **Hint 2**
    191 
    192 The lower bound is $\lfloor \frac{p_i}{2} \rfloor + 1$.
    193 
    194 **Hint 3**
    195 
    196 What happens if at least one pair of districts has a different designated winner?
    197 
    198 **Hint 4**
    199 
    200 What happens if that is not true; i.e all districts have the same designated winner?
    201 
    202 **Solution**
    203 
    204 Consider the process of constructing a solution, even though we will not explicitly construct it in the code. First note that if $x+y \lt \sum p_i$, then it is impossible.
    205 
    206 Then if $x+y \geq \sum p_i$, we start off by filling each district with the lower bound number $\lfloor \frac{p_i}{2} \rfloor + 1$ of votes from the designated winner. If we run out of votes from either party then the answer is no. After that we have two cases:
    207 
    208 Case 1: if there is at least one pair of districts with different designated winners, we can arbitrarily fill (with any color) each district up to its minimum capacity $p_i$, and then allocate the rest of the votes to a district where that vote's party is supposed to win in. Therefore we only need to check if the lower bound on designated winner votes can be achieved.
    209 
    210 Case 2: if all districts have the same designated winner, sometimes there are too many votes from the 'losing' party for a solution to exist. The minimum votes the winning party must have over the losing party is $n$, because we need a strict majority in every district, which corresponds to a vote difference of at least 1 in each district. WLOG let $x$ be the votes from the winning party and $y$ be the votes from the losing party, and we simply check if $x \geq y + n$.
    211 
    212 Time complexity: $\mathcal{O}(n)$
    213 
    214 **Implementation (C++)**
    215 
    216 ```
    217 #include <bits/stdc++.h>
    218  
    219 using namespace std;
    220 typedef long long ll;
    221  
    222 void test_case_run() {
    223     int n;
    224     ll x, y;
    225     cin >> n >> x >> y;
    226     
    227     string s;
    228     cin >> s;
    229     s = '.'+s;
    230     
    231     ll p[n+1];
    232     for (int i = 1; i <= n; i++) cin >> p[i];
    233     
    234     if (accumulate(p+1, p+n+1, 0LL) > x+y) {
    235         cout << "NO\n";
    236         return;
    237     }
    238     
    239     if (s == "." + string(n, '0') || s == "." + string(n, '1')) {
    240         if (s == "." + string(n, '1')) {
    241             swap(x, y);
    242         }
    243         
    244         ll x_need = 0;
    245         for (int i = 1; i <= n; i++) {
    246             x_need += p[i]/2 + 1;
    247         }
    248         
    249         if (x < x_need || x < y+n) {
    250             cout << "NO\n";
    251         } else {
    252             cout << "YES\n";
    253         }
    254         
    255         return;
    256     }
    257     
    258     ll x_need = 0, y_need = 0;
    259     for (int i = 1; i <= n; i++) {
    260         if (s[i] == '0') {
    261             x_need += p[i]/2 + 1;
    262         } else {
    263             y_need += p[i]/2 + 1;
    264         }
    265     }
    266     if (x >= x_need && y >= y_need) cout << "YES\n";
    267     else cout << "NO\n";
    268 }
    269  
    270 int main() {
    271     ios_base::sync_with_stdio(false);
    272     cin.tie(NULL);
    273     
    274     int t;
    275     cin >> t;
    276     while (t--) test_case_run();
    277     
    278     return 0;
    279 }
    280 ```
    281 
    282 # [2179F - Blackslex and Another RGB Walking](/contest/2179/problem/F "Codeforces Round 1071 (Div. 3)")
    283 
    284 Author: [omsincoconut](/profile/omsincoconut "Master omsincoconut")
    285 
    286 **Hint 1**
    287 
    288 Solve for a line graph.
    289 
    290 **Hint 2**
    291 
    292 Solve for a tree.
    293 
    294 **Hint 3**
    295 
    296 Does the exact same thing work? Why?
    297 
    298 **Solution**
    299 
    300 In the first run, use breadth-first search to find the distance of each vertex from vertex $1$. Color a vertex red if the distance is dividsible by $3$, green if the remainder of the division by $3$ is $1$, and blue if the remainder of the division by $3$ is $2$.
    301 
    302 Note that if two vertices are connected by an edge, then their distances differ by no more than $1$. In fact, the distances differ by exactly $1$ for a bipartite graph.
    303 
    304 **Why?**
    305 
    306 Consider two adjacent vertices has the same distance. Connect the shortest paths from the two vertices to vertex $1$ with the edge connecting the two vertices. We can see that an odd cycle would form.
    307 
    308 In the second run, move anywhere if every neighbor have the same color. Otherwise, note that
    309 
    310 * If the neighbors are red and green, then B is at a blue vertex, and should move to any green vertex.
    311 * If the neighbors are green and blue, then B is at a red vertex, and should move to any blue vertex.
    312 * If the neighbors are blue and red, then B is at a green vertex, and should move to any red vertex.
    313 
    314 Time complexity: $\mathcal{O}(n+m)$
    315 
    316 **Implementation (C++)**
    317 
    318 ```
    319 #include <bits/stdc++.h>
    320  
    321 using namespace std;
    322 const int INF = 1e9;
    323  
    324 void test_first() {
    325     int n, m;
    326     cin >> n >> m;
    327     
    328     vector<vector<int>> edge(n+1);
    329     for (int i = 1; i <= m; i++) {
    330         int a, b;
    331         cin >> a >> b;
    332         edge[a].push_back(b);
    333         edge[b].push_back(a);
    334     }
    335     
    336     vector<int> dist(n+1, INF);
    337     dist[1] = 0;
    338         
    339     queue<int> bfs;
    340     bfs.push(1);
    341     while (!bfs.empty()) {
    342         int a = bfs.front();
    343         bfs.pop();
    344             
    345         for (int b : edge[a]) {
    346             if (dist[b] > dist[a] + 1) {
    347                 dist[b] = dist[a] + 1;
    348                 bfs.push(b);
    349             }
    350         }
    351     }
    352     
    353     for (int i = 1; i <= n; i++) cout << "rgb"[dist[i]%3];
    354     cout << "\n";
    355 }
    356  
    357 void test_second() {
    358     int dv;
    359     string color;
    360     cin >> dv >> color;
    361     
    362     bool fr = false, fg = false, fb = false;
    363     for (char c : color) {
    364         if (c == 'r') fr = true;
    365         if (c == 'g') fg = true;
    366         if (c == 'b') fb = true;
    367     }
    368     
    369     if ((int)fr + (int)fg + (int)fb == 1) {
    370         cout << 1 << "\n";
    371         return;
    372     }
    373     
    374     char target;
    375     if (fr && fg) target = 'g';
    376     if (fg && fb) target = 'b';
    377     if (fb && fr) target = 'r';
    378     
    379     for (int i = 0; i < dv; i++) {
    380         if (color[i] == target) {
    381             cout << i+1 << "\n";
    382             return;
    383         }
    384     }
    385 }
    386  
    387 int main() {
    388     ios_base::sync_with_stdio(false);
    389     cin.tie(NULL);
    390     
    391     string player;
    392     int t;
    393     cin >> player >> t;
    394     
    395     if (player == "first") while (t--) test_first();
    396     else while (t--) {
    397         int q;
    398         cin >> q;
    399         while (q--) test_second();
    400     }
    401     
    402     return 0;
    403 }
    404 ```
    405 
    406 # [2179G - Blackslex and Penguin Migration](/contest/2179/problem/G "Codeforces Round 1071 (Div. 3)")
    407 
    408 Author: [omsincoconut](/profile/omsincoconut "Master omsincoconut")
    409 
    410 **Hint 1**
    411 
    412 Think about corners.
    413 
    414 **Hint 2**
    415 
    416 Think about non-opposite corners.
    417 
    418 **Hint 3**
    419 
    420 Think about cells furthest from another cell.
    421 
    422 **Solution**
    423 
    424 The idea is that distance from two non-opposite corners uniquely determine the position.
    425 
    426 **Why?**
    427 
    428 Note that the answer can be rotated or flipped and still be correct. Let us assume the two corners are at position $(1, 1)$ and position $(1, n)$. Let the distance from the two corners be $d_1$ and $d_2$. Assume that the cell is on $(x, y)$. Then, we can write
    429 
    430 $|1-x| + |1-y| = x+y-2 = d_1$ $|1-x| + |n-y| = x-y+n-1 = d_2$
    431 
    432 We can solve the system of equations to have
    433 
    434 $x = \frac{d_1+d_2-n+3}{2}$ $y = \frac{d_1-d_2+n+1}{2}$
    435 
    436 Start from an arbitrary cell, and query the distance from that cell to every other cell, using $n^2$ queries. Any cell furthest is a corner.
    437 
    438 Next, from that corner, query to every other cell, using $n^2$ queries. We now get the distances from one corner.
    439 
    440 Now, notice that the non-opposite corners would have a distance of $n-1$ from the corner we have right now. There will be $n$ candidate corners. Choose one arbitrary candidate and query the distance from this candidate to all other candidates, using $n$ queries. Any furthest cell is a desired non-opposite corner.
    441 
    442 Lastly, query from the new-found corner, using $n^2$ queries. We now have sufficient information to answer.
    443 
    444 Query count: $3n^2 + n - \mathcal{O}(1)$. This analysis did not account for small constant optimizations like not querying the same pair twice and not querying the distance to self.
    445 
    446 Time complexity: $\mathcal{O}(n^2)$
    447 
    448 **Implementation (C++)**
    449 
    450 ```
    451 #include <bits/stdc++.h>
    452  
    453 using namespace std;
    454  
    455 int query(int i, int j) {
    456     cout << "? " << i << " " << j << endl;
    457     int ret;
    458     cin >> ret;
    459     return ret;
    460 }
    461  
    462 void test_case_run() {
    463     int n;
    464     cin >> n;
    465     
    466     // Find the first corner
    467     int dist1[n*n+1];
    468     for (int i = 1; i <= n*n; i++) dist1[i] = query(1, i);
    469     
    470     int corner1 = 1;
    471     for (int i = 1; i <= n*n; i++) if (dist1[i] > dist1[corner1]) corner1 = i;
    472     
    473     // Query distance from first corner
    474     int dist_corner1[n*n+1];
    475     for (int i = 1; i <= n*n; i++) {
    476         dist_corner1[i] = query(corner1, i);
    477     }
    478  
    479     // Find second corner    
    480     vector<int> corner2_candidates;
    481     for (int i = 1; i <= n*n; i++) {
    482         if (dist_corner1[i] == n-1) corner2_candidates.push_back(i);
    483     }
    484     
    485     int dist_findcorner2[corner2_candidates.size()];
    486     for (int i = 0; i < corner2_candidates.size(); i++) {
    487         dist_findcorner2[i] = query(corner2_candidates[0], corner2_candidates[i]); 
    488     }
    489     
    490     int corner2_index = 0;
    491     for (int i = 0; i < corner2_candidates.size(); i++) {
    492         if (dist_findcorner2[i] > dist_findcorner2[corner2_index]) corner2_index = i;
    493     }
    494     
    495     int corner2 = corner2_candidates[corner2_index];
    496     
    497     // Query distance from second corner
    498     int dist_corner2[n*n+1];
    499     for (int i = 1; i <= n*n; i++) {
    500         dist_corner2[i] = query(corner2, i);
    501     }
    502     
    503     // Find position
    504     /*
    505     d1 = |x-1|+|y-1| = x+y-2
    506     d2 = |x-1|+|y-n| = x-y+n-1
    507     
    508     d1 + d2 = 2x+n-3 => x = (d1+d2-n+3)/2
    509     d1 - d2 = 2y-n-1 => y = (d1-d2+n+1)/2
    510     */
    511     int ans[n+1][n+1];
    512     for (int i = 1; i <= n*n; i++) {
    513         int d1 = dist_corner1[i], d2 = dist_corner2[i];
    514         int x = (d1+d2-n+3)/2;
    515         int y = (d1-d2+n+1)/2;
    516         ans[x][y] = i;
    517     }
    518     
    519     cout << "!" << endl;
    520     for (int i = 1; i <= n; i++) {
    521         for (int j = 1; j <= n; j++) cout << ans[i][j] << " ";
    522         cout << endl;
    523     }
    524 };
    525  
    526 int main() {
    527     ios_base::sync_with_stdio(false);
    528     cin.tie(NULL);
    529     
    530     int t;
    531     cin >> t;
    532     while (t--) test_case_run();
    533     
    534     return 0;
    535 }
    536 ```
    537 
    538 **Challenge**
    539 
    540 This problem is solvable in $3n^2$ queries. Try it.
    541 
    542 # [2179H - Blackslex and Plants](/contest/2179/problem/H "Codeforces Round 1071 (Div. 3)")
    543 
    544 Author: [NortGlG](/profile/NortGlG "Candidate Master NortGlG")
    545 
    546 **Hint 1**
    547 
    548 Solve the easier version of this problem first:
    549 
    550 * Let $f(x)$ be the value of the least significant bit of $x$.
    551 
    552 **Hint 1.1**
    553 
    554 Find the conditions needed to be satisfied to make the value of $f(x)$ become $2^y$ for any non-negative integer $y$.
    555 
    556 **Hint 1.2**
    557 
    558 $f(x) = 2^y$ if and only if $y$ is the largest non-negative integer that makes $2^y$ divide $x$.
    559 
    560 What other things can we imply from that observation ?
    561 
    562 **Hint 1.3**
    563 
    564 If $2^y$ divides $x$, then $2^0, 2^1, 2^2, \ldots, 2^{y-1}$ will divide $x$ too. Use this fact to solve this version of the problem.
    565 
    566 **Solution**
    567 
    568 For any non-negative integer $y$, this equation is always true:
    569 
    570 $2^{y+1} - 1 = 2^0 + 2^1 + 2^2 + \ldots + 2^y$
    571 
    572 From this equation, the value of $f(x) - 1$ can be represented as the sum of $2^{a-1}$ for each positive integer $a$ that $2^a$ divides $x$, that is:
    573 
    574 $f(x) - 1 = 2^0 + 2^1 + 2^2 + \ldots + 2^{a-1}$
    575 
    576 Which can be rearranged as:
    577 
    578 $f(x) = 2^0 + 2^1 + 2^2 + \ldots + 2^{a-1} + 1$
    579 
    580 You can see that every term of this sum can be calculated independently because the term $2^b$ exists because $2^{b+1}$ divides $x$.
    581 
    582 For each watering operation on range $[l,r]$, you need to perform this action:
    583 
    584 * For $a = 1, 2, 3, \ldots, \log n$; increase the water amount by $2^{a-1}$ in every position $i$ where $2^a$ divides $(i - l + 1)$, and also increase the water amount in every position in range $[l, r]$ by $1$, too.
    585 
    586 These operations can be handled using prefix sum arrays separately in each $a$.
    587 
    588 Time complexity: $\mathcal{O}((n + q)\log n)$.
    589 
    590 **Solution**
    591 
    592 Read **Hint 1** first.
    593 
    594 You can extend the idea from the easier version to solve the actual task.
    595 
    596 Since the value of the least significant bit can be represented using the sum of $2^0, 2^1, 2^2, \ldots$, the only thing left to consider is the coefficient of those values in each position.
    597 
    598 For watering operations that cover the range $[l, r]$, you can perform the following update to the coefficient array:
    599 
    600 * For all $l \leq i \leq r$, add $i$ to the $i$-th position.
    601 * For all $l \leq i \leq r$, subtract $l-1$ from the $i$-th position.
    602 
    603 Which is basically the same as increasing the coefficients value in each $l \leq i \leq r$ by $i - l + 1$.
    604 
    605 These operations can be implemented using prefix sum arrays separately in each $a$, too.
    606 
    607 Time complexity: $\mathcal{O}((n+q)\log n)$.
    608 
    609 **Implementation (C++)**
    610 
    611 ```
    612 #include<bits/stdc++.h>
    613 using namespace std;
    614 using ll = long long;
    615 const int N = 200200;
    616 int qs1[20][N];
    617 ll qs2[20][N];
    618 ll ans[N];
    619 void solve() {
    620     int n, q;
    621     cin >> n >> q;
    622     int sz = 31 - __builtin_clz(n);
    623     for (int i = 1;i <= n;i++) ans[i] = 0;
    624     for (int j = 0;j <= sz;j++) {
    625         for (int i = 0;i <= n;i++) qs1[j][i] = 0, qs2[j][i] = 0;
    626     }
    627     while (q--) {
    628         int l, r;
    629         cin >> l >> r;
    630         int sz = 31 - __builtin_clz(r - l + 1);
    631         for (int j = 0;j <= sz;j++) {
    632             int k = (r - l + 1) >> j;
    633             qs1[j][l + (1 << j) - 1]++;
    634             qs2[j][l + (1 << j) - 1] += l - 1;
    635             qs1[j][min(n + 1, l + ((k + 1) << j) - 1)]--;
    636             qs2[j][min(n + 1, l + ((k + 1) << j) - 1)] -= l - 1;
    637         }
    638     }
    639     for (int i = 0;i <= sz;i++) {
    640         for (int j = 1;j <= n;j++) {
    641             if (j >= (1 << i)) {
    642                 qs1[i][j] += qs1[i][j - (1 << i)];
    643                 qs2[i][j] += qs2[i][j - (1 << i)];
    644             }
    645             ans[j] += 1ll * qs1[i][j] * j * (1 << max(0, i - 1));
    646             ans[j] -= 1ll * qs2[i][j] * (1 << max(0, i - 1));
    647         }
    648     }
    649     for (int i = 1;i <= n;i++) {
    650         cout << ans[i] << ' ';
    651     }
    652     cout << '\n';
    653 }
    654  
    655 int main() {
    656     cin.tie(nullptr)->sync_with_stdio(false);
    657     int q;
    658     cin >> q;
    659     while (q--) {
    660         solve();
    661     }
    662     return 0;
    663 }
    664 ```