2216.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 — 1, 2); 201 ans += check(n, 1ll * n / i — 1, 2); 202 } 203 } 204 if (1ll * i * i == n) ans += check(n, i — 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 ```