From the statement we can conclude that a class can be slept through $$$\textbf{if and only if}$$$:

1. The class itself is not an important class.
2. The class is not within $$$k$$$ classes after any important class.

Here's an $$$O(nk)$$$ approach:

We directly simulate the process: for each important class at position $$$i$$$, mark positions $$$i+1, i+2, \dots, \min(i+k, n)$$$ as “must stay awake”. After processing all important classes, count the classes that are neither important nor marked. This $$$O(nk)$$$ solution is acceptable under the constraints.

There's also an $$$O(n)$$$ solution:

For each unimportant class, we only need to focus on the nearest important class before it. Thus we maintain a variable $$$last$$$ storing the index of the most recent important class (or $$$-\infty$$$ if none seen yet), then for each $$$i$$$ from $$$1$$$ to $$$n$$$, if it's an important class we let $$$last = i$$$, otherwise if $$$last + k \lt i$$$, the class is able to be slept through and we add $$$1$$$ to the answer.

#include<bits/stdc++.h>
using namespace std;
int n,k;string s;
void solve(){
	cin>>n>>k>>s;
	int ans=0;
	for(int i=0;i<n;i++){
		if(s[i]=='0'){
			int ok=1;
			for(int j=max(0,(int)i-k);j<i;j++){
				if(s[j]=='1'){
					ok=0;
					break;
				}
			}
			ans+=ok;
		}
	}
	cout<<ans<<endl;
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	int T;cin>>T;
	for(;T--;)solve();
	return 0;
}

Consider a simple greedy algorithm: For each turn, choose the option that gives the higher immediate score. That is, if our current score is $$$k$$$, it becomes $$$\max(k - a_i, b_i - k)$$$ after this turn. Why doesn't the algorithm work?

Try to improve the algorithm in Hint 1.

The greedy approach in Hint 1 fails because it assumes that if we know the maximum possible score after turn $$$i$$$ (denoted by $$$max_i$$$), we can determine $$$max_{i + 1}$$$ from it. However, this assumption is wrong and here is a counterexample:

$$$a = [2, 0], b = [1, 0]$$$

Here $$$max_1 = 1$$$ and $$$max_2 = 2$$$. The greedy approach takes the blue card in turn $$$1$$$. But to reach $$$max_2$$$, we must choose the red card in turn $$$1$$$, which turns our score into $$$-2$$$, and then choose the blue card in turn $$$2$$$. So in this example, $$$max_1$$$ does not give $$$max_2$$$.

We see that $$$max_1$$$ does not help us find $$$max_2$$$ if we choose the blue card in the second turn. The reason is, if we want to maximize our score when choosing a blue card, we want our current score to be as small as possible, so we are looking for the minimum possible score. To maximize $$$b_i - k$$$ we should minimize $$$k$$$.

From this we can see that if we have both the maximum possible score $$$max_{i - 1}$$$ and the minimum possible score $$$min_{i - 1}$$$ after turn $$$i - 1$$$, we can determine $$$max_{i} = \max(max_{i - 1} - a_i, b_i - min_{i - 1})$$$, because these two expressions cover the best outcomes from the red and blue options respectively. Similarly, the new minimum $$$min_{i} = \min(min_{i - 1} - a_i, b_i - max_{i - 1})$$$ comes from either taking the red card from the previous minimum, or the blue card from the previous maximum. And from $$$max_{i}, min_{i}$$$ we can move forward to $$$max_{i + 1}, min_{i + 1}$$$ and so on.

Thus, we start with $$$max_0 = min_0 = 0$$$ and calculate each $$$max_i, min_i$$$ throughout the process using the formulas above. The answer is $$$max_n$$$. This runs in $$$O(n)$$$ time complexity.

#include<bits/stdc++.h>
#define ll long long

using namespace std;

const int MAXN = 1e5 + 10;

int n;
int a[MAXN], b[MAXN];

int main() {
    int t; cin >> t;
    while (t--) {
        int n; cin >> n;
        for (int i = 1; i <= n; ++i) cin >> a[i];
        for (int i = 1; i <= n; ++i) cin >> b[i];
        ll mx = 0, mn = 0;
        for (int i = 1; i <= n; ++i) {
            ll new_mx = max(mx - a[i], b[i] - mn);
            ll new_mn = min(mn - a[i], b[i] - mx);
            mx = new_mx, mn = new_mn;
        }
        cout << mx << endl;
    }
    return 0;
}

Consider the cases $$$n = 1$$$ and $$$n = 2$$$. What do you observe?

Try to determine the "first" element that must belong to $$$B$$$.

Assume the minimum element in $$$A$$$ is $$$x$$$. We now prove that $$$x$$$ must be included in $$$B$$$.

There are no elements smaller than $$$x$$$, which means $$$x$$$ has no proper divisor (other than $$$x$$$ itself) inside $$$A$$$. If we do not put $$$x$$$ into $$$B$$$, then the second rule would be violated.

Thus we can determine the first element of $$$B$$$, and then check whether all its multiples $$$\le k$$$ are contained in $$$A$$$. We mark these multiples as "finished".

Now think greedily. We never need to process elements that are already marked "finished". Each time, we just find the smallest unfinished element in $$$A$$$, check it, and add it to $$$B$$$ if possible.

A loose upper bound on the running time is $$$O\bigl(n d(n) \log n\bigr)$$$, where $$$d(n)$$$ is the divisor function. However, this bound is rarely attained in practice: many operations are skipped thanks to the "finished" marks, so the algorithm runs much faster than this worst-case estimate.

#include<bits/stdc++.h>
using namespace std;
const int mxn=2e5+5;
set<int>s;
map<int,int>u;
int n,a[mxn],k;
void solve(){
	s.clear(),u.clear();
	cin>>n>>k;
	for(int i=1;i<=n;i++)cin>>a[i],s.insert(a[i]),u[a[i]]=1;
	vector<int>ans;ans.clear();
	while(s.size()){
		int t=*s.begin();
		ans.push_back(t);
		s.erase(s.begin());
		for(int cur=t;cur<=k;cur+=t){
			if(!u[cur]){
				cout<<"-1\n";
				return;
			}
			auto t=s.find(cur);
			if(t!=s.end())s.erase(t);
		}
	}
	cout<<ans.size()<<'\n';
	for(int i:ans)cout<<i<<' ';cout<<'\n';
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	int T=1;
	cin>>T;
	for(;T--;)solve();
	return 0;
}

What is the answer when $$$k \geq 32$$$?

We can use dynamic programming to solve it.

When $$$k \geq 32$$$, we can, at each step, add the smallest $$$t$$$ such that adding $$$2^{t}$$$ to the current $$$n$$$ produces a carry. After $$$k$$$ such steps, $$$n$$$ will become a power of $$$2$$$, and the answer will be $$$\operatorname{popcount}(n) + k - 1$$$.

Now we observe that the total number of carries in the end is $$$\operatorname{popcount}(n) + k - \operatorname{popcount}(n')$$$, where $$$n'$$$ is the final value of $$$n$$$ after all operations. To maximize this quantity, we want to minimize the final $$$\operatorname{popcount}(n')$$$.

To this end, let $$$dp[i][j][c]$$$ denote the optimal value we can obtain after processing the $$$i$$$ least significant bits, having used $$$j$$$ operations in total, where $$$c \in {0,1}$$$ indicates whether there is a carry from the $$$(i-1)$$$-th bit.

For the $$$i$$$-th least significant bit, we have two options: either select this bit (i.e., use one operation on this bit) or not select it.

Let $$$n_i$$$ be the $$$i$$$-th bit of the original $$$n$$$, and let $$$t_i$$$ be the sum at this bit after adding everything in. If we select this bit, then $$$t_i = 1 + c + n_i$$$; otherwise, $$$t_i = c + n_i$$$. From $$$t_i$$$, we can determine whether this bit produces a carry to the next position (the next carry is $$$c' = \lfloor t_i / 2 \rfloor$$$) and whether the $$$i$$$-th bit of $$$n'$$$ is $$$1$$$ or $$$0$$$ (the resulting bit is $$$t_i \bmod 2$$$), which allows us to perform the DP transition.

The time complexity is $$$O((\log_2 n)^2)$$$.

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int inf=1e9+7;
const int mxb=64,mxk=32;
int dp[mxb+2][mxk+2][2];
void Min(int&x,int y){x=min(x,y);}
void solve(){
	int n,k;cin>>n>>k;
	int pc=__builtin_popcount(n);
	if(n==0){
		cout<<max(0ll,k-1)<<'\n';
		return;
	}
	if(k>=32){
		cout<<k+pc-1<<'\n';
		return;
	}
	for(int i=0;i<=mxb;i++)for(int j=0;j<=k;j++)dp[i][j][0]=dp[i][j][1]=inf;
	dp[0][0][0]=0;
	for(int i=0;i<mxb;i++){
		int ni=(n>>i)&1ll;
		for(int u=0;u<=k;u++)for(int c=0;c<=1;c++){
			int cur=dp[i][u][c];
			if(cur>=inf)continue;
			{
				int sum=ni+c,bit=sum&1,nc=sum>>1;
				Min(dp[i+1][u][nc],cur+bit);		
			}
			if(u+1<=k){
				int sum=ni+1+c,bit=sum&1,nc=sum>>1;
				Min(dp[i+1][u+1][nc],cur+bit);
			}
		}
	}
	int bst=inf;
	for(int u=0;u<=k;u++)for(int c=0;c<=1;c++){
		int val=dp[mxb][u][c];
		if(val<inf)Min(bst,val+c);
	}
	int ans=k+pc-bst;
	cout<<ans<<'\n';
}
signed main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	int T;cin>>T;
	for(;T--;)solve();
	return 0;
}

$$$\lfloor 2.5n\rfloor$$$ is the expected number of operations. We add $$$800$$$ more to ensure that every correct solution would pass.

Think about how to solve it within $$$3n$$$, and how can we improve that.

We split the process into two phases. In the first phase, we make every pair $$$x$$$ and $$$n - x + 1$$$ symmetric; in the second phase, we turn the permutation into $$$1, 2, \dots, n$$$.

Let $$$pos[x]$$$ be the current position of $$$x$$$. We iterate $$$x$$$ from $$$1$$$ to $$$n$$$ in increasing order. If $$$pos[x] + pos[n + 1 - x] \neq n + 1$$$, then $$$x$$$ and $$$n + 1 - x$$$ are not symmetric. In this case, we query $$$(pos[x],\, n - pos[n + 1 - x] + 1)$$$. No matter whether the interactive judge mirrors the array and then swaps or not, this operation will always make $$$x$$$ and $$$n + 1 - x$$$ symmetric. When $$$n$$$ is odd, we should first move $$$(n+1)/2$$$ to the middle.

Next, we move these groups to their correct target positions in order. Suppose the target positions of a pair are $$$i$$$ and $$$n - i + 1$$$, while it is currently at $$$j$$$ and $$$n - j + 1$$$. We query $$$(i, j)$$$; this will surely place either the pair itself or its mirror into the correct positions.

Now we compute the expectation. Let $$$T$$$ be the expected number of queries spent in this second phase for a single group. After we query once, with probability $$$1/2$$$ the group is already correctly placed and we are done after $$$1$$$ query; with probability $$$1/2$$$ it is mirrored into another group’s target positions, in which case we have spent $$$1$$$ query and still expect $$$T$$$ more. Thus $$$T = 1 + \frac{1}{2} \cdot 1 + \frac{1}{2}(T + 1)$$$, which solves to $$$T = 4$$$.

There are $$$n/2$$$ groups, so this phase needs $$$2n$$$ queries in expectation. The first phase uses exactly $$$n/2$$$ queries (one per group), so the total expected number of queries is $$$5n/2$$$.

#include<bits/stdc++.h>
using namespace std;
const int mxn=40004;
int n,a[mxn],pos[mxn];
int mirror(int x){
	return n-x+1;
}
pair<int,int>ask(int x,int y){
	cout<<"? "<<x<<' '<<y<<endl;
	fflush(stdout);
	int u,v;cin>>u>>v;
	return {u,v};
}
void solve(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		pos[a[i]]=i;
	}
	if(n%2==1){
		int mid=(n+1)/2;
		while(pos[mid]!=mid){
			auto p=ask(mid,pos[mid]);
			int u=p.first,v=p.second;
			swap(a[u],a[v]);
			pos[a[u]]=u,pos[a[v]]=v;
		}
	}
	for(int i=1;i<=n/2;i++){
		int x=pos[i],y=pos[mirror(i)];
		if(x+y!=n+1){//not mirror
			auto p=ask(x,mirror(y));
			int u=p.first,v=p.second;
			swap(a[u],a[v]);
			pos[a[u]]=u,pos[a[v]]=v;
		}
	}
	for(int i=1;i<=n/2;i++){
		while(pos[i]!=i or pos[mirror(i)]!=mirror(i)){
			if(pos[i]!=i){
				auto p=ask(i,pos[i]);
				int u=p.first,v=p.second;
				swap(a[u],a[v]);
				pos[a[u]]=u,pos[a[v]]=v;				
			}else{
				auto p=ask(mirror(i),pos[mirror(i)]);
				int u=p.first,v=p.second;
				swap(a[u],a[v]);
				pos[a[u]]=u,pos[a[v]]=v;	
			}
		}
	}
	cout<<"!"<<endl;
	fflush(stdout);
}
int main(){
	int T=1;
	cin>>T;
	for(;T--;)solve();
	return 0;
}

Consider the process. First note that, because the array $$$a$$$ is non-increasing, the length of each segment whose sum first reaches $$$\ge x$$$ and is then cleared is nondecreasing.

We use the square-root decomposition idea. We fix a threshold $$$B$$$ that separates “short” segments from “long” ones. For segments of length at most $$$B$$$, we handle them using precomputed data; for segments of length greater than $$$B$$$, we use a slower direct procedure.

Since there are at most $$$q$$$ distinct values of $$$x$$$, we can first collect all queries offline and discretize these values. Then we build a table $$$\text{f[i][len]}$$$ that records the rightmost starting position of a segment of length $$$\text{len}$$$ whose sum is at least the $$$i$$$-th largest value of $$$x$$$.

When answering a query, we simply enumerate $$$\text{len} = 1, 2, \dots, B$$$ and, starting from the current left endpoint, quickly skip over and process all segments of length $$$\text{len}$$$. The time complexity for this part is $$$O(B)$$$ per query.

For segments of length $$$ \gt B$$$, we directly binary search the ending position of each such segment. Since every such segment has length at least $$$B$$$, we make at most $$$n/B$$$ jumps, so this part runs in $$$O\bigl((n/B)\log n\bigr)$$$ time.

If we choose $$$B = \sqrt{n\log n}$$$, the two parts balance and the total time complexity becomes $$$O\bigl(n\sqrt{n\log n}\bigr)$$$.

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int mxn=2e5+5;
const int B=512;
int T,f[B+3][mxn],n,a[mxn],q;
ll sum[mxn],N=1000000001;
int l_[mxn],r_[mxn],x_[mxn];
int id[mxn];
void solve(){
	cin>>n>>q;
	vector<int>v;v.clear();
	for(int i=1;i<=n;i++)
		cin>>a[i],
		sum[i]=sum[i-1]+a[i];
	for(int i=1;i<=q;i++)
		cin>>l_[i]>>r_[i]>>x_[i],
		v.push_back(x_[i]);
	v.push_back(0);
	v.push_back(1000000008);
	sort(v.begin(),v.end());
	v.erase(unique(v.begin(),v.end()),v.end());
	for(int i=1;i<=q;i++)
		id[i]=lower_bound(v.begin(),v.end(),x_[i])-v.begin();
	for(int i=1;i<=B;i++){
		int k=0;
		for(int j=n-i;j>=0;j--)
			for(;v[k]<=min(sum[j+i]-sum[j],N);k++)
				f[i][k]=j+1;
	}
	for(int t=1;t<=q;t++){
		int l,r,x,cnt=0;
		l=l_[t],r=r_[t],x=x_[t];
		for(int i=1;i<=B;i++)
			if(f[i][id[t]]>=l){
				int w=min(r-l+1,f[i][id[t]]-l+i)/i;
				cnt+=w;
				l+=w*i;
			}l--;
		while(1){
			if(sum[r]-sum[l]<x){
				cout<<cnt<<' '<<sum[r]-sum[l]<<'\n';
				break;
			}cnt++;
			int t=x,lo=l-1,hi=n+1,md;
			ll req=sum[l]+t;
			for(;lo<hi-1;){
				md=lo+hi>>1;
				if(sum[md]<req)lo=md;
				else hi=md;
			}
			l=hi;
		}
	}
	for(int i=0;i<max(n,(int)v.size())+3;i++)sum[i]=0;
	for(int j=0;j<B+3;j++)for(int i=0;i<max(n,(int)v.size())+3;i++)f[j][i]=0;
}
signed main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	T=1;cin>>T;
	while(T--)solve();
	return 0;
}

There exists an $$$O(n\sqrt{n})$$$ solution.

We can notice that when $$$n$$$ is even, it can only generate an even number: the sum of the first half is exactly the same as the second half. However, when $$$n$$$ is odd, we can generate any number by placing $$$n-k+1$$$ in the middle and $$$1$$$ in other positions.

We can prove that the final cost of the number must be 1, and it is between 1 and 9 (possibly with leading zeros). We don't need to remove the leading zeros.

So, which position should we reserve? Greedily, we should reserve as many leading zeros as possible. Therefore, we can reserve the last non-zero position and the zeros before it.

When $$$y \gt 1$$$ and $$$x \neq 1$$$, the number can be divided by $$$x$$$.

Consider dividing the current grid into 4 areas. In which area does our position lie?

Try to solve this problem using recursion.

Stop learning useless algorithms, go solve some problems, and learn how to use binary search.

How do we check whether the mex of a subarray is greater than $$$x$$$? When all the numbers from $$$0$$$ to $$$x-1$$$ have appeared in it.

Greedily split the array.

When should we output -1?

When the array is full (though this may not be entirely correct), we can replace one position with a blank, then fill it with the correct word.

Initially, when the array is completely blank, we choose a neural network. We will need to perform $$$n$$$ operations to fill all the correct words into the array in the worst case.

Consider hint 1. Which neural network should we choose first?

This is a classic problem.If you don't know how to solve it, you should learn about Trie.