codeforces-scrape

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

2138.md (52044B)


      1 Source: https://codeforces.com/blog/entry/146172
      2 
      3 [2139A — Maple and Multiplication](https://codeforces.com/contest/2139/problem/A)
      4 
      5 Idea: [installb](/profile/installb "Grandmaster installb") Preparation: [installb](/profile/installb "Grandmaster installb"),[2014CAIS01](/profile/2014CAIS01 "International Master 2014CAIS01")
      6 
      7 **Solution**
      8 
      9 If $a=b$ we need $0$ steps.
     10 
     11 If $a$ can be divided by $b$, we only need $1$ step, which is to multiply $b$ by $\frac{a}{b}$. Same for the case when $b$ can be divided by $a$.
     12 
     13 Otherwise, we need at most $2$ steps. As both $a$ and $b$ are positive integers, we can first multiply $a$ by $b$ and then multiply $b$ by the original value of $a$. Both number will be equal to $a\times b$.
     14 
     15 **Code (C++)**
     16 
     17 ```
     18 #include <bits/stdc++.h>
     19 using namespace std;
     20 typedef long long ll;
     21  
     22 int solve(){
     23     int a,b;
     24     cin >> a >> b;
     25     if(a == b) return 0;
     26     if(a % b == 0 || b % a == 0) return 1;
     27     return 2;
     28 }
     29  
     30 int main(){
     31     ios::sync_with_stdio(false);
     32     int TC;
     33     cin >> TC;
     34     while(TC --){
     35         cout << solve() << '\n';
     36     }
     37     return 0;
     38 }
     39 ```
     40 
     41 **Rate this problem**
     42 
     43 * Amazing problem:
     44 * Good problem:
     45 * Average problem:
     46 * Bad problem:
     47 * Horrible problem:
     48 
     49 [2139B — Cake Collection](https://codeforces.com/contest/2139/problem/B)
     50 
     51 Idea: [installb](/profile/installb "Grandmaster installb") Preparation: [installb](/profile/installb "Grandmaster installb")
     52 
     53 **Solution**
     54 
     55 The number of cakes collected from an oven depends only on the last time Maple visits it. Therefore, in the optimal strategy, she should visit distinct ovens in the last $\min(m,n)$ seconds.
     56 
     57 Let's think in reverse: suppose we fix an order $p_1,\dots,p_n$ of the ovens. Then at second $m$ we visit oven $p_1$, at second $m-1$ we visit oven $p_2$, and so on. For the $i$-th oven in this order, we collect $a_{p_i}\cdot \max(0, m-i+1)$ cakes.
     58 
     59 To maximize the total number of cakes collected, ovens with larger $a_i$ should be visited later (i.e., assigned larger multipliers). Thus we sort $a$ in non-increasing order first.
     60 
     61 The final answer is $\sum_{i=1}^n a_i \cdot \max(0, m-i+1)$.
     62 
     63 **Code (C++)**
     64 
     65 ```
     66 #include <bits/stdc++.h>
     67 using namespace std;
     68 typedef long long ll;
     69 const int INF = 0x3f3f3f3f;
     70  
     71 void solve(){
     72     int n,t;
     73     cin >> n >> t;
     74     ll ans = 0;
     75     vector <int> a(n);
     76     for(int i = 0;i < n;i ++) cin >> a[i];
     77     sort(a.begin(),a.begin() + n,greater <int>());
     78     for(int i = 0;i < n;i ++) ans += 1ll * a[i] * max(0,t - i);
     79     cout << ans << '\n';
     80 }
     81  
     82 int main(){
     83     ios::sync_with_stdio(false);
     84     int TC;
     85     cin >> TC;
     86     while(TC --){
     87         solve();
     88     }
     89     return 0;
     90 }
     91 ```
     92 
     93 **Rate this problem**
     94 
     95 * Amazing problem:
     96 * Good problem:
     97 * Average problem:
     98 * Bad problem:
     99 * Horrible problem:
    100 
    101 [2138A — Cake Assignment](https://codeforces.com/contest/2138/problem/A)
    102 
    103 Idea: [wjy666](/profile/wjy666 "Master wjy666") Preparation: [wjy666](/profile/wjy666 "Master wjy666")
    104 
    105 **Hint**
    106 
    107 You can backtrack from the final state.
    108 
    109 **Solution**
    110 
    111 Denote the state $(a,b)$ that indicates Chocola has $a$ cakes and Vanilla has $b$ cakes.
    112 
    113 After one operation of type $1$, Vanilla's number of cakes will definitely be at least half of the total, and similarly for operation $2$. If $0 \lt a \lt 2^{k}$, then $2^{k} \lt b \lt 2^{k+1}$, meaning the previous operation must have been type $1$. Similarly, if $0 \lt b \lt 2^{k}$, the previous operation must have been type $2$.
    114 
    115 Therefore, you can backtrack from the final state $(x,2^{k+1}-x)$, until it reaches the initial state $(2^k,2^k)$.
    116 
    117 Now let's analyze how many steps we need to do during the process.
    118 
    119 For the state $(a, b)$, where $a, b \neq 0$, assume $a = i \cdot 2^{p_a}$ and $b = j \cdot 2^{p_b}$, $i$ and $j$ are positive odd integers.
    120 
    121 Since $a + b = 2^{k+1}$, it must be true that $ 0 \le p_a = p_b \le k$ , and after one operation $1$ or $2$, both $p_a$ and $p_b$ decrease by exactly $1$.
    122 
    123 Therefore, the whole process takes at most $k$ steps, so we solve the problem with $O(tk)$ time complexity.
    124 
    125 **Code (C++)**
    126 
    127 ```
    128 #include <bits/stdc++.h> 
    129 using namespace std;
    130 int main(){
    131     int t; cin>>t;
    132     while(t--){
    133         long long k,x,kk; cin>>k>>x; kk=1ll<<k;
    134         if (!x||x==kk*2) {cout<<"-1\n"; continue;}
    135         long long y=kk*2-x;
    136         vector<int> ans; ans.clear();
    137         while(x!=kk){
    138             if (x>y) ans.push_back(2),x-=y,y*=2;
    139             else ans.push_back(1),y-=x,x*=2;
    140         }
    141         cout<<ans.size()<<"\n";
    142         while(!ans.empty()) cout<<ans.back()<<' ',ans.pop_back();
    143         cout<<"\n";
    144     }
    145     return 0;
    146 }
    147 ```
    148 
    149 **Rate this problem**
    150 
    151 * Amazing problem:
    152 * Good problem:
    153 * Average problem:
    154 * Bad problem:
    155 * Horrible problem:
    156 
    157 [2138B — Antiamuny Wants to Learn Swap](https://codeforces.com/contest/2138/problem/B)
    158 
    159 Idea: [tarjen](/profile/tarjen "International Grandmaster tarjen") Preparation: [installb](/profile/installb "Grandmaster installb"),[tarjen](/profile/tarjen "International Grandmaster tarjen"),[2014CAIS01](/profile/2014CAIS01 "International Master 2014CAIS01")
    160 
    161 **Solution**
    162 
    163 For array $b$, we can prove that $f(b)\neq g(b)$ **if and only if** there exist indexes $1\le i \lt j \lt k\le m$ which satisfy $b_i \gt b_j \gt b_k$.
    164 
    165 Since $a$ is a permutation, all elements in $b$ should be distinct. $g(b)$ is equal to the number of inversions in $b$. When there exists some index $i$ that satisfies $a_i \gt a_{i+1} \gt a_{i+2}$, we can reduce the number of inversions by $3$ by applying operation $2$, allowing $f(b)$ to become less than $g(b)$. This is the only case where you can reduce more than $1$ inversion with one operation.
    166 
    167 If there exist indexes $1\le i \lt j \lt k\le m$ which satisfy $b_i \gt b_j \gt b_k$, we can first choose indexes $i,k$, then move all elements greater than $b_i$ to the right of $b_k$ and move all elements less than $b_k$ to the left of $b_i$ by swapping adjacent numbers (applying the first operation). Now all elements $b_p$ between $b_i,b_k$ satisfy $b_i \gt b_p \gt b_k$. We then swap them to the left of $b_i$ until there is only one element $b_j$ left. Now $b_i \gt b_j \gt b_k$ and they are adjacent, and we can apply operation $2$ on the current index of $b_i$.
    168 
    169 If we only apply operation $1$ on indexes $i$ which satisfy $b_i \gt b_{i+1}$, there will never exist any index $i$ satisfying $b_i \gt b_{i+1} \gt b_{i+2}$ in $b$ during the process. If we apply an operation $1$ on some index $i$ where $b_i \lt b_{i+1}$, the number of inversions will be increased by $1$ instead of decreased by $1$, which makes it impossible to reach $f(b) \lt g(b)$ with one operation $2$, even if it decreases the number of inversions by $3$. Therefore, in this case $f(b)=g(b)$.
    170 
    171 For each element $a_i$, we define:
    172 
    173 * $l_i$: the maximum index $ \lt i$ such that $a_{l_i} \gt a_i$,
    174 * $r_i$: the minimum index $ \gt i$ such that $a_{r_i} \lt a_i$.
    175 
    176 Then the answer to a query $[l, r]$ is $\texttt{NO}$ if and only if some segment $[l_i, r_i]$ lies fully inside $[l, r]$.
    177 
    178 To answer multiple queries, you can preprocess the smallest $r$ for every $l$ such that the answers for all $[l,x](x\ge r)$ should be $\texttt{NO}$.
    179 
    180 The time complexity is $O(n)$ if you find $l_i,r_i$ with the Monotonic Stack trick. $O(n\log n)$ solutions can also pass.
    181 
    182 **Code (C++)**
    183 
    184 ```
    185 #include <bits/stdc++.h>
    186 using namespace std;
    187 void solve()
    188 {
    189     int n, q;
    190     cin >> n >> q;
    191     vector<int> a(n + 2);
    192     for (int i = 1; i <= n; i++)
    193     {
    194         cin >> a[i];
    195     }
    196  
    197     vector<int> mxl(n + 1), mir(n + 1);
    198     for (int i = 1; i <= n; i++)
    199     {
    200         mxl[i] = i - 1;
    201         while (mxl[i] > 0 && a[mxl[i]] < a[i])
    202             mxl[i] = mxl[mxl[i]];
    203     }
    204     for (int i = n; i >= 1; i--)
    205     {
    206         mir[i] = i + 1;
    207         while (mir[i] <= n && a[mir[i]] > a[i])
    208             mir[i] = mir[mir[i]];
    209     }
    210     vector<int> L(n + 1, 0);
    211     for (int i = 2; i < n; i++)
    212     {
    213         if (mxl[i] > 0 && mir[i] <= n)
    214         {
    215             L[mir[i]] = max(L[mir[i]], mxl[i]);
    216         }
    217     }
    218     for (int i = 1; i <= n; i++)
    219     {
    220         L[i] = max(L[i], L[i - 1]);
    221     }
    222  
    223     for (int i = 0; i < q; i++)
    224     {
    225         int l, r;
    226         cin >> l >> r;
    227         if (l <= L[r])
    228             cout << "NO\n";
    229         else
    230             cout << "YES\n";
    231     }
    232 }
    233 int main()
    234 {
    235     ios::sync_with_stdio(false);
    236     cin.tie(0);
    237     int T;
    238     cin >> T;
    239     while (T--)
    240     {
    241         solve();
    242     }
    243 }
    244 ```
    245 
    246 **Rate this problem**
    247 
    248 * Amazing problem:
    249 * Good problem:
    250 * Average problem:
    251 * Bad problem:
    252 * Horrible problem:
    253 
    254 [2138C1 — Maple and Tree Beauty (Easy Version)](https://codeforces.com/contest/2138/problem/C1)
    255 
    256 Idea: [installb](/profile/installb "Grandmaster installb") Preparation: [installb](/profile/installb "Grandmaster installb"),[tarjen](/profile/tarjen "International Grandmaster tarjen"),[2014CAIS01](/profile/2014CAIS01 "International Master 2014CAIS01")
    257 
    258 **Solution**
    259 
    260 We can first find out that the maximum possible answer is the minimum depth among all leaves $d=\min{dep_u}$, as the LCS can't be greater than the minimum length of all names.
    261 
    262 We consider a special case first where all leaves have the same depth. If we want to achieve the maximum answer $d$, the names of all leaves should be exactly the same. Which means, for any two vertices with the same depth, their labels has to be the same.
    263 
    264 For each depth $i$, we group all vertices with depth $i$ together as the $i$-th group (suppose root has depth $1$). For each group, all vertices in the group should have the same label. Let the size of groups $1,\cdots,d$ be $c_1,\cdots,c_d$. Now the problem can be considered as a knapsack problem, where you have $d$ items with weight $c_1,\cdots,c_d$. We need to find out whether you can take several numbers from $c$ that have a sum equal to $k$. This can be solved in $O(n^2)$.
    265 
    266 If the maximum answer $d$ is not achievable, we can show that you can always achieve $d-1$. For each group from the first to the $d$-th, we assign an arbitrary label $0$ or $1$ which still has at least $c_i$ numbers remaining to all vertices in the group. As all leaves have the same depth, $c_d$ should be the maximum element in the array, so you are always able to select a label for groups $1$ to $d-1$. Then arbitrarily distribute the remaining labels among vertices in the last groups (which are leaves).
    267 
    268 Now consider the general case where not all leaves have the same depth. If we want to achieve answer $=d$, we need to select $d$ groups. For each leaf vertex $v$, there should exist a vertex in the $d$-th group which is an ancestor of $v$. And for every $2\le i\le d$, for each vertex $v$ in the $i$-th group, there should exist a vertex in the $i-1$-th group which is an ancestor of $v$. All vertices in the same group should have the same label. Suppose the $i$-th group has label $l_i$, then we can achieve $\text{LCS}=l_1l_2\ldots l_d$ which has length $d$.
    269 
    270 We can still group all vertices with depth $1\le i\le d$ together as the $i$-th group. For all vertices with depth $ \gt d$, we can set their label arbitrarily. We can view them as items with weight $1$ in the knapsack problem.
    271 
    272 And we can show this is the optimal way to select $d$ groups. If some vertex $u$ with depth $\le d$ is not selected, there must be some vertices selected in some group in the subtree of $u$, because the path from the root to $u$ consists of fewer than $d$ vertices. If the smallest group index that some vertex in the subtree of $u$ belongs to is $i$, we can instead let $u$ be inside the $i$-th group, and then the labels of all vertices in the subtree of $u$ that were previously in group $i$ can be selected arbitrarily. If we consider the knapsack problem, we have reduced some $c_i$ by $x$ and added $x$ items with weight $1$. All achievable values still remain achievable, while some previously unachievable values become achievable.
    273 
    274 The time complexity is $O(n^2)$, the bottleneck is knapsack.
    275 
    276 **Code (C++)**
    277 
    278 ```
    279 // n^2/w
    280 #include <bits/stdc++.h>
    281 using namespace std;
    282 int solve() {
    283     int n, k;
    284     cin >> n >> k;
    285     vector<int> fa(n, -1), dep(n, 0);
    286     vector<int> noson(n, 1), cnt(n + 1);
    287     cnt[0]++;
    288     for (int i = 1; i < n; i++) {
    289         cin >> fa[i], fa[i]--;
    290         dep[i] = dep[fa[i]] + 1;
    291         cnt[dep[i]]++;
    292         noson[fa[i]] = 0;
    293     }
    294     int mxdep = 1e9;
    295     for (int i = 0; i < n; i++)
    296         if (noson[i]) mxdep = min(mxdep, dep[i]);
    297  
    298     int sum = 0;
    299  
    300     vector<int> dp(n + 1);
    301     dp[0] = 1;
    302     for (int i = 0; i <= mxdep; i++) {
    303         for (int j = sum; j >= 0; j--) dp[j + cnt[i]] |= dp[j];
    304         sum += cnt[i];
    305     }
    306     if (sum <= k || sum <= n - k) return mxdep + 1;
    307     for (int i = 0; i <= sum; i++)
    308         if (dp[i]) {
    309             if (i <= k && sum - i <= n - k) return mxdep + 1;
    310         }
    311     return mxdep;
    312 }
    313 int main() {
    314     ios::sync_with_stdio(false);
    315     cin.tie(0);
    316     int T;
    317     cin >> T;
    318     while (T--) cout << solve() << "\n";
    319     return 0;
    320 }
    321 ```
    322 
    323 **Rate this problem**
    324 
    325 * Amazing problem:
    326 * Good problem:
    327 * Average problem:
    328 * Bad problem:
    329 * Horrible problem:
    330 
    331 [2138C2 — Maple and Tree Beauty (Hard Version)](https://codeforces.com/contest/2138/problem/C2)
    332 
    333 Idea: [installb](/profile/installb "Grandmaster installb") Preparation: [installb](/profile/installb "Grandmaster installb"),[tarjen](/profile/tarjen "International Grandmaster tarjen"),[2014CAIS01](/profile/2014CAIS01 "International Master 2014CAIS01")
    334 
    335 **Solution**
    336 
    337 We focus on optimizing the knapsack problem. In the knapsack problem we only need to know $f_i=0/1$ which means whether you can achieve sum $i$, so we can optimize the knapsack with bitset. The time complexity is $O(\frac{n^2}{\omega})$ which is enough to pass E2.
    338 
    339 But actually we can do better. For the knapsack problem, it has at most $n$ items, and the sum of weights of all items is also at most $n$. We can do a sqrt decomposition trick here.
    340 
    341 * For items with weight $\ge\sqrt{n}$, there are at most $\sqrt{n}$ such items.
    342 * For items with weight $ \lt \sqrt{n}$, we count the number of items for each different weight. If there are $c_w$ items for weight $w$, we decompose $x$ into $c_w=2^0+2^1+\cdots+2^k+y$ where $k$ is the largest integer satisfying $2^0+2^1+\ldots+2^k\le c_w$. Then we create new items with weights $2^0\cdot w,2^1\cdot w,\ldots,2^k\cdot w,y\cdot w$. The set of new items is the same as $c_w$ items with weight $w$ if we only consider the different sum of weights the set of items can achieve. Now we only have $\sum_{w=1}^{\sqrt{n}}\log(c_w)=\sqrt{n}$ items.
    343 
    344 The total time complexity is $O(\sqrt{n}\cdot n+\sqrt{n}\cdot n)=O(n\sqrt{n})$.
    345 
    346 And this can also be optimized with bitset, leading to an $O(\frac{n\sqrt{n}}{\omega})$ solution.
    347 
    348 **Code (C++)**
    349 
    350 ```
    351 // nsqrtn/w
    352 #include <bits/stdc++.h>
    353 using namespace std;
    354 const int N = 2e5 + 10;
    355 template <int maxn>
    356 int solve(int n, int k) {
    357     if (maxn <= n) {
    358         return solve<min(N, maxn * 2)>(n, k);
    359     }
    360     bitset<maxn> dp;
    361     vector<int> fa(n, -1), dep(n, 0);
    362     vector<int> noson(n, 1), cnt(n + 1);
    363     cnt[0]++;
    364     for (int i = 1; i < n; i++) {
    365         cin >> fa[i], fa[i]--;
    366         dep[i] = dep[fa[i]] + 1;
    367         cnt[dep[i]]++;
    368         noson[fa[i]] = 0;
    369     }
    370     dp.reset();
    371     dp[0] = 1;
    372     int mxdep = 1e9;
    373     for (int i = 0; i < n; i++)
    374         if (noson[i]) mxdep = min(mxdep, dep[i]);
    375  
    376     int sum = 0;
    377     vector<int> all(cnt.begin(), cnt.begin() + mxdep + 1);
    378     sort(all.begin(), all.end());
    379     vector<int> v;
    380     for (int i = 0; i < (int)all.size(); i++) {
    381         int j = i;
    382         while (j + 1 < (int)all.size() && all[i] == all[j + 1]) j++;
    383         int t = j - i + 1;
    384         for (int z = 1; z <= t; z *= 2) {
    385             v.push_back(z * all[i]);
    386             t -= z;
    387         }
    388         if (t > 0) v.push_back(t * all[i]);
    389         i = j;
    390     }
    391     dp[0] = 1;
    392     for (auto val : v) {
    393         sum += val;
    394         dp |= (dp << val);
    395     }
    396     if (sum <= k || sum <= n - k) return mxdep + 1;
    397     for (int i = 0; i <= sum; i++)
    398         if (dp[i]) {
    399             if (i <= k && sum - i <= n - k) return mxdep + 1;
    400         }
    401     return mxdep;
    402 }
    403 int main() {
    404     ios::sync_with_stdio(false);
    405     cin.tie(0);
    406     int T;
    407     cin >> T;
    408     while (T--) {
    409         int n, k;
    410         cin >> n >> k;
    411         cout << solve<1>(n, k) << "\n";
    412     }
    413     return 0;
    414 }
    415 ```
    416 
    417 **Rate this problem**
    418 
    419 * Amazing problem:
    420 * Good problem:
    421 * Average problem:
    422 * Bad problem:
    423 * Horrible problem:
    424 
    425 [2139D — Antiamuny and Slider Movement](https://codeforces.com/contest/2138/problem/D)
    426 
    427 Idea: [tarjen](/profile/tarjen "International Grandmaster tarjen"),[StarSilk](/profile/StarSilk "International Grandmaster StarSilk") Preparation: [installb](/profile/installb "Grandmaster installb"),[tarjen](/profile/tarjen "International Grandmaster tarjen"),[StarSilk](/profile/StarSilk "International Grandmaster StarSilk")
    428 
    429 **Solution**
    430 
    431 Let’s define $b_i$ as the position of the $i$-th slider decreased by $i$. Every operation on the sliders can be interpreted as a modification of the array $b$.
    432 
    433 * If we increase the position of slider $i$, then $b_i$ increases. At the same time, every suffix element $b_{i+1}, b_{i+2}, \dots, b_n$ gets updated to $b_j := \max(b_j, b_i)$.
    434 * If we decrease the position of slider $i$, then $b_i$ decreases. At the same time, every prefix element $b_1, b_2, \dots, b_{i-1}$ gets updated to $b_j := \min(b_j, b_i)$.
    435 
    436 Since the array $b$ always remains **non-decreasing**, we can reinterpret operations as follows:
    437 
    438 * Every operation simultaneously applies a $\min$ operation to all elements on the left, and a $\max$ operation to all elements on the right.
    439 
    440 For a fixed slider $b_i$, the effect of each operation on the slider should be one of the following:
    441 
    442 1. $b_i := \max(b_i, x)$
    443 2. $b_i := \min(b_i, x)$
    444 3. $b_i := x$ (assignment)
    445 
    446 Our task is to compute the sum of final values of $b_i$ after all possible sequences of operations.
    447 
    448 We sort all operations by their parameter $x$. If multiple operations share the same $x$, we give them a consistent order and then assume all $x$ are distinct in the following part of the editorial.
    449 
    450 We first suppose that the position of the slider is changed at least once. Suppose the final value for slider $i$ is $b_e$, let’s consider which operation sets $b_i = b_e$ at the very end.
    451 
    452 At this point, we no longer care about the exact value of $b_i$ during the process — only whether it is less than, equal to, or greater than $b_e$.
    453 
    454 All operations of type $\max$ with $x \lt b_e$ and type $\min$ with $x \gt b_e$ are irrelevant. We can insert them anywhere after deciding the order of other operations without affecting the result. We won't consider these operations in the following parts of the editorial.
    455 
    456 All assignment operations $b_i := x$ can be reinterpreted:
    457 
    458 * If $x \lt b_e$, treat it as $b_i := \min(b_i, x)$.
    459 * If $x \gt b_e$, treat it as $b_i := \max(b_i, x)$.
    460 
    461 The last operation, that makes $b_i = b_e$ must be the one with parameter $x = b_e$.
    462 
    463 * If this operation is assignment, then all other operations can appear in any order.
    464 * If this operation is $\max$ type, then immediately before it we must have $b_i \lt b_e$.
    465 * + Either the last preceding valid operation is some $\min$ type operation making $b_i \lt b_e$;
    466 * + Or no other effective operation occurs, and the initial value of $b_i$ was already smaller than $b_e$.
    467 * If this operation is $\min$ type operation, it is symmetric: either the last preceding valid operation is a $\max$ type operation, or the initial value of $b_i$ was already larger than $b_e$.
    468 
    469 Finally, don’t forget the case where a slider is never touched, where it simply keeps its initial value.
    470 
    471 For each of the $n$ sliders, we need to check contributions over all $m$ operations. The overall time complexity is $O(nm)$.
    472 
    473 **Code (C++)**
    474 
    475 ```
    476 #include<bits/stdc++.h>
    477 using namespace std;
    478 const long long mod=1000000007;
    479 long long a[5000],ans[5000],tt[5001],inv[5001];
    480 struct apos{
    481 	long long id;
    482 	long long x;
    483 	friend bool operator<(apos a,apos b){
    484 		return a.x<b.x;
    485 	}
    486 }ap[5000];
    487 int main(){
    488 	ios::sync_with_stdio(false),cin.tie(0);
    489 	int T,flag;
    490 	long long n,m,p,q,x,i,j,cl,cr;
    491 	tt[0]=1;
    492 	for(i=1;i<=5000;i++)tt[i]=tt[i-1]*i%mod;
    493 	inv[1]=1;
    494 	for(i=2;i<=5000;i++)inv[i]=(mod-mod/i)*inv[mod%i]%mod;
    495 	for(cin>>T;T>0;T--)
    496 	{
    497 		cin>>n>>m>>p;
    498 		for(i=0;i<n;i++)
    499 		{
    500 			cin>>a[i];
    501 			a[i]-=i;
    502 		}
    503 		for(i=0;i<p;i++)
    504 		{
    505 			cin>>ap[i].id>>ap[i].x;
    506 			ap[i].id--;
    507 			ap[i].x-=ap[i].id;
    508 		}
    509 		sort(ap,ap+p);
    510 		for(i=0;i<n;i++)
    511 		{
    512 			flag=0;
    513 			for(j=0;j<p;j++)
    514 			{
    515 				if(ap[j].id<=i&&ap[j].x>=a[i])flag=1;
    516 				if(ap[j].id>=i&&ap[j].x<a[i])flag=1;
    517 			}
    518 			if(!flag)
    519 			{
    520 				ans[i]=a[i]+i;
    521 				continue;
    522 			}
    523 			ans[i]=0;
    524 			cl=0;
    525 			cr=0;
    526 			for(j=0;j<p;j++)
    527 			{
    528 				if(ap[j].id<=i)cr++;
    529 			}
    530 			for(j=0;j<p;j++)
    531 			{
    532 				if(ap[j].id<=i)cr--;
    533 				if(ap[j].id==i)ans[i]=(ans[i]+(ap[j].x+i)*inv[cl+cr+1])%mod;
    534 				if(ap[j].id<i)
    535 				{
    536 					if(cl==0&&cr==0&&a[i]<=ap[j].x)ans[i]=(ans[i]+ap[j].x+i)%mod;
    537 					else ans[i]=(ans[i]+(ap[j].x+i)*inv[cl+cr+1]%mod*inv[cl+cr]%mod*cl)%mod;
    538 				}
    539 				if(ap[j].id>i)
    540 				{
    541 					if(cl==0&&cr==0&&a[i]>ap[j].x)ans[i]=(ans[i]+ap[j].x+i)%mod;
    542 					else ans[i]=(ans[i]+(ap[j].x+i)*inv[cl+cr+1]%mod*inv[cl+cr]%mod*cr)%mod;
    543 				}
    544 				if(ap[j].id>=i)cl++;
    545 			}
    546 		}
    547 		for(int x = 0;x < n;x ++)
    548 		{
    549 			cout<<ans[x]*tt[p]%mod<<' ';
    550 		}
    551 		cout<<'\n';
    552 	}
    553 	return 0;
    554 }
    555 ```
    556 
    557 **Rate this problem**
    558 
    559 * Amazing problem:
    560 * Good problem:
    561 * Average problem:
    562 * Bad problem:
    563 * Horrible problem:
    564 
    565 [2139E1 — Determinant Construction (Easy Version)](https://codeforces.com/contest/2138/problem/E1)
    566 
    567 Idea: [wjy666](/profile/wjy666 "Master wjy666") Preparation: [wjy666](/profile/wjy666 "Master wjy666")
    568 
    569 **Solution 1**
    570 
    571 Thanks to [EvenImage](/profile/EvenImage "Legendary Grandmaster EvenImage") for his significant contribution to this solution.
    572 
    573 **Step 1**
    574 
    575 We can consider transforming the construction of a matrix into the construction of a directed graph, as the determinant and permutations are closely related to the cycle covers of a directed graph.
    576 
    577 If we have a directed graph with $n$ vertices, a cycle cover is a set of $n$ edges such that each vertex has exactly one incoming edge and one outgoing edge in this set (self-loops are allowed). In other words, these $n$ edges form one or more cycles that together cover all vertices in the graph.
    578 
    579 In a complete directed graph (with self-loops), every permutation of the vertices determines a cycle cover and vice versa. (The cycles of the permutation are precisely the cycles in the cover.)
    580 
    581 We consider the definition of the determinant:
    582 
    583 $ \det(M)=\sum_{\begin{subarray}{c}B=(b_{0},\ldots,b_{n-1})\\ B\in\mathcal{P}_{n}\end{subarray}}(-1)^{\mathrm{inv}(B)}\cdot\prod_{i=0}^{n-1}m_ {i,b_{i}} $
    584 
    585 This summation goes over all permutations $B$, in other words, over all cycle covers of the directed graph determined by the adjacency matrix $M$. We can also interpret $m_{i,j}=0$ as "the edge from $i$ to $j$ does not exist at all". Thus, the product term $\prod_{i=0}^{n-1}m_ {i,b_{i}}$ is non-zero only if all $m_ {i,b_{i}} \neq 0$, which corresponds to the existence of a cycle cover in the graph.
    586 
    587 We want to construct a directed graph such that the sum of the weights of its cycle covers equals $x$. Since the current problem only allows the use of $-1, 0, 1$, the edge weights can only be $1$ or $-1$, and the contribution of a valid cycle cover to the answer can only be $1$ or $-1$.
    588 
    589 PS: You can refer to pages 56-58 of <https://ipsc.ksp.sk/2012/real/solutions/booklet.pdf> for more information.
    590 
    591 **Step 2**
    592 
    593 There might be many ways to construct a legal directed graph. We will demonstrate a method that transforms the problem into constructing a DAG with exactly $x$ paths from source vertex $1$ to sink vertex $n$.
    594 
    595 For a directed acyclic graph $G$ with source vertex $1$ and sink vertex $n$, we can construct the following adjacency matrix:
    596 
    597 * $g_{i,j} = -1$ if there is an edge $i \rightarrow j$ in $G$. Set the weight of all original edges in $G$ to $-1$.
    598 * $g_{i,i} = 1$ for all $1 \lt i \lt n$. Add a self-loop with weight $1$ to all vertices in $G$ except the source and sink.
    599 * $g_{n,1} = 1$. Add an edge from the sink to the source with weight $1$.
    600 * Everything else $= 0$.
    601 
    602 We analyze all cycle covers of this new graph. Due to the presence of the edge $n \rightarrow 1$ , any cycle cover must contain a main cycle that includes nodes $1$ and $n$, formed by a path $P$ from $1$ to $n$ in $G$ and the edge $n \rightarrow 1$. For nodes not on path $P$ (i.e., intermediate nodes not covered by path $P$), they must be covered by self-loops with weight $1$. Therefore, each cycle cover uniquely corresponds to a path $P$ from $1$ to $n$.
    603 
    604 Since there are $x$ paths in $G$, we only need to ensure that the contribution of each cycle cover is $1$ to obtain a determinant value of $x$. Next, we will analyze how to achieve this by setting the weight of all original edges in $G$ to $-1$.
    605 
    606 For each cycle cover, first consider the product of all edge weights:
    607 
    608 * The main cycle has $k$ edges, among which $k-1$ edges come from path $P$ (each with weight $-1$), and one edge is $n \rightarrow 1$ (with weight $1$). Thus, the product term is $(-1)^{k-1}$.
    609 * The weights of all other self-loops are $1$.
    610 
    611 Therefore, the product of all edge weights is $(-1)^{k-1}$.
    612 
    613 Then we consider the sign term $(-1)^{\mathrm{inv}(B)}$. In fact, the parity of the number of inversions $\mathrm{inv}(B)$ in the permutation is consistent with the parity of the number of even cycles in the permutation. The main cycle is a cycle of length $k$, and the self-loops are all cycles of length $1$. Therefore, the sign term is $(-1)^{k-1}$.
    614 
    615 Thus, the contribution of each cycle cover is $(-1)^{k-1} \cdot (-1)^{k-1}=1$.
    616 
    617 Due to the constraints in the problem that the matrix size is at most $80$ and there are at most $3$ non-zero entries per row and column, we need to construct a DAG that satisfies:
    618 
    619 * Exactly $x$ paths from source vertex $1$ to sink vertex $n$.
    620 * At most $80$ nodes.
    621 * The in-degree of each node $\le 2$ and the out-degree of each node $\le 2$.
    622 
    623 **Step 3**
    624 
    625 Since $80$ is a loose boundary, there might be many constructions that satisfy it. We will introduce a construction method that encodes $x$ in base three.
    626 
    627 The basic unit shown in the figure can form a base-three digit because the number of paths from $1$ to $3$ is $2$, and from $1$ to $4$ is $3$. Node $4$ can be connected to the next unit, forming a chain of units, where each unit corresponds to a base-three digit. Nodes $3$ and $4$ have one free out-degree, which can contribute to the final answer.
    628 
    629 ![ ](/predownloaded/8b/b1/8bb177d55c6f9946d3ba3ad2d809d52d4e2da9b2.png)
    630 
    631 The example figure below shows how to construct $22=1+3+2 \cdot 3^2$ in this way. There are $\log_3 n$ basic units, each with $4$ nodes. The answer chain has at most $\log_3 n$ nodes. Therefore, the total number of nodes is $5\log_3 n + O(1)$, which can pass the problem.
    632 
    633 ![ ](/predownloaded/c3/ae/c3aef65143ebe908453ebf2cd1a515c1057222f4.png)
    634 
    635 **Code (C++)**
    636 
    637 ```
    638 #include<bits/stdc++.h> 
    639 using namespace std;
    640 const int N=81;
    641 int a[N][N];
    642 vector<pair<int,int>> e;
    643 void add(int x,int y){
    644     e.push_back({x,y});
    645 }
    646 void make_matrix(int n){
    647     for(int i=2;i<n;++i) a[i][i]=1;
    648     a[n][1]=1;
    649     for(auto [x,y]:e) a[x][y]=-1;
    650 }
    651 int main(){
    652     int _; scanf("%d",&_); //cin>>_;
    653     int max_bit=15;
    654     while(_--){
    655         memset(a,0,sizeof(a)); e.clear();
    656         int n=1;
    657         for(int i=0;i<max_bit;++i){
    658             add(n,n+1); add(n+1,n+2); add(n+2,n+3); add(n+3,n+4);
    659             add(n+1,n+3); add(n+2,n+4);
    660             n+=4;
    661         }
    662         int x,bit_1=1,bit_2=4; scanf("%d",&x); ++n;
    663         for(int i=0;i<max_bit;++i){
    664             if (x%3==1) add(bit_1,n),add(n,n+1),++n;
    665             if (x%3==2) add(bit_2,n),add(n,n+1),++n;
    666             bit_1+=4; bit_2+=4; x/=3;
    667         }
    668         make_matrix(n);
    669         cout << n <<'\n';
    670         for (int r = 1; r <= n; r++) {
    671             for (int c = 1; c <= n; c++) {
    672                 printf("%d ",a[r][c]);
    673             }
    674             cout << '\n';
    675         }
    676     }
    677 }
    678 ```
    679 
    680 **Solution 2**
    681 
    682 **Step 1**
    683 
    684 We can consider using Tridiagonal Matrices, where the advantage lies in transforming the calculation of the determinant value into a recursive formula.
    685 
    686 Let $d_{i,j}$ denote the element in the i-th row and j-th column of matrix $D$, $D_k$ represents the submatrix composed of the upper-left $k \times k$ elements, and $A_k$ denotes the determinant value of $D_k$.
    687 
    688 When $k \ge 2$, there are two ways to obtain $D_{k+1}$ from $D_k$:
    689 
    690 * Let $ d_{k+1,k+1}=1, d_{k+1,k}=1,d_{k,k+1}=1$ to get $A_{k+1}=A_k-A_{k-1}$
    691 * Let $ d_{k+1,k+1}=1, d_{k+1,k}=1,d_{k,k+1}=-1$ to get $A_{k+1}=A_k+A_{k-1}$
    692 
    693 Thus, we transform the problem into constructing a sequence $A_1,\ldots,A_m$ satisfying:
    694 
    695 * $A_1 = |D_1|, A_2 = |D_2|$
    696 * For any $k=2,3,\ldots,m-1$, one of the following two equations holds: $A_{k+1}=A_k-A_{k-1}$, or $A_{k+1}=A_k+A_{k-1}$
    697 * $A_m=n (m \le 80)$
    698 
    699 **Step 2**
    700 
    701 Consider recursively generating the entire sequence from $A_m=n$ backwards.
    702 
    703 * Choose a positive integer as $A_{m−1}$.
    704 * At a certain moment, we have $A_k$ and $A_{k+1}$, and obtain $A_{k−1}$ as follows:
    705 
    706   If $A_k \gt A_{k+1}$, let $A_{k-1}=A_k-A_{k+1}$; otherwise, let $A_{k-1}=A_{k+1}-A_k$
    707 
    708   This ensures that each number in the sequence is a non-negative integer.
    709 * If at some point there exist $D_1,D_2$ satisfying $A_k = |D_1|, A_{k+1} = |D_2|$, successfully finish the construction.
    710 
    711 For example,if we have $A_m=7$ and $A_{m−1}=3$, the final sequence will be $1,2,3,1,4,3,7$, and we will generate the matrix as
    712 
    713 $\begin{pmatrix} 1 & -1 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & -1 & 0 & 0 & 0 & 0 \\ 0 & 1 & 1 & 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 1 & -1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 1 & 1 & 0 \\ 0 & 0 & 0 & 0 & 1 & 1 & -1 \\ 0 & 0 & 0 & 0 & 0 & 1 & 1 \end{pmatrix}$
    714 
    715 Denote $(A_k,A_{k+1})=(x,y)$.
    716 
    717 When $x \gt y$, the recursion process can be written as $(x,y) \rightarrow (x-y,x) \rightarrow (y,x-y)$, increasing the length of the sequence by $2$, completing one iteration of subtraction.
    718 
    719 When $x \le y$, the recursion process can be written as $(x,y) \rightarrow (y-x,x)$, increasing the length of the sequence by $1$, completing one iteration of subtraction.
    720 
    721 The process will eventually lead to $(x,0)$ or $(0,x)$, where $x$ is the GCD of $A_m$ and $A_{m−1}$.
    722 
    723 When $A_m$ and $A_{m−1}$ are coprime, we have $x=1$, meeting the requirements for the sequence. In fact, we can stop earlier when $(1,2)$, and the sequence is still legal.
    724 
    725 When $A_m$ and $A_{m−1}$ are not coprime, we have $x \gt 1$, and this method can't obtain a sequence that meets the requirements.
    726 
    727 **Step 3**
    728 
    729 Given $A_m=n$, we need to find a suitable $A_{m−1}$ such that the length of the final sequence is less than or equal to $80$.
    730 
    731 Since $80$ is a relaxed constraint, and you only need to find one valid $A_{m−1}$, you can try various approaches.
    732 
    733 For example, you could enumerate all possibilities within the range $[1, n-1]$ for some large $n$, and then discover that there are many valid $A_{m−1}$ values that meet the criteria.
    734 
    735 If you randomly search for $A_{m−1}$ within the range, the expected number of attempts required is very low. In fact, the verification program tested all integers $n$ from $10$ to $10^7$, randomly selecting $1000$ possible $A_{m−1}$ values for each n and testing them. The results showed that in the worst case (when $n = 9827370$), there were still $24$ valid $A_{m−1}$ values that met the requirements out of the $1000$ randomly chosen values.
    736 
    737 **Code (C++)**
    738 
    739 Code:
    740 
    741 ```
    742 #include<bits/stdc++.h>
    743 using namespace std;
    744 int fl[1005],inf=1e9,cnt;
    745 int work(int x,int y){
    746     int ans=0,tmp;
    747     while(y&&ans<=80){
    748         ++ans; tmp=y;
    749         if (x>y) y=x-y; else y=y-x;
    750         x=tmp;
    751     }
    752     if (x>1) return inf;
    753     return ans;
    754 }
    755 void gen(int x,int y){
    756     //printf("%d\n",work(x,y));
    757     vector<int> seq; seq.clear(); seq.push_back(x); seq.push_back(y);
    758     int tmp;
    759     while(!(x==2&&y==1)){
    760         tmp=y;
    761         if (x>y) y=x-y; else y=y-x;//x=tmp;
    762         x=tmp; 
    763         seq.push_back(y);
    764     }
    765     int ans[105][105]={0};
    766     int pre=seq.back(),n=1; seq.pop_back(); ans[1][1]=1;
    767     while(!seq.empty()){
    768         ++n;
    769         if (seq.back()>pre) ans[n][n]=1,ans[n][n-1]=1,ans[n-1][n]=-1;
    770         else ans[n][n]=1,ans[n][n-1]=1,ans[n-1][n]=1;
    771         pre=seq.back(); seq.pop_back();
    772     }
    773     printf("%d\n",n);
    774     for(int i=1;i<=n;++i){
    775         for(int j=1;j<=n;++j){
    776             printf("%d ",ans[i][j]);
    777         }
    778         printf("\n");
    779     }
    780 }
    781 int main(){
    782     int _; cin>>_; mt19937 rd(time(0));
    783     while(_--){
    784         int n; cin>>n;
    785         if (n==0) {printf("1\n0\n"); continue;}
    786         if (n==1) {printf("1\n1\n"); continue;}
    787         while(1){
    788             int y=rd()%(n-1)+1;
    789             int tmp=work(n,y);
    790             if (tmp<=80) {gen(n,y); break;}
    791         }
    792     }
    793     return 0;
    794 }
    795 ```
    796 
    797 Verification Program:
    798 
    799 ```
    800 #pragma GCC optimize(3)
    801 #include<bits/stdc++.h>
    802 using namespace std;
    803 int inf=1e9;
    804 int work(int x,int y){
    805     int ans=0,tmp;
    806     while(y&&ans<=80){
    807         ++ans; tmp=y;
    808         if (x>y) y=x-y; else y=y-x;
    809         x=tmp;
    810     }
    811     if (x>1) return inf;
    812     return ans;
    813 }
    814 int main(){
    815     mt19937 rd(114514);
    816     int n=1e7,minn=1e3;
    817     for(int x=n;x>=5;x--){
    818         int _=1e3,c=0;
    819         while(_--){
    820             int y=rd()%(x-1)+1;
    821             int tmp=work(x,y);
    822             if (tmp<=80) ++c;
    823         }
    824         if (c<minn) minn=c,cout<<' '<<minn<<' '<<x<<endl;
    825         if (x%10000==1) cout<<clock()<<'#'<<x<<endl;
    826     }
    827     return 0;
    828 }
    829 ```
    830 
    831 **Rate this problem**
    832 
    833 * Amazing problem:
    834 * Good problem:
    835 * Average problem:
    836 * Bad problem:
    837 * Horrible problem:
    838 
    839 [2139E2 — Determinant Construction (Hard Version)](https://codeforces.com/contest/2138/problem/E2)
    840 
    841 Idea: [wjy666](/profile/wjy666 "Master wjy666") Preparation: [wjy666](/profile/wjy666 "Master wjy666")
    842 
    843 Since $50$ is a very tight constraint, the author did not find a method to construct the DAG for G2 as in Solution 1 of G1. If you have a better solution, please leave a comment below.
    844 
    845 **Hint**
    846 
    847 In Solution 2, the first two steps remain consistent with G1, but we need a better method to find a suitable $A_{m−1}$ such that the length of the final sequence is less than or equal to $50$. Randomly searching for $A_{m−1}$ within the range $[1, n-1]$ may result in TLE.
    848 
    849 We noticed that if $A_{m−1}$ and $A_m$ are two adjacent fibonacci numbers, the sequence will converge rapidly (with a length within $40$). Although not all $A_m=n$ are fibonacci numbers, we can still draw inspiration from this.
    850 
    851 **Solution A**
    852 
    853 We attempt to decompose $n$ as $n=a \cdot \operatorname{fib}(i)+b \cdot \operatorname{fib}(i-1), a,b \ge 0$, where $\operatorname{fib}(i)$ denotes the $i$-th fibonacci number.
    854 
    855 Then, we set $A_{m-1}=a \cdot \operatorname{fib}(i-1)+b \cdot \operatorname{fib}(i-2)$
    856 
    857 By iterating further, we obtain $A_{m-2}=a \cdot \operatorname{fib}(i-2)+b \cdot \operatorname{fib}(i-3)$, $\dots$
    858 
    859 The purpose of this is to make the iteration process rapidly decrease the value in the initial steps, similar to the fibonacci sequence. Intuitively, the larger the $i$ chosen, the higher the probability of finding a legal $A_{m-1}$.
    860 
    861 The author did not provide a rigorous mathematical proof for this, but using a verification program which found a legal $A_{m-1}$ for all $A_m=n \in [2,10^7]$ within one minute. Therefore, it is feasible to prove the correctness of this approach within the data range during the contest.
    862 
    863 **Code (C++)**
    864 
    865 ```
    866 #include<bits/stdc++.h>
    867 using namespace std;
    868 int fl[1005],inf=1e9,cnt;
    869 int work(int x,int y){
    870     int ans=0,tmp;
    871     while(y&&ans<=50){
    872         ++ans; tmp=y;
    873         if (x>y) y=x-y; else y=y-x;
    874         x=tmp;
    875     }
    876     if (x>1) return inf;
    877     return ans;
    878 }
    879 void gen(int x,int y){
    880     //printf("%d\n",work(x,y));
    881     vector<int> seq; seq.clear(); seq.push_back(x); seq.push_back(y);
    882     int tmp;
    883     while(!(x==2&&y==1)){
    884         tmp=y;
    885         if (x>y) y=x-y; else y=y-x;//x=tmp;
    886         x=tmp; 
    887         seq.push_back(y);
    888     }
    889     int ans[55][55]={0};
    890     int pre=seq.back(),n=1; seq.pop_back(); ans[1][1]=1;
    891     while(!seq.empty()){
    892         ++n;
    893         if (seq.back()>pre) ans[n][n]=1,ans[n][n-1]=1,ans[n-1][n]=-1;
    894         else ans[n][n]=1,ans[n][n-1]=1,ans[n-1][n]=1;
    895         pre=seq.back(); seq.pop_back();
    896     }
    897     printf("%d\n",n);
    898     for(int i=1;i<=n;++i){
    899         for(int j=1;j<=n;++j){
    900             printf("%d ",ans[i][j]);
    901         }
    902         printf("\n");
    903     }
    904 }
    905 typedef long long ll;
    906 ll fib[55]={1,1};
    907 ll exgcd(ll a,ll b,ll &x,ll &y){
    908 	if(!b){
    909 		x=1; y=0; return a;
    910 	}
    911 	ll d=exgcd(b,a%b,y,x);
    912 	y-=(a/b)*x;
    913 	return d;
    914 }
    915 map<int,int> mp;
    916 int main(){
    917     for(int i=2;i<=50;++i) fib[i]=fib[i-1]+fib[i-2];
    918     int _; cin>>_;
    919     while(_--){
    920         int n; cin>>n;
    921         if (n==0) {printf("1\n0\n"); continue;}
    922         if (n==1) {printf("1\n1\n"); continue;}
    923         if (n<=10){
    924             gen(n,n-1); continue;
    925         }
    926         if (mp[n]) {gen(n,mp[n]); continue;}
    927         int noww=0;
    928         while(fib[noww]<n) ++noww;
    929         int now=noww;
    930         while(now>=3){
    931             ll a=fib[now-1],b=fib[now-2],x,y,c=n;
    932             ll d=exgcd(a,b,x,y);
    933             x*=c,y*=c;
    934             //find x,y
    935             x=(x%b+b)%b;  y=(c-a*x)/b; if (y<0) {--now; continue;}
    936             int s=inf,o;
    937             while(y>=0){
    938                 o=fib[now-2]*x+fib[now-3]*y;
    939                 s=work(n,o);
    940                 if (s>50) {x+=b,y-=a; continue;}
    941                 else break;
    942             }
    943             if (s>50) {--now; continue;}
    944             else{
    945                 gen(n,o); mp[n]=o; break;
    946             }
    947         }
    948         //
    949     }
    950     return 0;
    951 }
    952 ```
    953 
    954 **Solution B**
    955 
    956 We note that for the fibonacci sequence, $\lim_{x \to \infty} \frac{\operatorname{fib}(x-1)}{\operatorname{fib}(x)} = \frac{\sqrt 5 -1}{2}$, which suggests that searching for $A_{m-1}$ around $\frac{\sqrt 5 -1}{2}n$ might be a promising approach.
    957 
    958 In fact, directly enumerating $A_{m-1}$ starting from $\frac{\sqrt 5 -1}{2}n$ and trying each one is a efficient method. The author also verified through a verification program that for all $A_m=n \in [2,10^7]$, a legal $A_{m-1}$ was found within one minute. Thus, it is feasible to prove the correctness of this approach within the data range during the contest.
    959 
    960 Considering that the time limit for this problem is relatively loose (5s), most attempts to search for $A_{m-1}$ around $\frac{\sqrt 5 -1}{2}n$ may be able to pass.
    961 
    962 **Code (C++)**
    963 
    964 ```
    965 #include<bits/stdc++.h>
    966 using namespace std;
    967 int fl[1005],inf=1e9,cnt;
    968 int work(int x,int y){
    969     int ans=0,tmp;
    970     while(y&&ans<=50){
    971         ++ans; tmp=y;
    972         if (x>y) y=x-y; else y=y-x;
    973         x=tmp;
    974     }
    975     if (x>1) return inf;
    976     return ans;
    977 }
    978 void gen(int x,int y){
    979     //printf("%d\n",work(x,y));
    980     vector<int> seq; seq.clear(); seq.push_back(x); seq.push_back(y);
    981     int tmp;
    982     while(!(x==2&&y==1)){
    983         tmp=y;
    984         if (x>y) y=x-y; else y=y-x;//x=tmp;
    985         x=tmp; 
    986         seq.push_back(y);
    987     }
    988     int ans[55][55]={0};
    989     int pre=seq.back(),n=1; seq.pop_back(); ans[1][1]=1;
    990     while(!seq.empty()){
    991         ++n;
    992         if (seq.back()>pre) ans[n][n]=1,ans[n][n-1]=1,ans[n-1][n]=-1;
    993         else ans[n][n]=1,ans[n][n-1]=1,ans[n-1][n]=1;
    994         pre=seq.back(); seq.pop_back();
    995     }
    996     printf("%d\n",n);
    997     for(int i=1;i<=n;++i){
    998         for(int j=1;j<=n;++j){
    999             printf("%d ",ans[i][j]);
   1000         }
   1001         printf("\n");
   1002     }
   1003 }
   1004 map<int,int> mp;
   1005 int main(){
   1006     int _; cin>>_;
   1007     while(_--){
   1008         int n; cin>>n;
   1009         if (n==0) {printf("1\n0\n"); continue;}
   1010         if (n==1) {printf("1\n1\n"); continue;}
   1011         if (mp[n]) {gen(n,mp[n]); continue;}
   1012         double s=(sqrt(5)-1.0)/2.0;
   1013         int st=s*n,l=max(1,st),r=n-1;
   1014         //int l=1,r=n-1;
   1015         int nowy,nows=50;
   1016         if (n%2==0){
   1017             if (l%2==0) ++l;
   1018             for(int y=l;y<=r;y+=2){
   1019                 int tmp=work(n,y);
   1020                 if (tmp<=nows) {gen(n,y); mp[n]=y; break;}
   1021             }
   1022         }
   1023         else{
   1024             for(int y=l;y<=r;++y){
   1025                 int tmp=work(n,y);
   1026                 if (tmp<=nows) {gen(n,y); mp[n]=y; break;}
   1027             }
   1028         }
   1029     }
   1030     return 0;
   1031 }
   1032 ```
   1033 
   1034 **Rate this problem**
   1035 
   1036 * Amazing problem:
   1037 * Good problem:
   1038 * Average problem:
   1039 * Bad problem:
   1040 * Horrible problem:
   1041 
   1042 [2139F — Ode to the Bridge Builder](https://codeforces.com/contest/2138/problem/F)
   1043 
   1044 Idea: [installb](/profile/installb "Grandmaster installb") Preparation: [installb](/profile/installb "Grandmaster installb")
   1045 
   1046 **Solution**
   1047 
   1048 For convenience, we mark the targets point and the points on the initial segment with $A(0,0),B(1,0),C(p,q)$.
   1049 
   1050 The problem asks us to do at most $\left\lceil 2|AC|\right\rceil$ moves. This constraint is actually not quite usual. We can first show that the theoretical lower bound should be $x=\left\lceil |AC|\right\rceil+\left\lceil |BC|\right\rceil−1$. We can show we can't get less moves by following: If we have already constructed the final structure, then $AC$ and $BC$ should be connected with a path, and we can find a path from $A$ to $C$ and a path from $B$ to $C$ that don't intersect (except at point $C$), otherwise the structure can't be built with non-degenerate triangles.
   1051 
   1052 And we have to alternate progressing through two paths every time we construct a triangle, otherwise we must draw a line longer than $1$. The last triangle will cover both paths, so the number of steps will be decreased by one. The optimal path is two straight segments (which is not always possible).
   1053 
   1054 **Case 1.1:** We first try some simple strategies. Two triangles can form a parallelogram, so we can connect $AC$, choose a point $D$ on $AC$ which makes $|AD|=\frac{|AC|}{\lceil|AC|\rceil}$, which is always in range $[0.5,1]$ when $|AC|\ge 1$. And from $\triangle ADB$ we can construct a parallelogram. We draw a line passing $D$ that is parallel to $AB$, a line passing $B$ that is parallel to $AC$, and they intersect at $E$. Then we pile up the same parallelogram structure until we reach $C$. This always works when $30^\circ\le\angle CAB\le60^\circ$.
   1055 
   1056 Proof: We first prove that all segments have length between $0.5$ and $1$. Because we stack the same parallelogram structure, all segments have length equal to $AB,BD$ or $AD$. $AB$ and $AD$ already meet the requirement. When $30^\circ\le\angle CAB\le60^\circ$, the length of $BD$ is at least $0.5$ as the distance between two parallel lines is at least $0.5$, and at most $1$ as $AB=1$ and $\angle CAB$ is never the largest angle in $\triangle DAB$. We can calculate that the number of moves we used is $2\left\lceil |AC|\right\rceil-1\le\left\lceil 2|AC|\right\rceil$ which matches the requirement (for the last parallelogram we only need one triangle).
   1057 
   1058 ![ ](/predownloaded/a6/c3/a6c3323e11dddf322cfc8b3188b3564471665a92.png)
   1059 
   1060 **Case 1.2:** We can change the way we construct parallelograms (with sides $AB,BC$) and this method always works when $30^\circ\le\angle CBx\le60^\circ$. The number of moves is $\left\lceil2|BC|\right\rceil\le \left\lceil 2|AC|\right\rceil$. This case is actually necessary, which will be explained in the following part.
   1061 
   1062 ![ ](/predownloaded/d5/83/d583339323c45df6492d338f0b207b364d914a94.png)
   1063 
   1064 **Case 2:** If $\angle CAB \lt \angle CBx \lt 30^\circ$. We first build a point $D$ which makes $AD=1$ and $\angle DAB=30^\circ$ and construct $\triangle DAB$.
   1065 
   1066 We can show that the constraint is actually easier to meet in this situation, because when $\angle CAB \lt \angle CBx \lt 30^\circ$, $|BC| \lt |AC|-0.5$. With this, $\left\lceil |AC|\right\rceil+\left\lceil |BC|\right\rceil−1=\left\lceil 2|AC|\right\rceil-1$ always holds, allowing us one extra move.
   1067 
   1068 Then we draw a line passing $D$ parallel to $BC$. We can show that if $\angle DAB=30^\circ$ and $0\le \angle CAB\le 30^\circ$, the distance from $D$ to line $BC$ is at least $0.5$. So all segments with ends on different lines will have length $\ge 0.5$.
   1069 
   1070 Then we select a point $E$ on $BC$, which makes $DE=1$. We can show that $\sqrt{3}-1\le |BE|\le 1$ based on some calculations in this case. Then we do a similar parallelogram construction process to $C$. The total number of moves is $2\left\lceil |CE|\right\rceil+2$.
   1071 
   1072 There are still two cases here to analyze to prove the number of steps fulfills our requirement. We write $|BC|=a+b$ where $a$ is the integer part of $|BC|$, then we analyze cases about $b$.
   1073 
   1074 * Case 2.1: When $b\ge\sqrt{3}-1$ or $b=0$, we can show that $2\left\lceil |AC|\right\rceil=\left\lceil 2|AC|\right\rceil$, and $\left\lceil |AC|\right\rceil=\left\lceil |BC|\right\rceil+1$ if $|AC|\ge 2$. The number of steps is $2\left\lceil |EC|\right\rceil+2\le 2\left\lceil |BC|\right\rceil+2=2\left\lceil |AC|\right\rceil$.
   1075 * Case 2.2: When $0 \lt b \lt \sqrt{3}-1$, we can show that $\left\lceil |EC|\right\rceil=\left\lceil |BC|\right\rceil-1$. The number of steps equals to $2+2\left\lceil |CE|\right\rceil=2\left\lceil |BC|\right\rceil\le \left\lceil |AC|\right\rceil+\left\lceil |BC|\right\rceil=\left\lceil 2|AC|\right\rceil$.
   1076 
   1077 Be careful with small cases where $|BC|$ is too short, which may make $|DF|=|EG| \lt 0.5$.
   1078 
   1079 Note that there are some cases where $\angle CBx \gt 30^\circ$ and $\angle CAB \lt 30^\circ$, where Case 2 strategy doesn't work. So case 1.2 is required.
   1080 
   1081 ![ ](/predownloaded/90/b2/90b2870a0ecc7f858552a5f8066e80cf47cc8494.png)
   1082 
   1083 **Case 3:** If $\angle CBx \gt \angle CAB \gt 60^\circ$. We first build a point $D$ which makes $AD=1$ and $\angle DAB=60^\circ$ and construct $\triangle DAB$. We write $|AC|=a+b$ where $a$ is integer, then we analyze two cases about $b$.
   1084 
   1085 **Case 3.1:** When $b \gt 0.5$ or $b=0$, $2\left\lceil |AC|\right\rceil=\left\lceil 2|AC|\right\rceil$. We begin a same parallelogram construction as Case 1 where the sides of parallelogram are $BC,BD$. We can show that $30^\circ\le\angle CBD\le60^\circ$. So it is possible to pile up to $C$ from $BD$ in $2\left\lceil |BC|\right\rceil-1$ moves. And in total we need $2\left\lceil |BC|\right\rceil\le2\left\lceil |AC|\right\rceil=\left\lceil 2|AC|\right\rceil$ moves.
   1086 
   1087 ![ ](/predownloaded/8c/dc/8cdc022ad3b685b90fac0681039b0ac07a8e8d76.png)
   1088 
   1089 **Case 3.2:** When $0 \lt b\le 0.5$, $2\left\lceil |AC|\right\rceil=\left\lceil 2|AC|\right\rceil+1$. We instead connect $CD$ and construct parallelogram with sides $DC,DB$. We can show that $120^\circ\le\angle CDB\le150^\circ$ so we can still do the parallelogram construction. When $|AC|\ge \sqrt{3}$, $\left\lceil |CD|\right\rceil=\left\lceil |AC||\right\rceil-1$, making the number of moves $2\left\lceil |CD|\right\rceil+1=2\left\lceil |AC|\right\rceil-1=\left\lceil 2|AC|\right\rceil$.
   1090 
   1091 ![ ](/predownloaded/18/39/18399c9d645d5245f21b9eb4559d9f6361683585.png)
   1092 
   1093 Actually case 1.1 is not required, because it is impossible to construct a testcase where $\angle CAB \lt 60^\circ, \angle CBx \gt 60^\circ,0 \lt b\le 0.5$ and Case 3.2 fails.
   1094 
   1095 **Code (C++)**
   1096 
   1097 ```
   1098 #include <bits/stdc++.h>
   1099 using namespace std;
   1100 typedef double db;
   1101 const db pi = acos(-1.0);
   1102 const int N = 1000005;
   1103 
   1104 inline int sgn(db x){
   1105     if(x < 1e-13 && x > -1e-13) return 0;
   1106     if(x > 0) return 1;
   1107     return -1;
   1108 }
   1109 
   1110 struct point{
   1111     db x,y;
   1112     point (db _x = 0.0,db _y = 0.0) : x(_x), y(_y) {}
   1113 };
   1114 point operator + (const point &p1,const point &p2){
   1115 	return point(p1.x + p2.x,p1.y + p2.y);
   1116 }
   1117 point operator - (const point &p1,const point &p2){
   1118 	return point(p1.x - p2.x,p1.y - p2.y);
   1119 }
   1120 point operator * (db x,const point &p){
   1121 	return point(x * p.x,x * p.y);
   1122 } 
   1123 bool operator == (point x,point y){
   1124 	return sgn(x.x - y.x) == 0 && sgn(x.y - y.y) == 0;
   1125 }
   1126 
   1127 inline db dot(point p1,point p2){
   1128     return p1.x * p2.x + p1.y * p2.y;
   1129 }
   1130 
   1131 inline db det(point p1,point p2){
   1132 	return p1.x * p2.y - p2.x * p1.y;
   1133 }
   1134 
   1135 inline db len(point p){
   1136     return sqrtl(1.0 * p.x * p.x + 1.0 * p.y * p.y);
   1137 }
   1138 
   1139 point project_point(point x,point ya,point yb){
   1140 	point v = yb - ya;
   1141 	return ya + (dot(v,x - ya) / dot(v,v)) * v;
   1142 }
   1143 
   1144 db distp(point x,point ya,point yb){
   1145 	return fabs(det(ya - x,yb - x)) / len(yb - ya);
   1146 }
   1147 
   1148 point line_circle_intersec_point(point o,point la,point lb){
   1149 	db dis = distp(o,la,lb),l;
   1150 	point pj = project_point(o,la,lb);
   1151 	l = sqrt(1.0 - dis * dis);
   1152 	point ret = pj + (l / len(lb - la)) * (lb - la);
   1153 	return ret;
   1154 }
   1155 
   1156 tuple <int,int,int> ans[N];
   1157 point p[N],target;
   1158 int step;
   1159 
   1160 bool check(int n){
   1161     set <pair <int,int> > st;
   1162     st.insert({1,2});
   1163     if(n > step) return 0;
   1164     db eps_len = 1e-8,eps_dis = 1e-4;
   1165     int fl = 0;
   1166     for(int i = 1;i <= n;i ++){
   1167         auto [u,v,w] = ans[i];
   1168         if(u > v) swap(u,v);
   1169         if(st.find({u,v}) == st.end()) return 0;
   1170         if(len(p[u] - p[w]) < 0.5 - eps_len || len(p[u] - p[w]) > 1.0 + eps_len) return 0;
   1171         if(len(p[v] - p[w]) < 0.5 - eps_len || len(p[v] - p[w]) > 1.0 + eps_len) return 0;
   1172         st.insert({u,w}); st.insert({v,w});
   1173         if(len(p[w] - target) <= eps_dis) fl = 1;
   1174     }
   1175     return 1;
   1176 }
   1177 
   1178 int solve1a(){
   1179     point dir = target - p[1];
   1180     int split = ceil(len(dir) - 1e-9);
   1181     int c = 2;
   1182     for(int i = 1;i < split;i ++){
   1183         ++ c; p[c] = p[1] + (1.0 * i / split) * dir;
   1184         ans[c - 2] = {c - 2,c - 1,c};
   1185         ++ c; p[c] = p[2] + (1.0 * i / split) * dir;
   1186         ans[c - 2] = {c - 2,c - 1,c};
   1187         // construct one parallelogram
   1188     }
   1189     ++ c; p[c] = target;
   1190     ans[c - 2] = {c - 2,c - 1,c};
   1191     if(check(c - 2)) return c - 2;
   1192     return 0;
   1193 }
   1194 
   1195 int solve1b(){
   1196     point dir = target - p[2];
   1197     int split = ceil(len(dir) - 1e-9);
   1198     int c = 2;
   1199     for(int i = 1;i <= split;i ++){
   1200         ++ c; p[c] = p[1] + (1.0 * i / split) * dir;
   1201         ans[c - 2] = {c - 2,c - 1,c};
   1202         ++ c; p[c] = p[2] + (1.0 * i / split) * dir;
   1203         ans[c - 2] = {c - 2,c - 1,c};
   1204     }
   1205     if(check(c - 2)) return c - 2;
   1206     return 0;
   1207 }
   1208 
   1209 int solve2(){
   1210     p[3] = point(sqrt(3.0) / 2,0.5);
   1211     p[4] = line_circle_intersec_point(p[3],p[2],target);
   1212     if(len(p[4] - p[2]) > 1)
   1213         p[4] = p[2] + (1.0 / len(target - p[2])) * (target - p[2]);
   1214     ans[1] = {1,2,3};
   1215     ans[2] = {2,3,4};
   1216     point dir = target - p[4];
   1217     int split = ceil(len(dir) - 1e-9);
   1218     int c = 4;
   1219     for(int i = 1;i <= split;i ++){
   1220         ++ c; p[c] = p[3] + (1.0 * i / split) * dir;
   1221         ans[c - 2] = {c - 2,c - 1,c};
   1222         ++ c; p[c] = p[4] + (1.0 * i / split) * dir;
   1223         ans[c - 2] = {c - 2,c - 1,c};
   1224     }
   1225     if(check(c - 2)) return c - 2;
   1226     return 0;
   1227 }
   1228 
   1229 int solve3a(){
   1230     p[3] = point(0.5,sqrt(3.0) / 2);
   1231     ans[1] = {1,2,3};
   1232     point dir = target - p[2];
   1233     int split = ceil(len(dir) - 1e-9);
   1234     int c = 3;
   1235     for(int i = 1;i < split;i ++){
   1236         ++ c; p[c] = p[2] + (1.0 * i / split) * dir;
   1237         ans[c - 2] = {c - 2,c - 1,c};
   1238         ++ c; p[c] = p[3] + (1.0 * i / split) * dir;
   1239         ans[c - 2] = {c - 2,c - 1,c};
   1240     }
   1241     ++ c; p[c] = target;
   1242     ans[c - 2] = {c - 2,c - 1,c};
   1243     if(check(c - 2)) return c - 2;
   1244     return 0;
   1245 }
   1246 
   1247 int solve3b(){
   1248     p[3] = point(0.5,sqrt(3.0) / 2);
   1249     ans[1] = {1,2,3};
   1250     point dir = target - p[3];
   1251     int split = ceil(len(dir) - 1e-9);
   1252     int c = 3;
   1253     for(int i = 1;i <= split;i ++){
   1254         ++ c; p[c] = p[2] + (1.0 * i / split) * dir;
   1255         ans[c - 2] = {c - 2,c - 1,c};
   1256         ++ c; p[c] = p[3] + (1.0 * i / split) * dir;
   1257         ans[c - 2] = {c - 2,c - 1,c};
   1258     }
   1259     if(check(c - 2)) return c - 2;
   1260     return 0;
   1261 }
   1262 
   1263 int solve(){
   1264     if(int res = solve1a()) return res;
   1265     if(int res = solve1b()) return res;
   1266     if(int res = solve2()) return res;
   1267     if(int res = solve3a()) return res;
   1268     if(int res = solve3b()) return res;
   1269     return 0;
   1270 }
   1271 
   1272 int main(){
   1273     int TC; scanf("%d",&TC);
   1274     p[1] = point(0,0);
   1275     p[2] = point(1,0);
   1276     while(TC --){
   1277         int tx,ty;
   1278         scanf("%d %d %d",&tx,&ty,&step);
   1279         step = ceil(2.0 * sqrt(1.0 * tx * tx + 1.0 * ty * ty));
   1280         target = point(tx,ty);
   1281         int n = solve();
   1282         assert(n > 0);
   1283         printf("%d\n",n);
   1284         for(int i = 1;i <= n;i ++){
   1285             auto [u,v,w] = ans[i];
   1286             printf("%d %d %.12lf %.12lf\n",u,v,p[w].x,p[w].y);
   1287         }
   1288     }
   1289     return 0;
   1290 }
   1291 ```
   1292 
   1293 **Rate this problem**
   1294 
   1295 * Amazing problem:
   1296 * Good problem:
   1297 * Average problem:
   1298 * Bad problem:
   1299 * Horrible problem: