codeforces-scrape

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

2215.md (28749B)


      1 Source: https://codeforces.com/blog/entry/152930
      2 
      3 We apologize for both the late editorial and the statement leaking issues. Unfortunately, as the problem authors, we never had any chances to prevent the leaking. Still, feel free to downvote if you have dissatisfaction due to these.
      4 
      5 But what so ever, we hope you can enjoy the problems.
      6 
      7 [2216A - Course Wishes](/contest/2216/problem/A)
      8 
      9 Idea by [Warriors_Cat](/profile/Warriors_Cat "Candidate Master Warriors_Cat")
     10 
     11 **Solution**
     12 
     13 The method is simple: for $i = k, k - 1, \dots, 1$ successively, we adjust the courses at the $i$-th level of course wish one by one directly to the $(k+1)$-th level. It is easy to check that the adjustment is valid.
     14 
     15 The number of steps is at most $nk \le 1000$.
     16 
     17 **Code(C++)**
     18 
     19 ```
     20 #include <iostream>
     21 #include <cstdio>
     22 #include <algorithm>
     23 #include <cstring>
     24 #include <cstdlib>
     25 using namespace std;
     26 #define ll long long
     27 #define rep(i, x, y) for(int i = x; i <= y; ++i)
     28 #define per(i, x, y) for(int i = x; i >= y; --i)
     29 inline int read(){
     30     int x = 0, f = 1; char ch = getchar();
     31     while(ch < '0' || ch > '9'){ if(ch == '-') f = -1; ch = getchar(); }
     32     while(ch >= '0' && ch <= '9'){ x = x * 10 + (ch ^ 48); ch = getchar(); }
     33     return x * f;
     34 }
     35 const int N = 55, M = 25, K = 1010;
     36 int n, k, a[M], b[N], c[N];
     37 int p[M][N], q[M][N], lenp[M], lenq[M];
     38 int cnt, x[K], y[K];
     39 inline void mian(){
     40     memset(a, 0, sizeof(a)); memset(b, 0, sizeof(b));
     41     memset(lenp, 0, sizeof(lenp));
     42     n = read(); k = read();
     43     rep(i, 1, k) a[i] = read();
     44     rep(i, 1, n) b[i] = read(), p[b[i]][++lenp[b[i]]] = i;
     45     cnt = 0;
     46     per(i, k, 1){
     47         int len = lenp[i];
     48         rep(j, 1, len){
     49             rep(l, i, k){
     50                 x[++cnt] = p[i][j];
     51             }
     52         }
     53     }
     54     printf("%d\n", cnt);
     55     rep(i, 1, cnt) printf("%d ", x[i]);
     56     puts("");
     57     return;
     58 }
     59 int main(){ int qwq = read(); while(qwq--) mian(); return 0; }
     60 ```
     61 
     62 [2216B - THU Packing Puzzle](/contest/2216/problem/B)
     63 
     64 Idea by [E.Space](/profile/E.Space "International Master E.Space")
     65 
     66 **Solution**
     67 
     68 Combining T with U decreases $n$ by $2$. Combining T with H decreases $n$ by 1. One H can be inserted from both directions. Combining k rotated T's decreases $n$ by $k-1$. THUs, if $c_T \gt c_U+2c_H$, the answer will be $2c_T+3c_H+2c_U+1$; otherwise, the answer will be $2c_T+3c_H+3c_U-\min{c_T,c_U}$.
     69 
     70 **Code(C++)**
     71 
     72 ```
     73 #include<bits/stdc++.h>
     74 #define cmin(a,b) (a>(b)?a=(b),1:0)
     75 #define cmax(a,b) (a<(b)?a=(b),1:0)
     76 #define dmin(a,b) ((a)<(b)?(a):(b))
     77 #define dmax(a,b) ((a)>(b)?(a):(b))
     78 namespace io{
     79 	int F(){
     80 		int n=0,F=0;
     81 		char ch;
     82 		while((ch=getchar())!='-'&&(ch<'0'||ch>'9'));
     83 		ch=='-'?F=1:n=ch-'0';
     84 		while((ch=getchar())>='0'&&ch<='9')n=n*10+ch-'0';
     85 		return F?-n:n;
     86 	}
     87 	long long G(){
     88 		long long n=0,F=0;
     89 		char ch;
     90 		while((ch=getchar())!='-'&&(ch<'0'||ch>'9'));
     91 		ch=='-'?F=1:n=ch-'0';
     92 		while((ch=getchar())>='0'&&ch<='9')n=n*10+ch-'0';
     93 		return F?-n:n;
     94 	}
     95 }
     96 int main(){
     97 	int T=io::F();
     98 	while(T--){
     99         long long t=io::F(),h=io::F(),u=io::F();
    100         if(t>h*2+u){
    101             printf("%lld\n",t*2+h*3+u*2+1);
    102         }
    103         else{
    104             printf("%lld\n",t*2+h*3+u*3-dmin(t,u));
    105         }
    106 	}
    107 	return 0;
    108 }
    109 ```
    110 
    111 [2215A - Interval Mod](/contest/2215/problem/A)
    112 
    113 Idea by [Ecrade_](/profile/Ecrade_ "Grandmaster Ecrade_")
    114 
    115 **Solution**
    116 
    117 Each $a_i$ can only end up as either $b_i = a_i \bmod p$ or $c_i = (a_i \bmod q) \bmod p$.
    118 
    119 We can see that except for the first chosen interval where all numbers must simultaneously become $b_i$ or simultaneously become $c_i$, all other numbers can become $\min(b_i, c_i)$.
    120 
    121 Greedily, it is never worse to choose the first interval to have length exactly $k$. Enumerate all intervals of length $k$, compute the result, and take the minimum. The final answer is:
    122 
    123 $ \min\limits_{r-l+1=k}\left(\sum\limits_{i\not\in[l,r]}\min(b_i,c_i)+\min\left(\sum\limits_{i\in[l,r]} b_i,\sum\limits_{i\in[l,r]} c_i\right)\right) $
    124 
    125 Using prefix sums for preprocessing, the time complexity is $\mathcal{O}(n)$.
    126 
    127 **Code(C++)**
    128 
    129 ```
    130 #include<bits/stdc++.h>
    131 using namespace std;
    132 typedef long long ll;
    133 ll t,n,k,p,q,a[100009],f[100009][2],g[100009];
    134 inline ll read(){
    135 	ll s = 0,w = 1;
    136 	char ch = getchar();
    137 	while (ch > '9' || ch < '0'){ if (ch == '-') w = -1; ch = getchar();}
    138 	while (ch <= '9' && ch >= '0') s = (s << 1) + (s << 3) + (ch ^ 48),ch = getchar();
    139 	return s * w;
    140 }
    141 int main(){
    142 	t = read();
    143 	while (t --){
    144 		ll ans = 1e18;
    145 		n = read(),k = read(),p = read(),q = read();
    146 		for (ll i = 1;i <= n;i += 1) a[i] = read();
    147 		for (ll i = 1;i <= n;i += 1) f[i][0] = a[i] % p % q,f[i][1] = a[i] % q % p;
    148 		for (ll i = 1;i <= n;i += 1) g[i] = g[i - 1] + min(f[i][0],f[i][1]);
    149 		for (ll i = 1;i <= n;i += 1) f[i][0] += f[i - 1][0],f[i][1] += f[i - 1][1];
    150 		for (ll i = k;i <= n;i += 1) ans = min(ans,min(f[i][0] - f[i - k][0],f[i][1] - f[i - k][1]) + g[i - k] + g[n] - g[i]);
    151 		printf("%lld\n",ans);
    152 	}
    153 	return 0;
    154 }
    155 ```
    156 
    157 [2215B - RReeppeettiittiioonn](/contest/2215/problem/B)
    158 
    159 Idea by [SpiritualKhorosho](/profile/SpiritualKhorosho "Candidate Master SpiritualKhorosho")
    160 
    161 **Solution**
    162 
    163 Divide the situations based on $k$:
    164 
    165 * $k=2$: $n=\sum\limits_{i=1}^{m}b^{i-1}(b+1)p_i$ must be a multiple of $b+1$, so enumerate factor of $n$.
    166 * $k\ge 3$: Similarly we can know $(b^{k-1}+\cdots+b+1)|n$,which implies $b\le \sqrt[k-1]{n}$,so enumerate $b$.
    167 
    168 Time complexity is $O\left(\sqrt{n}\right)$
    169 
    170 **Code(C++)**
    171 
    172 ```
    173 #include <cstdio>
    174 using namespace std;
    175 int check(long long n, long long b, int p) {
    176 	while (n) {
    177 		long long r = n % b;
    178 		n /= b;
    179 		for (int i = 1; i < p; ++i) {
    180 			if (n % b != r) return 0;
    181 			n /= b;
    182 		}
    183 	}
    184 	return 1;
    185 }
    186 int main(){
    187 	long long n, sum, pow;
    188 	int T, i, j, k, ans;
    189 	scanf("%d", &T);
    190 	while (T--) {
    191 		scanf("%lld", &n);
    192 		if (n <= 2) {
    193 			puts("0");
    194 			continue;
    195 		}
    196 		ans = 1;
    197 		if ((n & 1) == 0 && n >= 8) ans = 2;
    198 		for (i = 3; 1ll * i * i < n; ++i) {
    199 			if (n % i == 0) {
    200 				ans += check(n, i &mdash; 1, 2);
    201 				ans += check(n, 1ll * n / i &mdash; 1, 2);
    202 			}
    203 		}
    204 		if (1ll * i * i == n) ans += check(n, i &mdash; 1, 2);
    205 		for (i = 3; i <= 63; ++i) {
    206 			for (j = 2; j <= 1000000; ++j) {
    207 				sum = pow = 1;
    208 				for (k = 1; k < i; ++k) {
    209 					pow *= j;
    210 					sum += pow;
    211 					if (sum > n) break;
    212 				}
    213 				if (sum > n) break;
    214 				if (n % sum == 0) ans += check(n, j, i);
    215 			}
    216 			if (j == 2) break;
    217 		}
    218 		printf("%d\n", ans);
    219 	}
    220 	return 0;
    221 }
    222 ```
    223 
    224 [2215C - Oriented Journey](/contest/2215/problem/C)
    225 
    226 Idea by [dapingguo8](/profile/dapingguo8 "Master dapingguo8")
    227 
    228 **Solution**
    229 
    230 There are $2^{n-1}$ ways to direct the edges, which equals to the number of possible values of $s$. This implies we must find a strategy to deliver information from the very beginning, even there's little information about $T$ we can know.
    231 
    232 Note that indexes of nodes persist, so consider direct the edges in two ways. Suppose $(a,b)$ is an undirected edge in $T$ and $a \lt b$:
    233 
    234 * Assign direction $a\rightarrow b$. We'll call this edge a **black** edge.
    235 * Assign direction $b\rightarrow a$. We'll call this edge a **red** edge.
    236 
    237 Edges can be uncertain from the start, so consider utilize nodes to deliver information. Let's map the binary form of $s$ to nodes indexed $2$ to $n$, so each of these nodes has a number either $0$ or $1$ on it (and suppose node $1$ has $0$ written on it). When we acquire an undirected edge $(a,b)$ of $T$, if node $a$ and node $b$ have **different** number written on it, then direct the edge as **red**, and vice versa.
    238 
    239 And for the second run, it's easy to deduce the numbers on each node by a simple DFS to recover $s$.
    240 
    241 **Code(C++)**
    242 
    243 ```
    244 #include <bits/stdc++.h>
    245 #define all(s) s.begin(), s.end()
    246 using namespace std;
    247 using ll = long long;
    248 using ull = unsigned long long;
    249 
    250 void Alice() {
    251     int n; ll s; cin >> n >> s;
    252     s -= 1;
    253     vector<bool> special(n + 1, false);
    254     for (int i = 2; i <= n; i++) special[i] = (s >> (i - 2)) & 1;
    255     for (int i = 1; i < n; i++) {
    256         int u, v; cin >> u >> v;
    257         if (u > v) swap(u, v);
    258         if (special[u] ^ special[v]) swap(v, u);
    259         cout << u << ' ' << v << endl;
    260     }
    261 	return;
    262 }
    263 
    264 void Bob() {
    265     int n; cin >> n;
    266     vector<vector<pair<int, int>>> g(n + 1, vector<pair<int, int>>());
    267     for (int i = 1; i < n; i++) {
    268         int u, v; cin >> u >> v;
    269         int c = (u > v);
    270         g[u].push_back({v, c});
    271         g[v].push_back({u, c});
    272     }
    273     vector<bool> special(n + 1, false);
    274     auto dfs = [&](auto self, int u, int f) -> void {
    275         for (auto e : g[u]) {
    276             int v = e.first, c = e.second;
    277             if (v == f) continue;
    278             if (c) special[v] = special[u] ^ 1;
    279             else special[v] = special[u];
    280             self(self, v, u);
    281         }
    282     };
    283     dfs(dfs, 1, 0);
    284     ll s = 0;
    285     for (int i = 2; i <= n; i++) {
    286         if (special[i]) s |= (1 << (i - 2));
    287     }
    288     cout << s + 1 << endl;
    289 }
    290 
    291 int main() {
    292 	ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    293 	int t, q; cin >> t >> q;
    294 	while (t--) {
    295 		if (q == 1) Alice();
    296 		else Bob();
    297 	}
    298 }
    299 ```
    300 
    301 [2215D - EXPloration, EXPloitation, and Gain Some EXPerience!](/contest/2215/problem/D)
    302 
    303 Idea by [xiaoziyao](/profile/xiaoziyao "Master xiaoziyao")
    304 
    305 **Solution**
    306 
    307 We can identify a key strategy: if player A leads player B by a sufficiently large margin, A can make three consecutive moves of distance $1$ to occupy four consecutive positions. This effectively blocks B from reaching any position beyond A's current location.
    308 
    309 Specifically, suppose it is the leading player A's turn, with A at position $u$ and B at position $v$, where $u - v \geqslant 6$. In this case, A can force a block on B using a state sequence like the following (taking $v = u-6$ as an example): $(u-6,u) \to (u-6,u+1) \to (u-2,u+1) \to (u-2,u+2) \to (u-1,u+2) \to (u-1,u+3)$.
    310 
    311 This constitutes the optimal strategy for both sides. Player A can guarantee that the final score difference is at most the value achieved in this scenario, because once B is blocked, A is guaranteed to claim all remaining positions in the suffix. Conversely, player B can guarantee that the score difference is at least this value, since regardless of how A plays, B can secure all positions in this intermediate segment.
    312 
    313 Consequently, we can solve the problem using a backward DP. The state needs to track the position of the leading player, the distance gap $\in [0,5]$ between them, and a $2^4$ bitmask to record the occupancy status of the positions between the two players. This yields an $O(n)$ time complexity, and space complexity is easily manageable using rolling array optimization.
    314 
    315 During implementation, note that after making a move, the leading player might temporarily extend their lead to a distance of $\geqslant 6$. However, on the subsequent turn, they will either move back to reduce the gap, or the situation will naturally fall into the blocking case described above.
    316 
    317 **Code(C++)**
    318 
    319 ```
    320 #include<bits/stdc++.h>
    321 using namespace std;
    322 const int maxn=200005,maxs=(1<<4)+5;
    323 int T,n;
    324 int a[maxn];
    325 long long sum[maxn];
    326 long long f[2][5][maxn][maxs];
    327 bool g[2][5][maxn][maxs];
    328 long long dfs(int dir,int fr,int bk,int S){
    329     int hav=0;
    330     if(fr<n)
    331         hav=1;
    332     for(int i=bk+1;i<=n&&i<=bk+4;i++)
    333         if(((S>>(i-bk-1))&1)==0&&i!=fr)
    334             hav=1;
    335     if(hav==0)
    336         return 0;
    337     if(fr-bk>=6&&dir==0){
    338         long long res=sum[n]-sum[fr];
    339         for(int i=bk+1;i<=fr-1;i++)
    340             if(((S>>(i-bk-1))&1)==0)
    341                 res-=a[i];
    342         return res;
    343     }
    344     if(fr-bk<6&&g[dir][fr-bk-1][bk][S])
    345         return f[dir][fr-bk-1][bk][S];
    346     long long res=-1e18;
    347     if(dir==0){
    348         int flg=0;
    349         for(int i=fr+1;i<=n&&i<=fr+4;i++)
    350             flg=1,res=max(res,a[i]-dfs(1,i,bk,S|(1<<(fr-bk-1))));
    351         if(flg==0)
    352             res=-dfs(1,fr,bk,S);
    353     }
    354     else{
    355         int flg=0;
    356         for(int i=bk+1;i<=n&&i<=bk+4;i++)
    357             if(((S>>(i-bk-1))&1)==0&&i!=fr){
    358                 flg=1;
    359                 if(i<fr)
    360                     res=max(res,a[i]-dfs(0,fr,i,S>>(i-bk)));
    361                 if(i>fr)
    362                     res=max(res,a[i]-dfs(1,i,fr,0));
    363             }
    364         if(flg==0)
    365             res=-dfs(0,fr,bk,S);
    366     }
    367     if(fr-bk<6)
    368         f[dir][fr-bk-1][bk][S]=res,g[dir][fr-bk-1][bk][S]=1;
    369     return res;
    370 }
    371 int main(){
    372     memset(g,0,sizeof(g));
    373     scanf("%d",&T);
    374     while(T--){
    375         scanf("%d",&n);
    376         for(int i=3;i<=n;i++)
    377             scanf("%d",&a[i]),sum[i]=sum[i-1]+a[i];
    378         for(int i=n;i>=1;i--)
    379             for(int j=i-1;j>=1&&j>=i-5;j--)
    380                 for(int k=0;k<=1;k++)
    381                     for(int s=0;s<(1<<(i-j-1));s++)
    382                         dfs(k,i,j,s);
    383         printf("%lld\n",dfs(1,2,1,0));
    384         for(int i=0;i<=1;i++)
    385             for(int j=0;j<=4;j++)
    386                 for(int k=0;k<=n;k++)
    387                     for(int s=0;s<maxs;s++)
    388                         g[i][j][k][s]=0;
    389     }
    390     return 0;
    391 }
    392 ```
    393 
    394 [2215E - Star Map](/contest/2215/problem/E)
    395 
    396 Idea by [Kratrissa](/profile/Kratrissa "Grandmaster Kratrissa")
    397 
    398 **Solution**
    399 
    400 Consider the planar graph corresponding to the triangulation. Let the number of points on its outermost face be $x$, and the size of the triangulation be $t$. By Euler's formula for planar graphs, we have $V+F-E=1$. Together with $F\ge t$ and $E= \dfrac{3F+x}2$, we obtain $t\le F=2(n-1)-x$. The problem thus reduces to minimizing this $x$ and achieving equality simultaneously.
    401 
    402 We now identify which points must lie on the outermost face. Intuitively, if, when taking a point as the origin, there exists a quadrant containing no other points, then this point must be on the convex hull (outer face). We next give a construction under which all equalities hold.
    403 
    404 Sort all points by their $y$-coordinate in increasing order and add them one by one, while maintaining two monotonic stacks $q_1,q_2$ satisfying: $x_{q_{1,i}} \gt x_{q_{1,i-1}},\ y_{q_{1,i}} \gt y_{q_{1,i-1}}$; $x_{q_{2,i}} \lt x_{q_{2,i-1}},\ y_{q_{2,i}} \gt y_{q_{2,i-1}}$, and the top elements of the two stacks are identical.
    405 
    406 When inserting a point $(x_i,y_i)$, update the two stacks as follows:
    407 
    408 * If $q_1$ is nonempty, take its top element $j$. If $x_i \lt x_j$, pop $j$ from the stack; if the stack is still nonempty, let $k$ be its new top, and add $(i,j,k)$ to $T$. Repeat until $x_i \gt x_j$.
    409 * If $q_2$ is nonempty, take its top element $j$. If $x_i \gt x_j$, pop $j$ from the stack; if the stack is still nonempty, let $k$ be its new top, and add $(i,j,k)$ to $T$. Repeat until $x_i \lt x_j$.
    410 
    411 It can be easily verified that this construction achieves equality.
    412 
    413 **Code(C++)**
    414 
    415 ```
    416 #include <bits/stdc++.h>
    417 using namespace std;
    418 const int N = 2e5 + 5;
    419 int T, n, ql[N], qr[N], tpl, tpr, cnt;
    420 struct point {
    421     int x, y, id;
    422     bool operator<(const point &other) const {
    423         return y < other.y;
    424     }
    425 } p[N];
    426 struct triangle { int a, b, c; } ans[N << 1];
    427 int main() {
    428     scanf("%d", &T);
    429     while (T--) {
    430         scanf("%d", &n);
    431         for (int i = 1; i <= n; i++) 
    432             scanf("%d%d", &p[i].x, &p[i].y), p[i].id = i;
    433         sort(p + 1, p + n + 1);
    434         cnt = 0;
    435         ql[1] = qr[1] = 1;
    436         tpl = tpr = 1;
    437         for (int i = 2; i <= n; i++) {
    438             while (tpl && p[i].x < p[ql[tpl]].x) {
    439                 if (tpl >= 2) ans[++cnt] = triangle{p[i].id, p[ql[tpl]].id, p[ql[tpl - 1]].id};
    440                 tpl--;
    441             }
    442             ql[++tpl] = i;
    443             while (tpr && p[i].x > p[qr[tpr]].x) {
    444                 if (tpr >= 2) ans[++cnt] = triangle{p[i].id, p[qr[tpr]].id, p[qr[tpr - 1]].id};
    445                 tpr--;
    446             }
    447             qr[++tpr] = i;
    448         }
    449         printf("%d\n", cnt);
    450         for (int i = 1; i <= cnt; i++) 
    451             printf("%d %d %d\n", ans[i].a, ans[i].b, ans[i].c);
    452     }
    453     return 0;
    454 }
    455 ```
    456 
    457 [2215F - Research](/contest/2215/problem/F)
    458 
    459 Idea by [E.Space](/profile/E.Space "International Master E.Space")
    460 
    461 **Solution**
    462 
    463 The game cannot go on indefinitely. When $n \le k$, Alice must end the game immediately; otherwise, Bob will remove the green card on the next turn, making the score $0$. Moreover, Bob can continuously remove cards to make the deck thinner. Therefore, Bob has the ability to prevent Alice from continuing the game indefinitely.
    464 
    465 First, consider the case where $s=1$. In this situation, Alice must decide whether to take the green card or put it back. Once she puts it back, who gets the green card next only depends on its position. It can be observed that only when $n \equiv k \pmod{2k}$, regardless of how Alice puts it back, she cannot get the green card next time. In this case, it is clearly optimal to remove the green card directly; otherwise, Alice can always find a way to ensure she gets the green card next time by placing it either before or after all the other removed cards. Thus, putting it back is definitely better than removing it directly.
    466 
    467 Starting from Alice putting the green card back, both players will perform $x = \left\lfloor \frac{n+k}{2k} \right\rfloor$ operations, after which it will again become a situation where Alice can take the green card. The key question is how much the size of the pile will change.
    468 
    469 Let $f_k(n)$ be the final score when the pile size is $n$, $s=1$, and $k=k$. In each subsequent operation, both players can choose to remove a card or not. We can prove that the final score will be $1 + \max\left(\min{f_k(n-x-1), f_k(n-x)}, \min{f_k(n-x), f_k(n-x+1)}\right)$. Alternatively, it can be expressed as $1 + \min(\max{f_k(n-x-1), f_k(n-x+1)}, f_k(n-x))$.
    470 
    471 There are a total of $2x$ operations, which may remove between $0$ and $2x$ cards. We can shift the coordinate system to consider that, in the end, there will be $n-x$ cards left. When one person removes a card, it is equivalent to reducing the pile by $0.5$ cards, while not removing it increases the pile by $0.5$ cards. For Alice, she can choose to move $0.5$ steps left or right on her first move, and then let Bob choose one of the two adjacent options. Bob can always ensure he picks the smaller of the two, as long as all his subsequent moves are the opposite of Alice's. Thus, the final score will be less than or equal to this. Conversely, Alice can ensure that the score is greater than or equal to the smaller of the two options because she can make Bob make the same choice each time. Therefore, the answer must be this. However, there is a special case: when $n \equiv k+1 \pmod{2k}$, Alice must not remove the card and must place the green card at the bottom of the pile to ensure she can take it next time. Thus, in this case, Alice's first move can only be to move right, and the answer becomes $1 + \min\left( f_k(n - \left\lfloor \frac{n+k}{2k} \right\rfloor), f_k(n - \left\lfloor \frac{n+k}{2k} \right\rfloor + 1) \right)$.
    472 
    473 Next, this problem has an interesting property (which I discovered through tabulation): when $f_k(n-1) \lt f_k(n) \gt f_k(n+1)$, it must be that $n \equiv k-1 \pmod{2k}$. The proof is not difficult. Consider segmenting based on $n \equiv k \pmod{2k}$. For the case where $n-1, n, n+1$ are in the same segment (i.e., not including points where these values are $1$), let $f_k(n-1) = \max{[m_{12},] m_{23}}, f_k(n) = \max{m_{23}, m_{34}}, f_k(n+1) = \max{m_{34}, m_{45}}$. Here, $m_{ij}$ represents the minimum value of two adjacent terms of $f_k$ plus $1$. If $m_{23} \ge m_{34}$, then $f_k(n-1) \ge f_k(n)$ (regardless of whether the term $m_{12}$ exists), and if $m_{23} \lt m_{34}$, then $f_k(n+1) \ge f_k(n)$. When $n \equiv k+1$, $f_k(n-1) = 1, f_k(n) = m_{34}, f_k(n+1) = \max{m_{34}, m_{45}} \ge f_k(n)$. When $n \equiv k$, $f_k(n) = 1$ will certainly not be greater than the two sides. Therefore, when $f_k(n-1) \lt f_k(n) \gt f_k(n+1)$, it must be that $n \equiv k-1 \pmod{2k}$. At this point, $f_k(n+1) = 1$.
    474 
    475 Thus, as long as it is not one of the three cases $n \equiv k, n \equiv k+1, n-x \equiv k-1$, we have $f_k(n) = f_k(n-x) + 1$. For the third case, since $f_k(n-x-1)$ must be greater than or equal to $f_k(n-x+1) = 1$, it can be expressed as $1 + \min\left( f_k(n - \left\lfloor \frac{n+k}{2k} \right\rfloor), f_k(n - \left\lfloor \frac{n+k}{2k} \right\rfloor - 1) \right)$. Thus, we have the following recurrence relation:
    476 
    477 $f_k(n) = \begin{cases} 1, & n \equiv k \pmod{2k} \\ 1 + \min\left\{f_k\left(n - \left\lfloor \frac{n+k}{2k} \right\rfloor\right), f_k\left(n - \left\lfloor \frac{n+k}{2k} \right\rfloor + 1\right)\right\}, & n \equiv k+1 \pmod{2k} \\ 1 + \min\left\{ f_k\left(n - \left\lfloor \frac{n+k}{2k} \right\rfloor\right), f_k\left(n - \left\lfloor \frac{n+k}{2k} \right\rfloor - 1\right) \right\}, & n \equiv k-1 + \left\lfloor \frac{n+k}{2k} \right\rfloor \not\equiv k+1 \pmod{2k} \\ 1 + f_k(n - \left\lfloor \frac{n+k}{2k} \right\rfloor), & \text{otherwise} \end{cases}$
    478 
    479 Note that when $k$ is relatively large, $x$ is quite small, so for the last case, we can speed up at the same $x$. That is, consider jumping continuously $\left\lfloor \frac{(n+k) \bmod 2k}{x} \right\rfloor$ steps. Clearly, this will not pass through the first three cases. If this value is $0$, then we just make one step normally.
    480 
    481 Next, consider the case where $s \ne 1$. In other words, as the green card surfaces, both players still need to perform $x = \left\lfloor \frac{s-1}{2k} \right\rfloor$ operations. Thus, according to the previous analysis, the answer is $\min{\max{f_k(n-x-1), f_k(n-x+1)}, f_k(n-x)}$.
    482 
    483 The recurrence relation can be solved using memoization. Since when $n \equiv k$, it immediately returns $1$, and when $n \equiv k+1$, it will expand backward, encountering $n \equiv k-1$ will expand forward, so at each level, at most two states will be accessed. When $n \le (2k)^2$, we have $x \le 2k$, and because we accelerated the last line, there will only be $\min{n, (2k)^2} / 2k$ layers. When $n \gt (2k)^2$, each time $n$ will change to $\frac{2k-1}{2k}$ of its original value, resulting in $2k \max{0, \log(n/(2k)^2)}$ layers. The former reaches its maximum when $k = \sqrt{n}/2$, and the latter reaches its maximum when $k = \sqrt{n}/(2e)$, both being $O(\sqrt{n})$.
    484 
    485 **Code(C++)**
    486 
    487 ```
    488 #include<bits/stdc++.h>
    489 #define cmin(a,b) (a>(b)?a=(b),1:0)
    490 #define cmax(a,b) (a<(b)?a=(b),1:0)
    491 #define dmin(a,b) ((a)<(b)?(a):(b))
    492 #define dmax(a,b) ((a)>(b)?(a):(b))
    493 namespace io{
    494 	int F(){
    495 		int n=0,F=0;
    496 		char ch;
    497 		while((ch=getchar())!='-'&&(ch<'0'||ch>'9'));
    498 		ch=='-'?F=1:n=ch-'0';
    499 		while((ch=getchar())>='0'&&ch<='9')n=n*10+ch-'0';
    500 		return F?-n:n;
    501 	}
    502 	long long G(){
    503 		long long n=0,F=0;
    504 		char ch;
    505 		while((ch=getchar())!='-'&&(ch<'0'||ch>'9'));
    506 		ch=='-'?F=1:n=ch-'0';
    507 		while((ch=getchar())>='0'&&ch<='9')n=n*10+ch-'0';
    508 		return F?-n:n;
    509 	}
    510 }
    511 std::unordered_map<long long,long long> s;
    512 long long k;
    513 long long F(long long n){
    514 	if(n<3*k)return n-k+1;
    515 	long long& f = s[n];
    516 	if(f>0)return f;
    517 	if(n%(2*k)==k)return f=1;
    518 	long long x=(n+k)/(2*k);
    519 	if(n%(2*k)==k+1){
    520 		return f=std::min(F(n-x),F(n-x+1))+1;
    521 	}
    522 	else if((n-x)%(2*k)==k-1){
    523 		return f=std::min(F(n-x),F(n-x-1))+1;
    524 	}
    525 	else{
    526 		long long t = (n+k)-(2*k*x);
    527 		if(t>=x){
    528 			long long b=t/x;
    529 			return f=F(n-b*x)+b;
    530 		}
    531 		return f=F(n-x)+1;
    532 	}
    533 }
    534 int main(){
    535 	int T=io::F();
    536 	while(T--){
    537 		s.clear();
    538 		long long n=io::G();
    539 		k=io::G();
    540 		long long s=io::G();
    541 		
    542 		if(n<=k){
    543 			puts("1");
    544 			continue;
    545 		}
    546 		if((s-1)%(2*k)>=k){
    547 			puts("0");
    548 			continue;
    549 		}
    550 		int x=(s-1)/(2*k);
    551 		if(x==0){
    552 			printf("%lld\n",F(n));
    553 		}
    554 		else{
    555 			long long v1=F(n-x-1),v2=F(n-x),v3=F(n-x+1);
    556 			if(v2>v1&&v2>v3){
    557 				printf("%lld\n",dmax(v1,v3));
    558 			}
    559 			else{
    560 				printf("%lld\n",v2);
    561 			}
    562 		}
    563 	}
    564 	return 0;
    565 }
    566 ```
    567 
    568 [2215G - Maze](/contest/2215/problem/G)
    569 
    570 Idea By [crazy_sea](/profile/crazy_sea "Legendary Grandmaster crazy_sea")
    571 
    572 **Solution**
    573 
    574 First, we may assume without loss of generality that the cost of moving straight (up, down, left, right) is $1$, and the cost of moving diagonally is $\sqrt{2}$.
    575 
    576 Let the final answer be $a+b\sqrt{2}$; we then output $2a+3b$, and it is easy to verify that this does not affect the correctness of the result.
    577 
    578 Consider how to compute the answer under this assumption: direct calculation is nearly infeasible, but we can instead consider the answer in terms of projections. The problem guarantees that all obstacles form a single connected component and that the entire region is surrounded by obstacles on all sides.
    579 
    580 Specifically, we can consider the length of the path's projection in a certain direction. We attempt to project onto four directions (up, right, upper-right, upper-left), then perform a linear combination of these projections. After doing so, the problem reduces to finding the distance between two nodes in a tree, which can be solved with a straightforward method.
    581 
    582 The bottleneck of the algorithm lies in computing the distance between two nodes in the tree.
    583 
    584 **Code(C++)**
    585 
    586 ```
    587 #include <bits/stdc++.h>
    588 using namespace std;
    589 inline int read()
    590 {
    591 	int s=0,f=1;
    592 	char c=getchar();
    593 	while(c<'0'||c>'9')
    594 	{
    595 		if(c=='-')
    596 		f=-1;
    597 		c=getchar(); 
    598 	}
    599 	while(c>='0'&&c<='9')
    600 	{
    601 		s=s*10+c-'0';
    602 		c=getchar();
    603 	}
    604 	return s*f;
    605 }
    606 
    607 int lg[1000007];
    608 inline void Init()
    609 {
    610 	for(int i=1;i<=1000000;++i)
    611 	lg[i]=log2(i);
    612 }
    613 
    614 int n,m,q;
    615 struct Point{
    616 	int x,y;
    617 }p[300007];
    618 inline bool cmp0(Point x,Point y)
    619 {
    620 	if(x.x==y.x)
    621 	return x.y<y.y;
    622 	return x.x<y.x;	
    623 }
    624 struct Node{
    625 	int x,l,r,id;
    626 };
    627 struct Tree{
    628 	vector <int> a[1000007];
    629 	Node d[1000007];
    630 	vector <int> c[1000007];
    631 	int cnt;
    632 	int depth[1000007],fa[1000007][21];
    633 	inline void dfs0(int x,int Fa)
    634 	{
    635 		depth[x]=depth[Fa]+1;
    636 		fa[x][0]=Fa;
    637 		for(int i=1;i<=lg[depth[x]];++i)
    638 		fa[x][i]=fa[fa[x][i-1]][i-1];
    639 		for(int i=0;i<a[x].size();++i)
    640 		{
    641 			int v=a[x][i];
    642 			if(v==Fa)
    643 			continue;
    644 			dfs0(v,x);
    645 		}
    646 	}
    647 	inline int LCA(int x,int y)
    648 	{
    649 		if(depth[x]<depth[y])
    650 		swap(x,y);
    651 		while(depth[x]>depth[y])
    652 		x=fa[x][lg[depth[x]-depth[y]]];
    653 		if(x==y)
    654 		return x;
    655 		for(int i=lg[depth[x]];i>=0;--i)
    656 		{
    657 			if(fa[x][i]!=fa[y][i])
    658 			x=fa[x][i],y=fa[y][i];
    659 		}
    660 		return fa[x][0];
    661 	}
    662 	inline int query_id(int x,int y)
    663 	{
    664 		int lca=LCA(x,y);
    665 		if(lca==0)
    666 		return -1;
    667 		return depth[x]+depth[y]-2*depth[lca];
    668 	}
    669 	inline void build(int id)
    670 	{
    671 		if(id==0||id==2)
    672 		{
    673 			if(id==2)
    674 			{
    675 				for(int i=1;i<=m;++i)
    676 				{
    677 					int x=p[i].x,y=p[i].y;
    678 					p[i].x=x+y;
    679 					p[i].y=x-y;
    680 				}
    681 			}
    682 			sort(p+1,p+m+1,cmp0);
    683 			int l1=1;
    684 			for(int i=1+(id==2);i<=n*(1+(id==2));++i)
    685 			{
    686 				++cnt;
    687 				d[cnt].x=i,d[cnt].id=cnt;
    688 				if(id==0)
    689 				d[cnt].l=1;
    690 				else
    691 				d[cnt].l=-min(i-2,2*n-i);
    692 				while(l1<=m&&p[l1].x==i)
    693 				{
    694 					if(p[l1].y==d[cnt].l)
    695 					d[cnt].l=p[l1].y+1;
    696 					else
    697 					{
    698 						d[cnt].r=p[l1].y-1,c[i].push_back(cnt);
    699 						++cnt;
    700 						d[cnt].x=i,d[cnt].l=p[l1].y+1,d[cnt].id=cnt;
    701 					}
    702 					++l1;
    703 				}
    704 				if(id==0)
    705 				{
    706 					if(d[cnt].l>n)
    707 					--cnt;
    708 					else
    709 					d[cnt].r=n,c[i].push_back(cnt);
    710 				}
    711 				else
    712 				{
    713 					if(d[cnt].l>min(i-2,2*n-i))
    714 					--cnt;
    715 					else
    716 					d[cnt].r=min(i-2,2*n-i),c[i].push_back(cnt);
    717 				}
    718 			}
    719 			for(int x=1+(id==2);x<n*(1+(id==2));++x)
    720 			{
    721 				int l1=0;
    722 				for(int i=0;i<c[x].size();++i)
    723 				{
    724 					while(l1<c[x+1].size()&&d[c[x+1][l1]].r<d[c[x][i]].l-(id==0))
    725 					++l1;
    726 					bool flag=0;
    727 					while(l1<c[x+1].size()&&d[c[x+1][l1]].l<=d[c[x][i]].r+(id==0))
    728 					{
    729 						a[c[x][i]].push_back(c[x+1][l1]);
    730 						a[c[x+1][l1]].push_back(c[x][i]);
    731 						++l1;
    732 						flag=1;
    733 					}
    734 					if(flag)
    735 					--l1;
    736 				}
    737 			}
    738 			for(int i=1;i<=cnt;++i)
    739 			{
    740 				if(!depth[i])
    741 				dfs0(i,0);
    742 			}
    743 			if(id==2)
    744 			{
    745 				for(int i=1;i<=m;++i)
    746 				{
    747 					int x=p[i].x,y=p[i].y;
    748 					p[i].x=(x+y)/2;
    749 					p[i].y=(x-y)/2;
    750 				}
    751 			}
    752 		}
    753 		else if(id==1)
    754 		{
    755 			for(int i=1;i<=m;++i)
    756 			swap(p[i].x,p[i].y);
    757 			build(0);
    758 			for(int i=1;i<=m;++i)
    759 			swap(p[i].x,p[i].y);
    760 		}
    761 		else if(id==3)
    762 		{
    763 			for(int i=1;i<=m;++i)
    764 			p[i].y=n+1-p[i].y;
    765 			build(2);
    766 			for(int i=1;i<=m;++i)
    767 			p[i].y=n+1-p[i].y;
    768 		}
    769 		
    770 	}
    771 	inline int Query(int id,int sx,int sy,int tx,int ty)
    772 	{
    773 		int x=0,y=0;
    774 		if(id==0)
    775 		{
    776 			for(int i=0;i<c[sx].size();++i)
    777 			{
    778 				if(d[c[sx][i]].l<=sy&&sy<=d[c[sx][i]].r)
    779 				{
    780 					x=c[sx][i];
    781 					break;
    782 				}
    783 			}
    784 			for(int i=0;i<c[tx].size();++i)
    785 			{
    786 				if(d[c[tx][i]].l<=ty&&ty<=d[c[tx][i]].r)
    787 				{
    788 					y=c[tx][i];
    789 					break;
    790 				}
    791 			}
    792 			assert(x&&y);
    793 			return query_id(x,y);
    794 		}
    795 		else if(id==1)
    796 		{
    797 			return Query(0,sy,sx,ty,tx);
    798 		}
    799 		else if(id==2)
    800 		{
    801 			return Query(0,sx+sy,sx-sy,tx+ty,tx-ty);
    802 		}
    803 		else
    804 		{
    805 			return Query(2,sx,n+1-sy,tx,n+1-ty);
    806 		}
    807 	}
    808 }tree[4];
    809 int main()
    810 {
    811 	Init();
    812 	n=read(),m=read(),q=read();
    813 	for(int i=1;i<=m;++i)
    814 	p[i].x=read(),p[i].y=read();
    815 	for(int i=0;i<4;++i)
    816 	tree[i].build(i);
    817 	int sx,sy,tx,ty;
    818 	while(q--)
    819 	{
    820 		sx=read(),sy=read(),tx=read(),ty=read();
    821 		int ans=0;
    822 		for(int i=0;i<4;++i)
    823 		{
    824 			ans+=tree[i].Query(i,sx,sy,tx,ty)*(1+(i<2));
    825 			if(ans==-2)
    826 			{
    827 				assert(i==0);
    828 				break;
    829 			}
    830 		}
    831 		ans/=2;
    832 		printf("%d\n",ans);
    833 	}
    834 	return 0;
    835 }
    836 ```