• Excellent contest
• Good contest
• Average contest
• Bad contest
• Horrible contest

• Trivial contest
• Easy contest
• Average contest
• Hard contest
• Impossible contest

If $$$n$$$ is odd, there are clearly zero possible configurations.

Suppose $$$n$$$ is even. Then consider the number of legs that belong to cows. This can be any multiple of $$$4$$$ that is less than or equal to $$$n$$$. The remaining legs will belong to chickens. Thus, the answer is equal to the number of nonnegative multiples of $$$4$$$ which are less than or equal to $$$n$$$, which is given by $$$\lfloor \frac{n}{4} \rfloor + 1$$$.

#include <bits/stdc++.h>
using namespace std;
 
void solve(){
    int n;
    cin >> n;
    cout << (n & 1 ? 0 : n/4+1) << '\n';
}
 
int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    cin >> t;
    while(t--) solve();
}

• Excellent problem
• Good problem
• Average problem
• Bad problem
• Horrible problem

• Trivial problem
• Easy problem
• Average problem
• Hard problem
• Impossible problem

The given expression is equal to $$$|(a_2 - a_1) + (a_3 - a_2) + \dots + (a_n - a_{n-1})|$$$.

This simplifies to $$$|a_n - a_1|$$$.

We want to minimize the absolute difference between the first and last elements. To do so, if one of them is set and the other one isn't, we will set them to be equal. Now, the remaining blank elements do not affect the given expression, so we can set them all to be zero.

#include <bits/stdc++.h>
using namespace std;
 
void solve(){
    int n;
    cin >> n;
    vector<int> a(n);
    for(int i=0; i<n; i++)
        cin >> a[i];
    if(a[0] == -1)
        a[0] = a[n-1];
    if(a[n-1] == -1)
        a[n-1] = a[0];
    for(int i=0; i<n; i++)
        if(a[i] == -1)
            a[i] = 0;
    cout << abs(a[n-1] - a[0]) << '\n';
    for(int i=0; i<n; i++)
        cout << a[i] << " \n"[i == n-1];
}
 
int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    cin >> t;
    while(t--) solve();
}

• Excellent problem
• Good problem
• Average problem
• Bad problem
• Horrible problem

• Trivial problem
• Easy problem
• Average problem
• Hard problem
• Impossible problem

The $$$\mathrm{XOR}$$$ of all $$$2n$$$ elements is invariant. Note that this is also equal to the $$$\mathrm{XOR}$$$ between Ajisai and Mai's final scores. Therefore, if this value is zero, the game ends in a tie. Otherwise, Ajisai and Mai's final scores will differ, so the game does not end in a tie.

Suppose the $$$\mathrm{XOR}$$$ of all $$$2n$$$ elements is nonzero. If $$$a_i = b_i$$$, then the $$$i$$$-th turn is useless. Now, consider the largest $$$i$$$ such that $$$a_i \neq b_i$$$. This person can control whose score is $$$0$$$ and whose score is $$$1$$$. Since all future turns are useless, they win. Therefore, if the largest $$$i$$$ satisfying $$$a_i \neq b_i$$$ is odd, Ajisai wins. Otherwise, Mai wins.

#include <bits/stdc++.h>
using namespace std;
 
void solve(){
    int n, x = 0, idx;
    cin >> n;
    vector<int> a(n), b(n);
    for(int i=0; i<n; i++){
        cin >> a[i];
        x ^= a[i];
    }
    for(int i=0; i<n; i++){
        cin >> b[i];
        x ^= b[i];
    }
    if(!x){
        cout << "Tie" << '\n';
        return;
    }
    for(int i=0; i<n; i++)
        if(a[i] ^ b[i])
            idx = i;
    cout << (idx & 1 ? "Mai" : "Ajisai") << '\n';
}
 
int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    cin >> t;
    while(t--) solve();
}

The $$$\mathrm{XOR}$$$ of all $$$2n$$$ elements is equal to the $$$\mathrm{XOR}$$$ between Ajisai and Mai's final scores. Therefore, we know exactly what bits their scores will differ in.

The most significant of these bits dictates who wins the game. Therefore, we can apply the solution from the easy version to the most significant bit of the $$$\mathrm{XOR}$$$ of all $$$2n$$$ elements.

#include <bits/stdc++.h>
using namespace std;
 
void solve(){
    int n, x = 0, bit, idx;
    cin >> n;
    vector<int> a(n), b(n);
    for(int i=0; i<n; i++){
        cin >> a[i];
        x ^= a[i];
    }
    for(int i=0; i<n; i++){
        cin >> b[i];
        x ^= b[i];
    }
    if(!x){
        cout << "Tie" << '\n';
        return;
    }
    for(int i=0; i<20; i++)
        if(x&1<<i)
            bit = i;
    for(int i=0; i<n; i++)
        if((a[i]^b[i])&1<<bit)
            idx = i;
    cout << (idx & 1 ? "Mai" : "Ajisai") << '\n';
}
 
int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    cin >> t;
    while(t--) solve();
}

• Excellent problem
• Good problem
• Average problem
• Bad problem
• Horrible problem

• Trivial problem
• Easy problem
• Average problem
• Hard problem
• Impossible problem

Let $$$\mathrm{pre}_i$$$ denote the minimum of $$$p_1, \dots, p_i$$$, and let $$$\mathrm{suf}_i$$$ denote the maximum of $$$p_i, \dots, p_n$$$. Then if there exists some $$$i$$$ such that $$$\mathrm{pre}_{i-1} \gt \mathrm{suf}_i$$$, then the answer is $$$\texttt{No}$$$. This is because there is no edge from any value in $$$p_1, \dots, p_{i-1}$$$ to any value in $$$p_i, \dots, p_n$$$.

Otherwise, suppose that for every $$$i$$$, we have that $$$\mathrm{pre}_{i-1} \lt \mathrm{suf}_i$$$. Then for every $$$i$$$, we have that there exists a path from $$$p_{i-1}$$$ to $$$p_i$$$, by going from $$$p_{i-1}$$$ to $$$\mathrm{pre}_{i-1}$$$ to $$$\mathrm{suf}_i$$$ to $$$p_i$$$. Since the graph consisting of these paths is connected, it must have some spanning tree, so the answer is $$$\texttt{Yes}$$$.

#include <bits/stdc++.h>
using namespace std;
 
void solve(){
    int n;
    cin >> n;
    vector<int> p(n+1), pre(n+1, n), suf(n+2);
    for(int i=1; i<=n; i++){
        cin >> p[i];
        pre[i] = min(pre[i-1], p[i]);
    }
    for(int i=n; i>=1; i--)
        suf[i] = max(suf[i+1], p[i]);
    for(int i=2; i<=n; i++)
        if(pre[i-1] > suf[i]){
            cout << "No" << '\n';
            return;
        }
    cout << "Yes" << '\n';
}
 
int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    cin >> t;
    while(t--) solve();
}

Suppose that $$$\mathrm{pre}_{i-1} \lt \mathrm{suf}_i$$$ for all $$$i$$$. Let $$$s_1 \lt \dots \lt s_k = n$$$ denote the indices satisfying $$$p_i = \mathrm{suf}_i$$$, that is, the suffix maxes of $$$p$$$. Then let's partition $$$p$$$ into blocks ending at each $$$s_i$$$. Now, consider a block consisting of $$$p[l, r]$$$ for $$$l=s_{i-1}+1$$$ and $$$r=s_i$$$. We have that $$$\mathrm{suf}_l = \mathrm{suf}_r = p_r$$$ by construction, which means that all values in $$$p[l, r-1]$$$ are less than $$$p_r$$$. So we can connect all of these values to $$$p_r$$$.

Now, each block is connected, so it suffices to connect the blocks to each other. We have that $$$\mathrm{pre}_{l-1} \lt \mathrm{suf}_l = p_r$$$, so we can connect $$$p_r$$$ to $$$\mathrm{pre}_{l-1}$$$. By induction, we see that all blocks are now connected, since each block is connected to some previous block.

#include <bits/stdc++.h>
using namespace std;
 
void solve(){
    int n;
    cin >> n;
    vector<int> p(n+1), pre(n+1, n);
    vector<pair<int, int>> suf(n+2);
    for(int i=1; i<=n; i++){
        cin >> p[i];
        pre[i] = min(pre[i-1], p[i]);
    }
    for(int i=n; i>=1; i--)
        suf[i] = max(suf[i+1], {p[i], i});
    for(int i=2; i<=n; i++)
        if(pre[i-1] > suf[i].first){
            cout << "No" << '\n';
            return;
        }
    cout << "Yes" << '\n';
    for(int l=1; l<=n;){
        int r = suf[l].second;
        for(int i=l; i<r; i++)
            cout << p[i] << ' ' << p[r] << '\n';
        if(l > 1)
            cout << pre[l-1] << ' ' << p[r] << '\n';
        l = r+1;
    }
}
 
int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    cin >> t;
    while(t--) solve();
}

• Excellent problem
• Good problem
• Average problem
• Bad problem
• Horrible problem

• Trivial problem
• Easy problem
• Average problem
• Hard problem
• Impossible problem

Let $$$x$$$'s denote elements which all share a common divisor, and let $$$-$$$'s denote any elements. Then an array of the form $$$[-, x, x, -, x, x, \dots]$$$ will have no bad indices. Let's call an array of this form "perfect".

Suppose the $$$x$$$'s are even elements. We have roughly $$$\frac{n}{2}$$$ even elements, which means we can form a perfect array of length roughly $$$\frac{3n}{4}$$$. Now, we have roughly $$$\frac{n}{6}$$$ elements which are odd multiples of $$$3$$$, which means we can form a disjoint perfect array of length roughly $$$\frac{n}{4}$$$. By concatenating these two arrays, we achieve a roughly full permutation with $$$O(1)$$$ bad indices. See the next section for a proof of the bound on bad indices.

Instead of counting bad indices, we will count good indices. We form a perfect array of length $$$3\lfloor \frac{n}{4} \rfloor$$$, where all indices are good except for potentially the last one. We also form a perfect array of length $$$3\lfloor \frac{n+3}{12} \rfloor$$$ because we gain a new triple for every pair of $$$\{3, 9\} \pmod{12}$$$. Again, all indices are good except for potentially the last one. Therefore, we achieve $$$3\lfloor \frac{n}{4}\rfloor + 3\lfloor \frac{n+3}{12} \rfloor - 2$$$ good indices. It can be verified for every residue class $$$\bmod 12$$$ that this is lower bounded by $$$n-6$$$. Since there are $$$n-2$$$ indices in total, we have at most $$$4$$$ bad indices.

#include <bits/stdc++.h>
using namespace std;
 
void solve(){
    int n;
    cin >> n;
    vector<vector<int>> a(3);
    for(int i=1; i<=n; i++)
        if(!(i % 2))
            a[0].push_back(i);
        else if(!(i % 3))
            a[1].push_back(i);
        else
            a[2].push_back(i);
    while(a[2].size() >= 1 && a[0].size() >= 2){
        cout << a[2].back() << ' ';
        a[2].pop_back();
        cout << a[0].back() << ' ';
        a[0].pop_back();
        cout << a[0].back() << ' ';
        a[0].pop_back();
    }
    while(a[2].size() >= 1 && a[1].size() >= 2){
        cout << a[2].back() << ' ';
        a[2].pop_back();
        cout << a[1].back() << ' ';
        a[1].pop_back();
        cout << a[1].back() << ' ';
        a[1].pop_back();
    }
    for(int i : a[0])
        cout << i << ' ';
    for(int i : a[1])
        cout << i << ' ';
    for(int i : a[2])
        cout << i << ' ';
    cout << '\n';
}
 
int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    cin >> t;
    while(t--) solve();
}

A construction commented by d1amondzz seems to prove an upper bound of $$$f(3), f(5) \leq 1$$$ and $$$f(n) = 0$$$ for $$$n\neq 3, 5$$$. I think several other comments may have alluded to a similar solution as well. The general idea is that for the largest prefix of primes $$$p_1, ..., p_k$$$ satisfying $$$p_{k-1}\cdot p_k \leq n$$$, we can construct an array $$$q$$$ as follows: for each $$$p_i$$$, first append $$$p_i$$$ to $$$q$$$, then append all elements with smallest prime factor $$$p_i$$$, ending with $$$p_i\cdot p_{i+1}$$$. Then all adjacent elements are not coprime, so as long as this array is of size at least roughly $$$\frac{2}{3}n$$$, we can intersperse it with the remaining elements to achieve no bad indices. All composites are included in $$$q$$$, because if a composite number has smallest prime factor at least $$$p_{k+1}$$$, then its value is at least $$$(p_{k+1})^2 \gt p_k\cdot p_{k+1} \gt n$$$ by construction of $$$k$$$. So we have that $$$q$$$ is of length asympototically at least $$$n-\frac{n}{\log n}$$$, which is asymptotically at least $$$cn$$$ for any $$$c \lt 1$$$. We can furthermore verify that this construction works for all small $$$n$$$ except for $$$3$$$ and $$$5$$$.

As for the lower bound, it's easy to see that $$$f(3) \geq 1$$$ since all pairs are coprime, and that $$$f(5) \geq 1$$$ since the only pair that is not coprime is $$$\{2, 4\}$$$, but we cannot have that these elements appear in all triples. Therefore, we have that $$$f(3) = f(5) = 1$$$ and $$$f(n) = 0$$$ for $$$n\neq 3, 5$$$.

• Excellent problem
• Good problem
• Average problem
• Bad problem
• Horrible problem

• Trivial problem
• Easy problem
• Average problem
• Hard problem
• Impossible problem

Let's fix the number of double operations we use; call this integer $$$k$$$. Now, we can treat each value independently.

Consider a specific pair $$$a_i, b_i$$$. If we don't apply any addition operations, we have that $$$a_i$$$ becomes $$$a_i \cdot 2^k$$$. Clearly we need that $$$a_i \cdot 2^k \leq b_i$$$. Now, observe that applying an addition operation before applying $$$j$$$ of the $$$k$$$ double operations is equivalent to adding $$$2^j$$$ to our final sum. We need to add $$$b_i - a_i \cdot 2^k$$$, so in total, we apply $$$\lfloor \frac{b_i - a_i \cdot 2^k}{2^k} \rfloor = \lfloor \frac{b_i}{2^k} \rfloor - a_i$$$ addition operations at the beginning, each adding $$$2^k$$$ to our sum. Then, we apply $$$\texttt{popcount}((b_i - a_i \cdot 2^k)\pmod{2^k}) = \texttt{popcount}(b_i\pmod{2^k})$$$ addition operations later, where $$$\texttt{popcount}(x)$$$ denotes the number of set bits in $$$x$$$. This is because, if the $$$j$$$-th bit of $$$b_i - a_i \cdot 2^k$$$ is set for some $$$j \lt k$$$, we would like to apply an operation before applying $$$j$$$ of the double operations so we can add $$$2^j$$$ to our sum.

We would like to choose the largest number of double operations possible, since a double operation increases all values by at least one. Furthermore, since $$$n\geq 2$$$, a double operation is strictly more effective than an addition operation. However, we still need to satisfy $$$a_i \cdot 2^k \leq b_i$$$ for all $$$i$$$. Therefore, we will choose $$$k=\min \log_2{\frac{b_i}{a_i}}$$$.

Between each double operation, the addition operations can be rearranged. Let's consider all of the addition operations applied before applying exactly $$$j$$$ double operations; denote these values $$$c_1, \dots, c_n$$$, where $$$c_i$$$ is the number of addition operations performed on element $$$a_i$$$. Then we can multiply our number of sequences by $$${\sum c_i \choose c_1, \dots, c_n}$$$, the multinomial coefficient of $$$c_i$$$. This is equal to $$$\frac{(\sum c_i)!}{\prod (c_i!)}$$$. To simplify implementation, note that for $$$j \lt k$$$, all $$$c_i$$$ are either $$$0$$$ or $$$1$$$, so the denominator is only nontrivial for $$$j=k$$$. The final answer is the product of these values across all $$$0\leq j\leq k$$$. See the next section for intuition on multinomial coefficients and some of the details on its implementation.

The intuition behind the formula for multinomial coefficients is as follows: let's say $$$n=3$$$, and we want to find the number of ways to color $$$\sum c_i$$$ balls such that $$$c_1$$$ are red, $$$c_2$$$ are green, and $$$c_3$$$ are blue. Let's call our positions "red $$$1$$$" $$$\dots$$$ "red $$$c_1$$$" $$$\dots$$$ "blue $$$c_3$$$". Now, it's clear that there are $$$(\sum c_i)!$$$ ways to assign each ball to a position, because we have $$$\sum c_i$$$ choices of balls to assign to "red $$$1$$$", then $$$\sum c_i - 1$$$ remaining choices of balls to assign to "red $$$2$$$", and so forth, until we only have one choice of balls to assign to "blue $$$c_3$$$". However, this overcounts, because there is no difference between assigning ball $$$1$$$ to "red $$$1$$$" and ball $$$2$$$ to "red $$$2$$$", and vice versa. We are overcounting the red assignments by a factor of $$$c_1!$$$, because every valid selection of red balls achieves $$$c_1!$$$ assignments of red balls to positions. Similar reasoning holds for the green and blue balls, so in total, we have $$$\frac{(\sum c_i)!}{\prod (c_i!)}$$$ different sequences.

Multinomial coefficients can be computed by precomputing factorials. For the numerator, note that if $$$\sum c_i \geq 10^6+3$$$ then $$$(\sum c_i)! \equiv 0\pmod{10^6+3}$$$ because we have a factor of $$$10^6+3$$$, so we only need to precompute factorials up to $$$10^6+2$$$. For the denominator, we can divide by $$$c_i!$$$ by multiplying by the modular inverse of $$$c_i!$$$ modulo $$$10^6+3$$$. Crucially, note that $$$c_i \lt 10^6+3$$$ because the number of addition operations you can apply is at most $$$b_i - a_i \lt 10^6$$$, so modular inverses are well-defined.

#include <bits/stdc++.h>
#define int long long
using namespace std;
 
int mod = 1e6+3;
 
vector<int> fact(mod);
 
int inv(int a){
    return a <= 1 ? a : mod - mod / a * inv(mod % a) % mod;
}
 
void solve(){
    int n, x, ans = 1;
    cin >> n;
    vector<int> a(n), b(n);
    for(int i=0; i<n; i++)
        cin >> a[i];
    for(int i=0; i<n; i++)
        cin >> b[i];
    int k = __lg(b[0] / a[0]);
    for(int i=1; i<n; i++)
        k = min(k, __lg(b[i] / a[i]));
    x = k;
    vector<int> cnt(k), c(n);
    for(int i=0; i<n; i++){
        for(int j=0; j<k; j++){
            cnt[j] += b[i] & 1;
            b[i] >>= 1;
        }
        c[i] = b[i] - a[i];
    }
    for(int j=0; j<k; j++){
        x += cnt[j];
        ans = ans * fact[cnt[j]] % mod;
    }
    int last = accumulate(c.begin(), c.end(), 0LL);
    ans = (last < mod ? ans * fact[last] % mod : 0);
    for(int i : c){
        x += i;
        ans = ans * inv(fact[i]) % mod;
    }
    cout << x << ' ' << ans << '\n';
}
 
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    fact[0] = 1;
    for(int i=1; i<mod; i++) fact[i] = fact[i-1] * i % mod;
    int t;
    cin >> t;
    while(t--) solve();
}

• Excellent problem
• Good problem
• Average problem
• Bad problem
• Horrible problem

• Trivial problem
• Easy problem
• Average problem
• Hard problem
• Impossible problem

Let's first try to solve this problem with inefficient time and memory, then we will later optimize it. For $$$1\leq i\leq n$$$ and $$$0\leq j\leq m-n$$$, let $$$\mathrm{dp}[i][j]$$$ denote the largest score achievable from the first $$$i$$$ indices, while also satisfying $$$a_i = i+j$$$. Now, since $$$a$$$ must be strictly increasing, we equivalently have that $$$a_i - i$$$ is monotonically increasing. Therefore, we can transition as follows: $$$\mathrm{dp}[i][j] = \max_{k\leq j} \mathrm{dp}[i-1][k] + v(i, i+j)$$$, because we may choose $$$a_{i-1}$$$ to be any value satisfying $$$a_{i-1} - (i-1) \leq j$$$, then we choose $$$a_i = i+j$$$, adding a score of $$$v(i, i+j)$$$.

Now, we will try to remove the first dimension; that is, $$$\mathrm{dp}[j]$$$ denotes the largest score achievable while also satisfying $$$a_i = i+j$$$, where we will update this array as we iterate through all $$$i$$$. We will store this in a data structure that supports quickly querying prefix maximums and increasing point values; in particular, either a Fenwick tree or a segment tree will work.

Suppose we are at some stage $$$i$$$ and would like to update $$$\mathrm{dp}[j]$$$. As before, we want to update it to $$$\max_{k\leq j} \mathrm{dp}[k] + v(i, i+j)$$$. We should process $$$j$$$ in reverse order, as we want to ensure that we are accessing $$$\mathrm{dp}[i-1][k]$$$ instead of $$$\mathrm{dp}[i][k]$$$.

However, we only have to update $$$\mathrm{dp}[j]$$$ if $$$v(i, i+j)$$$ is nonzero. This is because, if $$$v(i, i+j)$$$ is zero, then we are updating $$$\mathrm{dp}[j]$$$ to $$$\max_{k\leq j} \mathrm{dp}[k]$$$. However, since we are only querying prefix maximums, any query involving $$$j$$$ will implicitly query all $$$k\leq j$$$ anyways, so it is not necessary to explicitly update $$$\mathrm{dp}[j]$$$. Our final answer is $$$\max \mathrm{dp}[j]$$$. See the next section for runtime analysis.

For simplicity of analysis, assume $$$m - n \geq c$$$ for some reasonable $$$c$$$, to avoid pathological cases where $$$\log (m-n)$$$ is undefined or zero.

For each $$$i$$$, we are updating $$$O(\frac{m-n}{i})$$$ values. Therefore, in total, we have $$$O(\sum \frac{m-n}{i}) = O((m-n)H(n))$$$ updates. Since harmonic numbers are known to grow logarithmically, this is $$$O((m-n)\log n)$$$. Each update takes $$$O(\log (m-n))$$$ time, as it involves a query and an update on a Fenwick tree or segment tree of size $$$m-n+1$$$. So the updates in total take $$$O((m-n)\log n\log{(m-n)})$$$ time.

However, we also need to compute $$$v(i, i+j)$$$ for each update. This will take $$$O(\sum v(i, i+j))$$$ time. For a fixed $$$i$$$, we have that $$$O(\frac{m-n}{i})$$$ values satisfy $$$v(i, i+j) \geq 1$$$, $$$O(\frac{m-n}{i^2})$$$ values satisfy $$$v(i, i+j) \geq 2$$$, and so forth. Therefore, for a fixed $$$i$$$, we have that $$$\sum v(i, i+j) = O(\sum \frac{m-n}{i^k}) = O(\frac{m-n}{i}\sum \frac{1}{i^{k-1}}) = O(\frac{m-n}{i} \cdot \frac{1}{1-\frac{1}{i}}) = O(\frac{m-n}{i} \cdot \frac{i}{i-1}) = O((m-n) \cdot \frac{1}{i-1})$$$. Across all $$$i\geq 2$$$, we have $$$O((m-n)H(n-1)) = O((m-n)\log n)$$$. This is dominated by the $$$O((m-n)\log n\log{(m-n)})$$$ term from the updates.

Finally, we have an additional $$$n$$$ term, as we have to iterate through all $$$i\leq n$$$. Our total runtime is $$$O((m-n)\log n\log{(m-n)} + n)$$$.

#include <bits/stdc++.h>
using namespace std;
 
void solve(){
    int n, m;
    cin >> n >> m;
    vector<int> mx(m-n+1);
    function<int(int)> query = [&](int i)->int{
        int ret = 0;
        for(; i>=0; i=(i&i+1)-1)
            ret = max(ret, mx[i]);
        return ret;
    };
    function<void(int, int)> update = [&](int i, int val){
        for(; i<=m-n; i|=i+1)
            mx[i] = max(mx[i], val);
    };
    function<int(int, int)> v = [](int b, int x)->int{
        int ans = 0;
        while(!(x % b)){
            ans++;
            x /= b;
        }
        return ans;
    };
    for(int i=2; i<=n; i++)
        for(int j=(m-n+i)/i*i; j>=i; j-=i)
            update(j-i, query(j-i) + v(i, j));
    cout << query(m-n) << '\n';
}
 
int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    cin >> t;
    while(t--) solve();
}

• Excellent problem
• Good problem
• Average problem
• Bad problem
• Horrible problem

• Trivial problem
• Easy problem
• Average problem
• Hard problem
• Impossible problem