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.

The number of steps is at most $$$nk \le 1000$$$.

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cstdlib>
using namespace std;
#define ll long long
#define rep(i, x, y) for(int i = x; i <= y; ++i)
#define per(i, x, y) for(int i = x; i >= y; --i)
inline int read(){
    int x = 0, f = 1; char ch = getchar();
    while(ch < '0' || ch > '9'){ if(ch == '-') f = -1; ch = getchar(); }
    while(ch >= '0' && ch <= '9'){ x = x * 10 + (ch ^ 48); ch = getchar(); }
    return x * f;
}
const int N = 55, M = 25, K = 1010;
int n, k, a[M], b[N], c[N];
int p[M][N], q[M][N], lenp[M], lenq[M];
int cnt, x[K], y[K];
inline void mian(){
    memset(a, 0, sizeof(a)); memset(b, 0, sizeof(b));
    memset(lenp, 0, sizeof(lenp));
    n = read(); k = read();
    rep(i, 1, k) a[i] = read();
    rep(i, 1, n) b[i] = read(), p[b[i]][++lenp[b[i]]] = i;
    cnt = 0;
    per(i, k, 1){
        int len = lenp[i];
        rep(j, 1, len){
            rep(l, i, k){
                x[++cnt] = p[i][j];
            }
        }
    }
    printf("%d\n", cnt);
    rep(i, 1, cnt) printf("%d ", x[i]);
    puts("");
    return;
}
int main(){ int qwq = read(); while(qwq--) mian(); return 0; }

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}$$$.

#include<bits/stdc++.h>
#define cmin(a,b) (a>(b)?a=(b),1:0)
#define cmax(a,b) (a<(b)?a=(b),1:0)
#define dmin(a,b) ((a)<(b)?(a):(b))
#define dmax(a,b) ((a)>(b)?(a):(b))
namespace io{
	int F(){
		int n=0,F=0;
		char ch;
		while((ch=getchar())!='-'&&(ch<'0'||ch>'9'));
		ch=='-'?F=1:n=ch-'0';
		while((ch=getchar())>='0'&&ch<='9')n=n*10+ch-'0';
		return F?-n:n;
	}
	long long G(){
		long long n=0,F=0;
		char ch;
		while((ch=getchar())!='-'&&(ch<'0'||ch>'9'));
		ch=='-'?F=1:n=ch-'0';
		while((ch=getchar())>='0'&&ch<='9')n=n*10+ch-'0';
		return F?-n:n;
	}
}
int main(){
	int T=io::F();
	while(T--){
        long long t=io::F(),h=io::F(),u=io::F();
        if(t>h*2+u){
            printf("%lld\n",t*2+h*3+u*2+1);
        }
        else{
            printf("%lld\n",t*2+h*3+u*3-dmin(t,u));
        }
	}
	return 0;
}

Each $$$a_i$$$ can only end up as either $$$b_i = a_i \bmod p$$$ or $$$c_i = (a_i \bmod q) \bmod p$$$.

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)$$$.

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:

Using prefix sums for preprocessing, the time complexity is $$$\mathcal{O}(n)$$$.

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll t,n,k,p,q,a[100009],f[100009][2],g[100009];
inline ll read(){
	ll s = 0,w = 1;
	char ch = getchar();
	while (ch > '9' || ch < '0'){ if (ch == '-') w = -1; ch = getchar();}
	while (ch <= '9' && ch >= '0') s = (s << 1) + (s << 3) + (ch ^ 48),ch = getchar();
	return s * w;
}
int main(){
	t = read();
	while (t --){
		ll ans = 1e18;
		n = read(),k = read(),p = read(),q = read();
		for (ll i = 1;i <= n;i += 1) a[i] = read();
		for (ll i = 1;i <= n;i += 1) f[i][0] = a[i] % p % q,f[i][1] = a[i] % q % p;
		for (ll i = 1;i <= n;i += 1) g[i] = g[i - 1] + min(f[i][0],f[i][1]);
		for (ll i = 1;i <= n;i += 1) f[i][0] += f[i - 1][0],f[i][1] += f[i - 1][1];
		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]);
		printf("%lld\n",ans);
	}
	return 0;
}

Divide the situations based on $$$k$$$:

• $$$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$$$.

• $$$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$$$.

Time complexity is $$$O\left(\sqrt{n}\right)$$$

#include <cstdio>
using namespace std;
int check(long long n, long long b, int p) {
	while (n) {
		long long r = n % b;
		n /= b;
		for (int i = 1; i < p; ++i) {
			if (n % b != r) return 0;
			n /= b;
		}
	}
	return 1;
}
int main(){
	long long n, sum, pow;
	int T, i, j, k, ans;
	scanf("%d", &T);
	while (T--) {
		scanf("%lld", &n);
		if (n <= 2) {
			puts("0");
			continue;
		}
		ans = 1;
		if ((n & 1) == 0 && n >= 8) ans = 2;
		for (i = 3; 1ll * i * i < n; ++i) {
			if (n % i == 0) {
				ans += check(n, i &mdash; 1, 2);
				ans += check(n, 1ll * n / i &mdash; 1, 2);
			}
		}
		if (1ll * i * i == n) ans += check(n, i &mdash; 1, 2);
		for (i = 3; i <= 63; ++i) {
			for (j = 2; j <= 1000000; ++j) {
				sum = pow = 1;
				for (k = 1; k < i; ++k) {
					pow *= j;
					sum += pow;
					if (sum > n) break;
				}
				if (sum > n) break;
				if (n % sum == 0) ans += check(n, j, i);
			}
			if (j == 2) break;
		}
		printf("%d\n", ans);
	}
	return 0;
}

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.

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$$$:

• Assign direction $$$a\rightarrow b$$$. We'll call this edge a black edge.
• Assign direction $$$b\rightarrow a$$$. We'll call this edge a red edge.

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.

And for the second run, it's easy to deduce the numbers on each node by a simple DFS to recover $$$s$$$.

#include <bits/stdc++.h>
#define all(s) s.begin(), s.end()
using namespace std;
using ll = long long;
using ull = unsigned long long;

void Alice() {
    int n; ll s; cin >> n >> s;
    s -= 1;
    vector<bool> special(n + 1, false);
    for (int i = 2; i <= n; i++) special[i] = (s >> (i - 2)) & 1;
    for (int i = 1; i < n; i++) {
        int u, v; cin >> u >> v;
        if (u > v) swap(u, v);
        if (special[u] ^ special[v]) swap(v, u);
        cout << u << ' ' << v << endl;
    }
	return;
}

void Bob() {
    int n; cin >> n;
    vector<vector<pair<int, int>>> g(n + 1, vector<pair<int, int>>());
    for (int i = 1; i < n; i++) {
        int u, v; cin >> u >> v;
        int c = (u > v);
        g[u].push_back({v, c});
        g[v].push_back({u, c});
    }
    vector<bool> special(n + 1, false);
    auto dfs = [&](auto self, int u, int f) -> void {
        for (auto e : g[u]) {
            int v = e.first, c = e.second;
            if (v == f) continue;
            if (c) special[v] = special[u] ^ 1;
            else special[v] = special[u];
            self(self, v, u);
        }
    };
    dfs(dfs, 1, 0);
    ll s = 0;
    for (int i = 2; i <= n; i++) {
        if (special[i]) s |= (1 << (i - 2));
    }
    cout << s + 1 << endl;
}

int main() {
	ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	int t, q; cin >> t >> q;
	while (t--) {
		if (q == 1) Alice();
		else Bob();
	}
}

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.

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)$$$.

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.

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.

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.

#include<bits/stdc++.h>
using namespace std;
const int maxn=200005,maxs=(1<<4)+5;
int T,n;
int a[maxn];
long long sum[maxn];
long long f[2][5][maxn][maxs];
bool g[2][5][maxn][maxs];
long long dfs(int dir,int fr,int bk,int S){
    int hav=0;
    if(fr<n)
        hav=1;
    for(int i=bk+1;i<=n&&i<=bk+4;i++)
        if(((S>>(i-bk-1))&1)==0&&i!=fr)
            hav=1;
    if(hav==0)
        return 0;
    if(fr-bk>=6&&dir==0){
        long long res=sum[n]-sum[fr];
        for(int i=bk+1;i<=fr-1;i++)
            if(((S>>(i-bk-1))&1)==0)
                res-=a[i];
        return res;
    }
    if(fr-bk<6&&g[dir][fr-bk-1][bk][S])
        return f[dir][fr-bk-1][bk][S];
    long long res=-1e18;
    if(dir==0){
        int flg=0;
        for(int i=fr+1;i<=n&&i<=fr+4;i++)
            flg=1,res=max(res,a[i]-dfs(1,i,bk,S|(1<<(fr-bk-1))));
        if(flg==0)
            res=-dfs(1,fr,bk,S);
    }
    else{
        int flg=0;
        for(int i=bk+1;i<=n&&i<=bk+4;i++)
            if(((S>>(i-bk-1))&1)==0&&i!=fr){
                flg=1;
                if(i<fr)
                    res=max(res,a[i]-dfs(0,fr,i,S>>(i-bk)));
                if(i>fr)
                    res=max(res,a[i]-dfs(1,i,fr,0));
            }
        if(flg==0)
            res=-dfs(0,fr,bk,S);
    }
    if(fr-bk<6)
        f[dir][fr-bk-1][bk][S]=res,g[dir][fr-bk-1][bk][S]=1;
    return res;
}
int main(){
    memset(g,0,sizeof(g));
    scanf("%d",&T);
    while(T--){
        scanf("%d",&n);
        for(int i=3;i<=n;i++)
            scanf("%d",&a[i]),sum[i]=sum[i-1]+a[i];
        for(int i=n;i>=1;i--)
            for(int j=i-1;j>=1&&j>=i-5;j--)
                for(int k=0;k<=1;k++)
                    for(int s=0;s<(1<<(i-j-1));s++)
                        dfs(k,i,j,s);
        printf("%lld\n",dfs(1,2,1,0));
        for(int i=0;i<=1;i++)
            for(int j=0;j<=4;j++)
                for(int k=0;k<=n;k++)
                    for(int s=0;s<maxs;s++)
                        g[i][j][k][s]=0;
    }
    return 0;
}

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.

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.

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.

When inserting a point $$$(x_i,y_i)$$$, update the two stacks as follows:

• 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$$$.

• 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$$$.

It can be easily verified that this construction achieves equality.

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
int T, n, ql[N], qr[N], tpl, tpr, cnt;
struct point {
    int x, y, id;
    bool operator<(const point &other) const {
        return y < other.y;
    }
} p[N];
struct triangle { int a, b, c; } ans[N << 1];
int main() {
    scanf("%d", &T);
    while (T--) {
        scanf("%d", &n);
        for (int i = 1; i <= n; i++) 
            scanf("%d%d", &p[i].x, &p[i].y), p[i].id = i;
        sort(p + 1, p + n + 1);
        cnt = 0;
        ql[1] = qr[1] = 1;
        tpl = tpr = 1;
        for (int i = 2; i <= n; i++) {
            while (tpl && p[i].x < p[ql[tpl]].x) {
                if (tpl >= 2) ans[++cnt] = triangle{p[i].id, p[ql[tpl]].id, p[ql[tpl - 1]].id};
                tpl--;
            }
            ql[++tpl] = i;
            while (tpr && p[i].x > p[qr[tpr]].x) {
                if (tpr >= 2) ans[++cnt] = triangle{p[i].id, p[qr[tpr]].id, p[qr[tpr - 1]].id};
                tpr--;
            }
            qr[++tpr] = i;
        }
        printf("%d\n", cnt);
        for (int i = 1; i <= cnt; i++) 
            printf("%d %d %d\n", ans[i].a, ans[i].b, ans[i].c);
    }
    return 0;
}

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.

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.

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.

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))$$$.

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)$$$.

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$$$.

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:

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.

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)}$$$.

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})$$$.

#include<bits/stdc++.h>
#define cmin(a,b) (a>(b)?a=(b),1:0)
#define cmax(a,b) (a<(b)?a=(b),1:0)
#define dmin(a,b) ((a)<(b)?(a):(b))
#define dmax(a,b) ((a)>(b)?(a):(b))
namespace io{
	int F(){
		int n=0,F=0;
		char ch;
		while((ch=getchar())!='-'&&(ch<'0'||ch>'9'));
		ch=='-'?F=1:n=ch-'0';
		while((ch=getchar())>='0'&&ch<='9')n=n*10+ch-'0';
		return F?-n:n;
	}
	long long G(){
		long long n=0,F=0;
		char ch;
		while((ch=getchar())!='-'&&(ch<'0'||ch>'9'));
		ch=='-'?F=1:n=ch-'0';
		while((ch=getchar())>='0'&&ch<='9')n=n*10+ch-'0';
		return F?-n:n;
	}
}
std::unordered_map<long long,long long> s;
long long k;
long long F(long long n){
	if(n<3*k)return n-k+1;
	long long& f = s[n];
	if(f>0)return f;
	if(n%(2*k)==k)return f=1;
	long long x=(n+k)/(2*k);
	if(n%(2*k)==k+1){
		return f=std::min(F(n-x),F(n-x+1))+1;
	}
	else if((n-x)%(2*k)==k-1){
		return f=std::min(F(n-x),F(n-x-1))+1;
	}
	else{
		long long t = (n+k)-(2*k*x);
		if(t>=x){
			long long b=t/x;
			return f=F(n-b*x)+b;
		}
		return f=F(n-x)+1;
	}
}
int main(){
	int T=io::F();
	while(T--){
		s.clear();
		long long n=io::G();
		k=io::G();
		long long s=io::G();
		
		if(n<=k){
			puts("1");
			continue;
		}
		if((s-1)%(2*k)>=k){
			puts("0");
			continue;
		}
		int x=(s-1)/(2*k);
		if(x==0){
			printf("%lld\n",F(n));
		}
		else{
			long long v1=F(n-x-1),v2=F(n-x),v3=F(n-x+1);
			if(v2>v1&&v2>v3){
				printf("%lld\n",dmax(v1,v3));
			}
			else{
				printf("%lld\n",v2);
			}
		}
	}
	return 0;
}

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}$$$.

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.

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.

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.

The bottleneck of the algorithm lies in computing the distance between two nodes in the tree.

#include <bits/stdc++.h>
using namespace std;
inline int read()
{
	int s=0,f=1;
	char c=getchar();
	while(c<'0'||c>'9')
	{
		if(c=='-')
		f=-1;
		c=getchar(); 
	}
	while(c>='0'&&c<='9')
	{
		s=s*10+c-'0';
		c=getchar();
	}
	return s*f;
}

int lg[1000007];
inline void Init()
{
	for(int i=1;i<=1000000;++i)
	lg[i]=log2(i);
}

int n,m,q;
struct Point{
	int x,y;
}p[300007];
inline bool cmp0(Point x,Point y)
{
	if(x.x==y.x)
	return x.y<y.y;
	return x.x<y.x;	
}
struct Node{
	int x,l,r,id;
};
struct Tree{
	vector <int> a[1000007];
	Node d[1000007];
	vector <int> c[1000007];
	int cnt;
	int depth[1000007],fa[1000007][21];
	inline void dfs0(int x,int Fa)
	{
		depth[x]=depth[Fa]+1;
		fa[x][0]=Fa;
		for(int i=1;i<=lg[depth[x]];++i)
		fa[x][i]=fa[fa[x][i-1]][i-1];
		for(int i=0;i<a[x].size();++i)
		{
			int v=a[x][i];
			if(v==Fa)
			continue;
			dfs0(v,x);
		}
	}
	inline int LCA(int x,int y)
	{
		if(depth[x]<depth[y])
		swap(x,y);
		while(depth[x]>depth[y])
		x=fa[x][lg[depth[x]-depth[y]]];
		if(x==y)
		return x;
		for(int i=lg[depth[x]];i>=0;--i)
		{
			if(fa[x][i]!=fa[y][i])
			x=fa[x][i],y=fa[y][i];
		}
		return fa[x][0];
	}
	inline int query_id(int x,int y)
	{
		int lca=LCA(x,y);
		if(lca==0)
		return -1;
		return depth[x]+depth[y]-2*depth[lca];
	}
	inline void build(int id)
	{
		if(id==0||id==2)
		{
			if(id==2)
			{
				for(int i=1;i<=m;++i)
				{
					int x=p[i].x,y=p[i].y;
					p[i].x=x+y;
					p[i].y=x-y;
				}
			}
			sort(p+1,p+m+1,cmp0);
			int l1=1;
			for(int i=1+(id==2);i<=n*(1+(id==2));++i)
			{
				++cnt;
				d[cnt].x=i,d[cnt].id=cnt;
				if(id==0)
				d[cnt].l=1;
				else
				d[cnt].l=-min(i-2,2*n-i);
				while(l1<=m&&p[l1].x==i)
				{
					if(p[l1].y==d[cnt].l)
					d[cnt].l=p[l1].y+1;
					else
					{
						d[cnt].r=p[l1].y-1,c[i].push_back(cnt);
						++cnt;
						d[cnt].x=i,d[cnt].l=p[l1].y+1,d[cnt].id=cnt;
					}
					++l1;
				}
				if(id==0)
				{
					if(d[cnt].l>n)
					--cnt;
					else
					d[cnt].r=n,c[i].push_back(cnt);
				}
				else
				{
					if(d[cnt].l>min(i-2,2*n-i))
					--cnt;
					else
					d[cnt].r=min(i-2,2*n-i),c[i].push_back(cnt);
				}
			}
			for(int x=1+(id==2);x<n*(1+(id==2));++x)
			{
				int l1=0;
				for(int i=0;i<c[x].size();++i)
				{
					while(l1<c[x+1].size()&&d[c[x+1][l1]].r<d[c[x][i]].l-(id==0))
					++l1;
					bool flag=0;
					while(l1<c[x+1].size()&&d[c[x+1][l1]].l<=d[c[x][i]].r+(id==0))
					{
						a[c[x][i]].push_back(c[x+1][l1]);
						a[c[x+1][l1]].push_back(c[x][i]);
						++l1;
						flag=1;
					}
					if(flag)
					--l1;
				}
			}
			for(int i=1;i<=cnt;++i)
			{
				if(!depth[i])
				dfs0(i,0);
			}
			if(id==2)
			{
				for(int i=1;i<=m;++i)
				{
					int x=p[i].x,y=p[i].y;
					p[i].x=(x+y)/2;
					p[i].y=(x-y)/2;
				}
			}
		}
		else if(id==1)
		{
			for(int i=1;i<=m;++i)
			swap(p[i].x,p[i].y);
			build(0);
			for(int i=1;i<=m;++i)
			swap(p[i].x,p[i].y);
		}
		else if(id==3)
		{
			for(int i=1;i<=m;++i)
			p[i].y=n+1-p[i].y;
			build(2);
			for(int i=1;i<=m;++i)
			p[i].y=n+1-p[i].y;
		}
		
	}
	inline int Query(int id,int sx,int sy,int tx,int ty)
	{
		int x=0,y=0;
		if(id==0)
		{
			for(int i=0;i<c[sx].size();++i)
			{
				if(d[c[sx][i]].l<=sy&&sy<=d[c[sx][i]].r)
				{
					x=c[sx][i];
					break;
				}
			}
			for(int i=0;i<c[tx].size();++i)
			{
				if(d[c[tx][i]].l<=ty&&ty<=d[c[tx][i]].r)
				{
					y=c[tx][i];
					break;
				}
			}
			assert(x&&y);
			return query_id(x,y);
		}
		else if(id==1)
		{
			return Query(0,sy,sx,ty,tx);
		}
		else if(id==2)
		{
			return Query(0,sx+sy,sx-sy,tx+ty,tx-ty);
		}
		else
		{
			return Query(2,sx,n+1-sy,tx,n+1-ty);
		}
	}
}tree[4];
int main()
{
	Init();
	n=read(),m=read(),q=read();
	for(int i=1;i<=m;++i)
	p[i].x=read(),p[i].y=read();
	for(int i=0;i<4;++i)
	tree[i].build(i);
	int sx,sy,tx,ty;
	while(q--)
	{
		sx=read(),sy=read(),tx=read(),ty=read();
		int ans=0;
		for(int i=0;i<4;++i)
		{
			ans+=tree[i].Query(i,sx,sy,tx,ty)*(1+(i<2));
			if(ans==-2)
			{
				assert(i==0);
				break;
			}
		}
		ans/=2;
		printf("%d\n",ans);
	}
	return 0;
}