[A](https://mirror.codeforces.com/gym/105805/problem/A)↵
↵
Idea:[user:imranakki,2025-01-23], [user:wuhudsm,2025-01-23]↵
↵
<spoiler summary="solution">↵
↵
Let $x = n \times k + r$, where $r$ is the remainder when $x$ is divided by $n$ ($r < n$).↵
↵
$x + $ $(x$ $mod$ $n)$ $= n \times k + r + r = n \times k + 2 \times r = n$↵
↵
First case: $k = 0$↵
↵
$2 \times r = n$, $r$ must be an integer, so we have $+1$ solution if $n$ is even.↵
↵
Second case: $k = 1$↵
↵
$n + 2 \times r = n$, $\Rightarrow r = 0$, here we have $+1$ solution for every $n$.↵
↵
In general:↵
↵
If $n$ is even, we have $2$ solutions.↵
↵
If $n$ is odd, we have only $1$ solution.↵
↵
</spoiler>↵
↵
↵
<spoiler summary="code(C++)">↵
```cpp↵
#include <bits/stdc++.h>↵
using namespace std;↵
#define ll long long ↵
#define fast \↵
ios_base::sync_with_stdio(0); \↵
cin.tie(0); \↵
cout.tie(0);↵
↵
int main(){↵
fast;↵
ll t;↵
cin>>t;↵
while(t--){↵
ll n;↵
cin>>n;↵
if(n%2) cout<<"1\n";↵
else cout<<"2\n";↵
} ↵
}↵
```↵
</spoiler>↵
↵
<spoiler summary="Rate the Problem">↵
Amazing problem: [likes:2039A,option1]↵
↵
Good problem: [likes:2039A,option2]↵
↵
Average problem: [likes:2039A,option3]↵
↵
Bad problem: [likes:2039A,option4]↵
↵
Didn't solve: [likes:2039A,option5]↵
</spoiler>↵
↵
↵
[B](https://mirror.codeforces.com/gym/105805/problem/B)↵
↵
Idea:[user:kaosar_the_Joyboy,2025-03-16]↵
↵
<spoiler summary="solution">↵
Let $n$ in canonical form be ${a_1} ^ {b_1} \times {a_2} ^ {b_2} \times {a_3} ^ {b_3} ...$, where $a_{i}$ is the $i-$th prime number and $b_{i}$ is its power. For example: $2025 = 2 ^ 0 \times 3 ^ 4 \times 5 ^ 2 \times 7 ^ 0 \times 11 ^ 0 ...$.↵
↵
Let $E$ be an even square number. That means $E = e ^ 2$. $E$ is even, when $e$ is even too $\Rightarrow$ $E = e ^ 2 = (2 \times k) ^ 2 = 4 \times k^2$. We can see that $E$ is divisible by $2^2$. $E$ is square number $\Rightarrow$ every power is even. So we can represent $E = {c_1} ^ {d_1} \times {c_2} ^ {d_2} \times {c_3} ^ {d_3} ...$ where $c_{i}$ is the $i-$th prime number, $d_{i}$ is its power, $d_{i}$ is always even, and we know that $2^2$ divides $O$, so $d_{1} \ge 2$. $(*)$↵
↵
Let $O$ be an odd square number. In analogical way: $O = {x_1} ^ {y_1} \times {x_2} ^ {y_2} \times {x_3} ^ {y_3} ...$ where $x_{i}$ is the $i-$th prime number and $y_{i}$ is its power. $O$ is not even, so we know for sure that $y_{1} = 0$. And $O$ is square number $\Rightarrow$ all $y$ are even numbers. $(**)$↵
↵
Now we can calculate $f(n)$ and $g(n)$. We know that $n = {a_1} ^ {b_1} \times {a_2} ^ {b_2} \times {a_3} ^ {b_3} ...$.↵
↵
From $(*)$: $f(n) = (\lfloor \frac{b_{1}}{2} \rfloor) \times (\lfloor \frac{b_{2}}{2} \rfloor + 1) \times (\lfloor \frac{b_{3}}{2} \rfloor + 1) ...$↵
↵
From $(**):$ $g(n) = (\lfloor \frac{b_{2}}{2} \rfloor + 1) \times (\lfloor \frac{b_{3}}{2} \rfloor + 1) \times (\lfloor \frac{b_{4}}{2} \rfloor + 1) ...$↵
↵
$\frac{f(n)}{g(n)} = \lfloor \frac{b_{1}}{2} \rfloor$. We know $a_{1} = 2$, so we must find the largest power of $2$, which divides $n$, and the final answer is this power divided by $2$.↵
↵
</spoiler>↵
↵
↵
<spoiler summary="code(C++)">↵
↵
```C++↵
#include <bits/stdc++.h>↵
using namespace std;↵
#define ll long long ↵
#define fast \↵
ios_base::sync_with_stdio(0); \↵
cin.tie(0); \↵
cout.tie(0);↵
↵
int main(){↵
fast;↵
ll t;↵
cin>>t;↵
while(t--){↵
ll n;↵
cin>>n;↵
if(n%2) cout<<"0\n";↵
else{↵
ll cnt=0;↵
while(n%2==0){↵
n/=2;↵
cnt++;↵
}↵
cout<<(cnt/2)<<"\n";↵
}↵
} ↵
}↵
```↵
↵
↵
</spoiler>↵
↵
<spoiler summary="Rate the Problem">↵
Amazing problem: [likes:2039b,option1]↵
↵
Good problem: [likes:2039b,option2]↵
↵
Average problem: [likes:2039b,option3]↵
↵
Bad problem: [likes:2039b,option4]↵
↵
Didn't solve: [likes:2039b,option5]↵
</spoiler>↵
↵
[C](https://mirror.codeforces.com/gym/105805/problem/C)↵
↵
Idea:[user:b00s,2025-01-23]↵
↵
↵
↵
<spoiler summary="solution">↵
↵
↵
↵
↵
</spoiler>↵
↵
↵
↵
<spoiler summary="code(C++)">↵
↵
↵
~~~~~↵
#include <bits/stdc++.h>↵
using namespace std;↵
#define ll long long ↵
#define fast \↵
ios_base::sync_with_stdio(0); \↵
cin.tie(0); \↵
cout.tie(0);↵
↵
int main(){↵
fast;↵
ll t;↵
cin>>t;↵
while(t--){↵
ll n;↵
cin>>n;↵
vector<ll> a(n);↵
for(ll i=0;i<n;i++) cin>>a[i];↵
if(n>=5) cout<<"YES\n";↵
else{↵
bool ok=true;↵
for(ll i=0;i<n;i++){↵
if(a[i]%2!=(i+1)%2) ok=false;↵
}↵
if(ok) cout<<"YES\n";↵
else cout<<"NO\n";↵
}↵
} ↵
}↵
~~~~~↵
↵
↵
↵
</spoiler>↵
↵
↵
<spoiler summary="Rate the Problem">↵
Amazing problem: [likes:2039c,option1]↵
↵
Good problem: [likes:2039c,option2]↵
↵
Average problem: [likes:2039c,option3]↵
↵
Bad problem: [likes:2039c,option4]↵
↵
Didn't solve: [likes:2039c,option5]↵
</spoiler>↵
↵
[D](https://mirror.codeforces.com/gym/105805/problem/D)↵
↵
Idea:[user:wuhudsm,2025-01-23]↵
↵
<spoiler summary="solution">↵
↵
An important observation is that for an $i$, its contribution for inversions is only related to the type of operation, and not to the arrangement of the numbers before $i$.↵
↵
Note:↵
↵
- $left[i]$: number of inversions made by $a[i]$ if we insert it to front.↵
↵
- $right[i]$: number of inversions made by $a[i]$ if we insert it to back.↵
↵
We can calculate $left[i]$ and $right[i]$ for each $i$ independently using Fenwick tree.↵
↵
To find the answer for each $j$, we can sort $(left[i],right[i])$ by the value of $(left[i]-right[i])$. Then run the greedy algorithm.↵
↵
</spoiler>↵
↵
↵
↵
<spoiler summary="code">↵
```cpp↵
#include <map>↵
#include <set>↵
#include <cmath>↵
#include <ctime>↵
#include <queue>↵
#include <stack>↵
#include <cstdio>↵
#include <cstdlib>↵
#include <vector>↵
#include <cstring>↵
#include <algorithm>↵
#include <iostream>↵
#include <bitset>↵
using namespace std;↵
typedef double db; ↵
typedef long long ll;↵
typedef unsigned long long ull;↵
const int N=1000010;↵
const int LOGN=28;↵
const ll TMD=0;↵
const ll INF=2147483647;↵
int T,n;↵
int a[N],BIT[N],op1[N],op2[N],d[N];↵
↵
void add(int p,int x)↵
{↵
for(int i=p;i<=n;i+=(i&-i)) BIT[i]+=x;↵
}↵
↵
int getsum(int p)↵
{↵
int sum=0;↵
for(int i=p;i;i-=(i&-i)) sum+=BIT[i];↵
return sum;↵
}↵
↵
int main()↵
{↵
scanf("%d",&T);↵
while(T--)↵
{↵
scanf("%d",&n);↵
for(int i=1;i<=n;i++) scanf("%d",&a[i]);↵
for(int i=1;i<=n;i++) BIT[i]=0;↵
for(int i=1;i<=n;i++)↵
{↵
op1[i]=getsum(a[i]-1);↵
op2[i]=getsum(n)-getsum(a[i]);↵
d[i]=op1[i]-op2[i];↵
add(a[i],1);↵
}↵
ll cur=0;↵
for(int i=1;i<=n;i++) cur+=op2[i];↵
printf("%I64d ",cur);↵
sort(d+1,d+n+1);↵
for(int i=1;i<=n;i++)↵
{↵
cur+=d[i]; ↵
printf("%I64d%c",cur,i==n?'\n':' ');↵
}↵
}↵
↵
return 0;↵
}↵
↵
```↵
↵
</spoiler>↵
↵
<spoiler summary="Rate the Problem">↵
Amazing problem: [likes:2039d,option1]↵
↵
Good problem: [likes:2039d,option2]↵
↵
Average problem: [likes:2039d,option3]↵
↵
Bad problem: [likes:2039d,option4]↵
↵
Didn't solve: [likes:2039d,option5]↵
</spoiler>↵
↵
[E1](https://mirror.codeforces.com/gym/105805/problem/E1)+[E2](https://mirror.codeforces.com/gym/105805/problem/E2)↵
↵
Idea:[user:xksark,2025-01-23] (easy version), [user:wuhudsm,2025-01-23] (hard version)↵
↵
<spoiler summary="solution (easy version)">↵
↵
Let's say we have already found the positions of the numbers $0$, $1$, $\ldots$, $k-1$ and want to find the position where the number $k$ is hidden. We will add positions of the numbers $0$, $1$, $\ldots$, $k-1$ to each query and binary search on the remaining positions that are not yet occupied. ↵
↵
Number of queries made is $\Sigma_{i=0}^{n-1} \log(n-i) \le 9n+1$.↵
↵
↵
</spoiler>↵
↵
<spoiler summary="solution (hard version)">↵
↵
First, let's identify the positions of $0$ and $1$. Then we will find that this method is applicable to any $x$ and $x+1$.↵
↵
Let $S_0$ and $S_1$ be the sets of possible positions for $0$ and $1$, respectively. Initially, $S_0 = S_1 = \{0, 1, ..., n-1 \} $.↵
↵
Case $1$: $S_0 = S_1$.↵
↵
Let $lhalf$ be a half of $S_0$, and $rhalf = S_0 - lhalf$. Consider querying $lhalf$:↵
↵
- If the answer is $1$, we immediately know that $0$ is in $lhalf$ and $1$ is in $rhalf$.↵
↵
- If the answer is $>1$, we immediately know that both $0$ and $1$ are in $lhalf$.↵
↵
- If the answer is $0$, we need to query rhalf once more to determine the distribution of $0$ and $1$.↵
↵
Through this operation, we reduce the size of both $S_0$ and $S_1$ by half. If randomization is used, the expected number of queries needed is $\frac{3}{2}$.↵
↵
Case 2: $S_0$ and $S_1$ are disjoint.↵
↵
Similarly, we randomly select half of $S_0$, $lhalf_0$, and half of $S_1$, $lhalf_1$. Consider querying $lhalf_0∩∪ lhalf_1$:↵
↵
If the answer is $1$ or $>1$, we can reduce the size of both $S_0$ and $S_1$ by half with just one query.↵
↵
Otherwise, we need to spend an additional query on $rhalf_0∩∪ lhalf_1$.↵
↵
The total (expected) number of queries is $\frac{3}{4}$ of the easy version (i.e. $\frac{3}{4}\ \cdot 9n=6.275n$ ).↵
↵
What is the probability that the number of queries exceeds $7n$? After transformation, this problem is equivalent to tossing a uniform coin $5000$ times, with a probability of facing up more than $3000$ times. This is a binomial distribution. We approximate it using a normal distribution, calculate the Z-value, and query the table. We can know that the probability is less than $10^{-9}$, which is small enough.↵
↵
</spoiler>↵
↵
<spoiler summary="code(easy version)">↵
↵
~~~~~↵
#include <bits/stdc++.h>↵
#define endl '\n'↵
↵
using ll = long long;↵
using namespace std;↵
↵
const ll MOD = 1e9 + 7;↵
↵
int perm[1026];↵
int id[1026];↵
↵
void solve()↵
{↵
int n;↵
↵
cin >> n;↵
↵
set <int> st;↵
↵
for (int i = 0; i < n; i++)↵
{↵
perm[i] = id[i] = 0;↵
st.insert(i);↵
}↵
↵
for (int i = 0; i < n; i++)↵
{↵
int l = 0, r = st.size() - 1;↵
int mid, pos = *(st.rbegin());↵
↵
while (l < r)↵
{↵
mid = l + r >> 1;↵
↵
vector <int> query;↵
↵
for (int q = 0; q < i; q++)↵
{↵
query.push_back(id[q]);↵
}↵
↵
int curr = -1;↵
int last = 0;↵
↵
for (auto it : st)↵
{↵
curr++;↵
query.push_back(it);↵
↵
if (curr == mid)↵
{↵
last = it;↵
↵
break;↵
}↵
}↵
↵
cout << "? " << query.size();↵
↵
for (auto it : query)↵
{↵
cout << " " << it;↵
}↵
↵
cout << endl;↵
cout.flush();↵
↵
int mex;↵
↵
cin >> mex;↵
↵
if (mex > i)↵
{↵
r = mid;↵
pos = last;↵
}↵
else↵
{↵
l = mid + 1;↵
}↵
}↵
↵
perm[pos] = i;↵
st.erase(pos);↵
id[i] = pos;↵
↵
cout << "! " << pos << " " << i << endl;↵
cout.flush();↵
}↵
}↵
↵
int main()↵
{↵
ios::sync_with_stdio(0);↵
cin.tie(0);↵
cout.tie(0);↵
↵
int t;↵
↵
cin >> t;↵
↵
while (t--)↵
{↵
solve();↵
}↵
↵
return 0;↵
}↵
↵
↵
~~~~~↵
↵
↵
</spoiler>↵
↵
<spoiler summary="code(hard version)">↵
↵
~~~~~↵
#include <bits/stdc++.h>↵
using namespace std;↵
↵
#define all(x) x.begin(),x.end()↵
↵
const int N = 2000;↵
int n, ans[N];↵
↵
vector<int> f; // position of already found nums↵
↵
int ask(vector<int> &v) { // asking funciton for case 1↵
cout << "? " << (int)v.size() + (int)f.size(); ↵
for(int &x : f) cout << ' ' << x-1;↵
for(int &x : v) cout << ' ' << x-1;↵
cout << endl;↵
↵
int mex;↵
cin >> mex;↵
return mex;↵
}↵
↵
int ask(vector<int> &v, vector<int> &u) { // asking function for case 2↵
cout << "? " << (int)v.size() + (int)u.size() + (int)f.size();↵
for(int &x : f) cout << ' ' << x-1;↵
for(int &x : v) cout << ' ' << x-1;↵
for(int &x : u) cout << ' ' << x-1;↵
cout << endl;↵
↵
int mex;↵
cin >> mex;↵
return mex;↵
}↵
↵
void answer(int i,int v)↵
{↵
cout<<"! "<<i<<' '<<v<<endl;↵
cout<<flush;↵
}↵
↵
void rand_shuffle(vector<int> &v, vector<int> &q1, vector<int> &q2) {↵
int sz = v.size();↵
for(int i = 0; i < sz; ++i) { // random shuffle↵
int j = rand() % (i + 1);↵
swap(v[i], v[j]);↵
}↵
for(int i = 0; i < sz; ++i) {↵
if(i + i < sz) {↵
q1.push_back(v[i]);↵
} else {↵
q2.push_back(v[i]);↵
}↵
}↵
}↵
↵
void solve() {↵
cin >> n;↵
↵
set<int> pos;↵
for(int i = 1; i <= n; ++i) pos.insert(i);↵
↵
for(int cur = 1; cur < n; cur += 2) {↵
vector<int> A(all(pos)), B(all(pos));↵
↵
while(A.size() > 1 || B.size() > 1) {↵
↵
bool ok = (A[0] == B[0]); // To check for case 1 or 2↵
vector<int> q1, q2, q3, q4;↵
↵
rand_shuffle(A, q1, q2); // shuffle and split the set S0↵
↵
if(ok) { // Case 1 : S0 == S1↵
↵
int mex = ask(q1);↵
if(mex > cur) { ↵
A = q1;↵
B = q1;↵
} else if(mex == cur) {↵
A = q1;↵
B = q2;↵
} else {↵
mex = ask(q2);↵
if(mex > cur) {↵
A = q2;↵
B = q2;↵
} else {↵
A = q2;↵
B = q1;↵
}↵
}↵
↵
} else { // Case 2 : S0 != S1↵
↵
rand_shuffle(B, q3, q4); // shuffle and split the set S1↵
↵
int mex = ask(q1, q3);↵
if(mex > cur) {↵
A = q1;↵
B = q3;↵
} else if(mex == cur) {↵
A = q1;↵
B = q4;↵
} else {↵
mex = ask(q2, q3);↵
if(mex > cur) {↵
A = q2;↵
B = q3;↵
} else {↵
A = q2;↵
B = q4;↵
}↵
}↵
}↵
}↵
↵
//↵
answer(A[0]-1,cur-1);↵
answer(B[0]-1,cur);↵
//↵
↵
ans[A[0]] = cur - 1; // fill the answer↵
ans[B[0]] = cur;↵
↵
pos.erase(A[0]); // erase the already used positions ↵
pos.erase(B[0]);↵
↵
f.push_back(A[0]); // add used positions for all future queries↵
f.push_back(B[0]);↵
}↵
↵
if(n & 1) {↵
answer(*pos.begin()-1,n-1);↵
↵
ans[*pos.begin()] = n - 1;↵
}↵
↵
/*↵
cout << "!";↵
for(int i = 1; i <= n; ++i) cout << ' ' << ans[i];↵
cout << endl; ↵
*/↵
↵
f.clear();↵
}↵
↵
int main() {↵
ios::sync_with_stdio(false);↵
cin.tie(nullptr);↵
↵
srand(chrono::steady_clock::now().time_since_epoch().count());↵
↵
int tt = 1; ↵
cin >> tt;↵
while(tt--) {↵
solve();↵
}↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
<spoiler summary="Rate the Problem">↵
Amazing problem: [likes:2039e,option1]↵
↵
Good problem: [likes:2039e,option2]↵
↵
Average problem: [likes:2039e,option3]↵
↵
Bad problem: [likes:2039e,option4]↵
↵
Didn't solve: [likes:2039e,option5]↵
</spoiler>↵
↵
↵
[F](https://mirror.codeforces.com/gym/105805/problem/F)↵
↵
Idea:[user:wuhudsm,2025-01-23]↵
↵
↵
<spoiler summary="solution">↵
↵
Note $b[i]$: Number of $j$'s with $a[j] >= i$.↵
↵
Let's see what happens when a move happens. ↵
↵
$oldb[i]=(number\ of\ olda[j]=i)+(number\ of\ olda[j]>i)$. ↵
↵
For all $L<=i<R$, all $a[j]=i$ has been decreased by $1$ so $newb[i]=(number\ of\ olda[j]>i)=oldb[i+1]$. This is left shift $b[L...R]$. ↵
↵
What about $b[R]$? Since we can choose any $a[j]=R$, the value range of $newb[R]$ is $[oldb[R+1],oldb[R]]$. ↵
↵
Generally, doing an operation in $[L,R]$ is to set $b[L]:=\ a\ value\ in\ [b[R+1],b[R]]$, then left shift $b[L...R]$. ↵
↵
Consider different $R$ (including $+\infty$), the value range of $b[L]$ is $[0,b[L]-1]$, this corresponds to "taking any number ($>0$) of stones from the pile of stones in $b[L]$". ↵
↵
Overall, the game is classical nim game on array $b$.↵
↵
</spoiler>↵
↵
↵
<spoiler summary="code(C++)">↵
↵
↵
~~~~~↵
#include <map>↵
#include <set>↵
#include <cmath>↵
#include <ctime>↵
#include <queue>↵
#include <stack>↵
#include <cstdio>↵
#include <cstdlib>↵
#include <vector>↵
#include <cstring>↵
#include <algorithm>↵
#include <iostream>↵
#include <bitset>↵
using namespace std;↵
typedef double db; ↵
typedef long long ll;↵
typedef unsigned long long ull;↵
const int N=1000010;↵
const int LOGN=28;↵
const ll TMD=0;↵
const ll INF=2147483647;↵
int T,n;↵
int a[N],b[N];↵
↵
int main()↵
{↵
scanf("%d",&T);↵
while(T--)↵
{↵
scanf("%d",&n);↵
for(int i=1;i<=n;i++) scanf("%d",&a[i]);↵
int NIM_SUM=0,cur=0;↵
vector<int> v;↵
map<int,int> cnt;↵
v.push_back(0);↵
for(int i=1;i<=n;i++)↵
{↵
if(!cnt[a[i]]) v.push_back(a[i]);↵
cnt[a[i]]++;↵
}↵
sort(v.begin(),v.end());↵
for(int i=v.size()-1;i;i--)↵
{↵
cur+=cnt[v[i]];↵
if((v[i]-v[i-1])&1) NIM_SUM^=cur;↵
}↵
printf("%s\n",NIM_SUM?"YES":"NO");↵
}↵
↵
return 0;↵
}↵
↵
~~~~~↵
↵
↵
↵
</spoiler>↵
↵
<spoiler summary="Rate the Problem">↵
Amazing problem: [likes:2039f,option1]↵
↵
Good problem: [likes:2039f,option2]↵
↵
Average problem: [likes:2039f,option3]↵
↵
Bad problem: [likes:2039f,option4]↵
↵
Didn't solve: [likes:2039f,option5]↵
</spoiler>↵
↵
↵
Idea:[user:imranakki,2025-01-23], [user:wuhudsm,2025-01-23]↵
↵
<spoiler summary="solution">↵
↵
Let $x = n \times k + r$, where $r$ is the remainder when $x$ is divided by $n$ ($r < n$).↵
↵
$x + $ $(x$ $mod$ $n)$ $= n \times k + r + r = n \times k + 2 \times r = n$↵
↵
First case: $k = 0$↵
↵
$2 \times r = n$, $r$ must be an integer, so we have $+1$ solution if $n$ is even.↵
↵
Second case: $k = 1$↵
↵
$n + 2 \times r = n$, $\Rightarrow r = 0$, here we have $+1$ solution for every $n$.↵
↵
In general:↵
↵
If $n$ is even, we have $2$ solutions.↵
↵
If $n$ is odd, we have only $1$ solution.↵
↵
</spoiler>↵
↵
↵
<spoiler summary="code(C++)">↵
```cpp↵
#include <bits/stdc++.h>↵
using namespace std;↵
#define ll long long ↵
#define fast \↵
ios_base::sync_with_stdio(0); \↵
cin.tie(0); \↵
cout.tie(0);↵
↵
int main(){↵
fast;↵
ll t;↵
cin>>t;↵
while(t--){↵
ll n;↵
cin>>n;↵
if(n%2) cout<<"1\n";↵
else cout<<"2\n";↵
} ↵
}↵
```↵
</spoiler>↵
↵
<spoiler summary="Rate the Problem">↵
Amazing problem: [likes:2039A,option1]↵
↵
Good problem: [likes:2039A,option2]↵
↵
Average problem: [likes:2039A,option3]↵
↵
Bad problem: [likes:2039A,option4]↵
↵
Didn't solve: [likes:2039A,option5]↵
</spoiler>↵
↵
↵
[B](https://mirror.codeforces.com/gym/105805/problem/B)↵
↵
Idea:[user:kaosar_the_Joyboy,2025-03-16]↵
↵
<spoiler summary="solution">↵
Let $n$ in canonical form be ${a_1} ^ {b_1} \times {a_2} ^ {b_2} \times {a_3} ^ {b_3} ...$, where $a_{i}$ is the $i-$th prime number and $b_{i}$ is its power. For example: $2025 = 2 ^ 0 \times 3 ^ 4 \times 5 ^ 2 \times 7 ^ 0 \times 11 ^ 0 ...$.↵
↵
Let $E$ be an even square number. That means $E = e ^ 2$. $E$ is even, when $e$ is even too $\Rightarrow$ $E = e ^ 2 = (2 \times k) ^ 2 = 4 \times k^2$. We can see that $E$ is divisible by $2^2$. $E$ is square number $\Rightarrow$ every power is even. So we can represent $E = {c_1} ^ {d_1} \times {c_2} ^ {d_2} \times {c_3} ^ {d_3} ...$ where $c_{i}$ is the $i-$th prime number, $d_{i}$ is its power, $d_{i}$ is always even, and we know that $2^2$ divides $O$, so $d_{1} \ge 2$. $(*)$↵
↵
Let $O$ be an odd square number. In analogical way: $O = {x_1} ^ {y_1} \times {x_2} ^ {y_2} \times {x_3} ^ {y_3} ...$ where $x_{i}$ is the $i-$th prime number and $y_{i}$ is its power. $O$ is not even, so we know for sure that $y_{1} = 0$. And $O$ is square number $\Rightarrow$ all $y$ are even numbers. $(**)$↵
↵
Now we can calculate $f(n)$ and $g(n)$. We know that $n = {a_1} ^ {b_1} \times {a_2} ^ {b_2} \times {a_3} ^ {b_3} ...$.↵
↵
From $(*)$: $f(n) = (\lfloor \frac{b_{1}}{2} \rfloor) \times (\lfloor \frac{b_{2}}{2} \rfloor + 1) \times (\lfloor \frac{b_{3}}{2} \rfloor + 1) ...$↵
↵
From $(**):$ $g(n) = (\lfloor \frac{b_{2}}{2} \rfloor + 1) \times (\lfloor \frac{b_{3}}{2} \rfloor + 1) \times (\lfloor \frac{b_{4}}{2} \rfloor + 1) ...$↵
↵
$\frac{f(n)}{g(n)} = \lfloor \frac{b_{1}}{2} \rfloor$. We know $a_{1} = 2$, so we must find the largest power of $2$, which divides $n$, and the final answer is this power divided by $2$.↵
↵
</spoiler>↵
↵
↵
<spoiler summary="code(C++)">↵
↵
```C++↵
#include <bits/stdc++.h>↵
using namespace std;↵
#define ll long long ↵
#define fast \↵
ios_base::sync_with_stdio(0); \↵
cin.tie(0); \↵
cout.tie(0);↵
↵
int main(){↵
fast;↵
ll t;↵
cin>>t;↵
while(t--){↵
ll n;↵
cin>>n;↵
if(n%2) cout<<"0\n";↵
else{↵
ll cnt=0;↵
while(n%2==0){↵
n/=2;↵
cnt++;↵
}↵
cout<<(cnt/2)<<"\n";↵
}↵
} ↵
}↵
```↵
↵
↵
</spoiler>↵
↵
<spoiler summary="Rate the Problem">↵
Amazing problem: [likes:2039b,option1]↵
↵
Good problem: [likes:2039b,option2]↵
↵
Average problem: [likes:2039b,option3]↵
↵
Bad problem: [likes:2039b,option4]↵
↵
Didn't solve: [likes:2039b,option5]↵
</spoiler>↵
↵
[C](https://mirror.codeforces.com/gym/105805/problem/C)↵
↵
Idea:[user:b00s,2025-01-23]↵
↵
↵
↵
<spoiler summary="solution">↵
↵
↵
↵
↵
</spoiler>↵
↵
↵
↵
<spoiler summary="code(C++)">↵
↵
↵
~~~~~↵
#include <bits/stdc++.h>↵
using namespace std;↵
#define ll long long ↵
#define fast \↵
ios_base::sync_with_stdio(0); \↵
cin.tie(0); \↵
cout.tie(0);↵
↵
int main(){↵
fast;↵
ll t;↵
cin>>t;↵
while(t--){↵
ll n;↵
cin>>n;↵
vector<ll> a(n);↵
for(ll i=0;i<n;i++) cin>>a[i];↵
if(n>=5) cout<<"YES\n";↵
else{↵
bool ok=true;↵
for(ll i=0;i<n;i++){↵
if(a[i]%2!=(i+1)%2) ok=false;↵
}↵
if(ok) cout<<"YES\n";↵
else cout<<"NO\n";↵
}↵
} ↵
}↵
~~~~~↵
↵
↵
↵
</spoiler>↵
↵
↵
<spoiler summary="Rate the Problem">↵
Amazing problem: [likes:2039c,option1]↵
↵
Good problem: [likes:2039c,option2]↵
↵
Average problem: [likes:2039c,option3]↵
↵
Bad problem: [likes:2039c,option4]↵
↵
Didn't solve: [likes:2039c,option5]↵
</spoiler>↵
↵
[D](https://mirror.codeforces.com/gym/105805/problem/D)↵
↵
Idea:[user:wuhudsm,2025-01-23]↵
↵
<spoiler summary="solution">↵
↵
An important observation is that for an $i$, its contribution for inversions is only related to the type of operation, and not to the arrangement of the numbers before $i$.↵
↵
Note:↵
↵
- $left[i]$: number of inversions made by $a[i]$ if we insert it to front.↵
↵
- $right[i]$: number of inversions made by $a[i]$ if we insert it to back.↵
↵
We can calculate $left[i]$ and $right[i]$ for each $i$ independently using Fenwick tree.↵
↵
To find the answer for each $j$, we can sort $(left[i],right[i])$ by the value of $(left[i]-right[i])$. Then run the greedy algorithm.↵
↵
</spoiler>↵
↵
↵
↵
<spoiler summary="code">↵
```cpp↵
#include <map>↵
#include <set>↵
#include <cmath>↵
#include <ctime>↵
#include <queue>↵
#include <stack>↵
#include <cstdio>↵
#include <cstdlib>↵
#include <vector>↵
#include <cstring>↵
#include <algorithm>↵
#include <iostream>↵
#include <bitset>↵
using namespace std;↵
typedef double db; ↵
typedef long long ll;↵
typedef unsigned long long ull;↵
const int N=1000010;↵
const int LOGN=28;↵
const ll TMD=0;↵
const ll INF=2147483647;↵
int T,n;↵
int a[N],BIT[N],op1[N],op2[N],d[N];↵
↵
void add(int p,int x)↵
{↵
for(int i=p;i<=n;i+=(i&-i)) BIT[i]+=x;↵
}↵
↵
int getsum(int p)↵
{↵
int sum=0;↵
for(int i=p;i;i-=(i&-i)) sum+=BIT[i];↵
return sum;↵
}↵
↵
int main()↵
{↵
scanf("%d",&T);↵
while(T--)↵
{↵
scanf("%d",&n);↵
for(int i=1;i<=n;i++) scanf("%d",&a[i]);↵
for(int i=1;i<=n;i++) BIT[i]=0;↵
for(int i=1;i<=n;i++)↵
{↵
op1[i]=getsum(a[i]-1);↵
op2[i]=getsum(n)-getsum(a[i]);↵
d[i]=op1[i]-op2[i];↵
add(a[i],1);↵
}↵
ll cur=0;↵
for(int i=1;i<=n;i++) cur+=op2[i];↵
printf("%I64d ",cur);↵
sort(d+1,d+n+1);↵
for(int i=1;i<=n;i++)↵
{↵
cur+=d[i]; ↵
printf("%I64d%c",cur,i==n?'\n':' ');↵
}↵
}↵
↵
return 0;↵
}↵
↵
```↵
↵
</spoiler>↵
↵
<spoiler summary="Rate the Problem">↵
Amazing problem: [likes:2039d,option1]↵
↵
Good problem: [likes:2039d,option2]↵
↵
Average problem: [likes:2039d,option3]↵
↵
Bad problem: [likes:2039d,option4]↵
↵
Didn't solve: [likes:2039d,option5]↵
</spoiler>↵
↵
[E1](https://mirror.codeforces.com/gym/105805/problem/E1)+[E2](https://mirror.codeforces.com/gym/105805/problem/E2)↵
↵
Idea:[user:xksark,2025-01-23] (easy version), [user:wuhudsm,2025-01-23] (hard version)↵
↵
<spoiler summary="solution (easy version)">↵
↵
Let's say we have already found the positions of the numbers $0$, $1$, $\ldots$, $k-1$ and want to find the position where the number $k$ is hidden. We will add positions of the numbers $0$, $1$, $\ldots$, $k-1$ to each query and binary search on the remaining positions that are not yet occupied. ↵
↵
Number of queries made is $\Sigma_{i=0}^{n-1} \log(n-i) \le 9n+1$.↵
↵
↵
</spoiler>↵
↵
<spoiler summary="solution (hard version)">↵
↵
First, let's identify the positions of $0$ and $1$. Then we will find that this method is applicable to any $x$ and $x+1$.↵
↵
Let $S_0$ and $S_1$ be the sets of possible positions for $0$ and $1$, respectively. Initially, $S_0 = S_1 = \{0, 1, ..., n-1 \} $.↵
↵
Case $1$: $S_0 = S_1$.↵
↵
Let $lhalf$ be a half of $S_0$, and $rhalf = S_0 - lhalf$. Consider querying $lhalf$:↵
↵
- If the answer is $1$, we immediately know that $0$ is in $lhalf$ and $1$ is in $rhalf$.↵
↵
- If the answer is $>1$, we immediately know that both $0$ and $1$ are in $lhalf$.↵
↵
- If the answer is $0$, we need to query rhalf once more to determine the distribution of $0$ and $1$.↵
↵
Through this operation, we reduce the size of both $S_0$ and $S_1$ by half. If randomization is used, the expected number of queries needed is $\frac{3}{2}$.↵
↵
Case 2: $S_0$ and $S_1$ are disjoint.↵
↵
Similarly, we randomly select half of $S_0$, $lhalf_0$, and half of $S_1$, $lhalf_1$. Consider querying $lhalf_0
↵
If the answer is $1$ or $>1$, we can reduce the size of both $S_0$ and $S_1$ by half with just one query.↵
↵
Otherwise, we need to spend an additional query on $rhalf_0
↵
The total (expected) number of queries is $\frac{3}{4}$ of the easy version (i.e. $\frac{3}{4}\ \cdot 9n=6.
↵
What is the probability that the number of queries exceeds $7n$? After transformation, this problem is equivalent to tossing a uniform coin $5000$ times, with a probability of facing up more than $3000$ times. This is a binomial distribution. We approximate it using a normal distribution, calculate the Z-value, and query the table. We can know that the probability is less than $10^{-9}$, which is small enough.↵
↵
</spoiler>↵
↵
<spoiler summary="code(easy version)">↵
↵
~~~~~↵
#include <bits/stdc++.h>↵
#define endl '\n'↵
↵
using ll = long long;↵
using namespace std;↵
↵
const ll MOD = 1e9 + 7;↵
↵
int perm[1026];↵
int id[1026];↵
↵
void solve()↵
{↵
int n;↵
↵
cin >> n;↵
↵
set <int> st;↵
↵
for (int i = 0; i < n; i++)↵
{↵
perm[i] = id[i] = 0;↵
st.insert(i);↵
}↵
↵
for (int i = 0; i < n; i++)↵
{↵
int l = 0, r = st.size() - 1;↵
int mid, pos = *(st.rbegin());↵
↵
while (l < r)↵
{↵
mid = l + r >> 1;↵
↵
vector <int> query;↵
↵
for (int q = 0; q < i; q++)↵
{↵
query.push_back(id[q]);↵
}↵
↵
int curr = -1;↵
int last = 0;↵
↵
for (auto it : st)↵
{↵
curr++;↵
query.push_back(it);↵
↵
if (curr == mid)↵
{↵
last = it;↵
↵
break;↵
}↵
}↵
↵
cout << "? " << query.size();↵
↵
for (auto it : query)↵
{↵
cout << " " << it;↵
}↵
↵
cout << endl;↵
cout.flush();↵
↵
int mex;↵
↵
cin >> mex;↵
↵
if (mex > i)↵
{↵
r = mid;↵
pos = last;↵
}↵
else↵
{↵
l = mid + 1;↵
}↵
}↵
↵
perm[pos] = i;↵
st.erase(pos);↵
id[i] = pos;↵
↵
cout << "! " << pos << " " << i << endl;↵
cout.flush();↵
}↵
}↵
↵
int main()↵
{↵
ios::sync_with_stdio(0);↵
cin.tie(0);↵
cout.tie(0);↵
↵
int t;↵
↵
cin >> t;↵
↵
while (t--)↵
{↵
solve();↵
}↵
↵
return 0;↵
}↵
↵
↵
~~~~~↵
↵
↵
</spoiler>↵
↵
<spoiler summary="code(hard version)">↵
↵
~~~~~↵
#include <bits/stdc++.h>↵
using namespace std;↵
↵
#define all(x) x.begin(),x.end()↵
↵
const int N = 2000;↵
int n, ans[N];↵
↵
vector<int> f; // position of already found nums↵
↵
int ask(vector<int> &v) { // asking funciton for case 1↵
cout << "? " << (int)v.size() + (int)f.size(); ↵
for(int &x : f) cout << ' ' << x-1;↵
for(int &x : v) cout << ' ' << x-1;↵
cout << endl;↵
↵
int mex;↵
cin >> mex;↵
return mex;↵
}↵
↵
int ask(vector<int> &v, vector<int> &u) { // asking function for case 2↵
cout << "? " << (int)v.size() + (int)u.size() + (int)f.size();↵
for(int &x : f) cout << ' ' << x-1;↵
for(int &x : v) cout << ' ' << x-1;↵
for(int &x : u) cout << ' ' << x-1;↵
cout << endl;↵
↵
int mex;↵
cin >> mex;↵
return mex;↵
}↵
↵
void answer(int i,int v)↵
{↵
cout<<"! "<<i<<' '<<v<<endl;↵
cout<<flush;↵
}↵
↵
void rand_shuffle(vector<int> &v, vector<int> &q1, vector<int> &q2) {↵
int sz = v.size();↵
for(int i = 0; i < sz; ++i) { // random shuffle↵
int j = rand() % (i + 1);↵
swap(v[i], v[j]);↵
}↵
for(int i = 0; i < sz; ++i) {↵
if(i + i < sz) {↵
q1.push_back(v[i]);↵
} else {↵
q2.push_back(v[i]);↵
}↵
}↵
}↵
↵
void solve() {↵
cin >> n;↵
↵
set<int> pos;↵
for(int i = 1; i <= n; ++i) pos.insert(i);↵
↵
for(int cur = 1; cur < n; cur += 2) {↵
vector<int> A(all(pos)), B(all(pos));↵
↵
while(A.size() > 1 || B.size() > 1) {↵
↵
bool ok = (A[0] == B[0]); // To check for case 1 or 2↵
vector<int> q1, q2, q3, q4;↵
↵
rand_shuffle(A, q1, q2); // shuffle and split the set S0↵
↵
if(ok) { // Case 1 : S0 == S1↵
↵
int mex = ask(q1);↵
if(mex > cur) { ↵
A = q1;↵
B = q1;↵
} else if(mex == cur) {↵
A = q1;↵
B = q2;↵
} else {↵
mex = ask(q2);↵
if(mex > cur) {↵
A = q2;↵
B = q2;↵
} else {↵
A = q2;↵
B = q1;↵
}↵
}↵
↵
} else { // Case 2 : S0 != S1↵
↵
rand_shuffle(B, q3, q4); // shuffle and split the set S1↵
↵
int mex = ask(q1, q3);↵
if(mex > cur) {↵
A = q1;↵
B = q3;↵
} else if(mex == cur) {↵
A = q1;↵
B = q4;↵
} else {↵
mex = ask(q2, q3);↵
if(mex > cur) {↵
A = q2;↵
B = q3;↵
} else {↵
A = q2;↵
B = q4;↵
}↵
}↵
}↵
}↵
↵
//↵
answer(A[0]-1,cur-1);↵
answer(B[0]-1,cur);↵
//↵
↵
ans[A[0]] = cur - 1; // fill the answer↵
ans[B[0]] = cur;↵
↵
pos.erase(A[0]); // erase the already used positions ↵
pos.erase(B[0]);↵
↵
f.push_back(A[0]); // add used positions for all future queries↵
f.push_back(B[0]);↵
}↵
↵
if(n & 1) {↵
answer(*pos.begin()-1,n-1);↵
↵
ans[*pos.begin()] = n - 1;↵
}↵
↵
/*↵
cout << "!";↵
for(int i = 1; i <= n; ++i) cout << ' ' << ans[i];↵
cout << endl; ↵
*/↵
↵
f.clear();↵
}↵
↵
int main() {↵
ios::sync_with_stdio(false);↵
cin.tie(nullptr);↵
↵
srand(chrono::steady_clock::now().time_since_epoch().count());↵
↵
int tt = 1; ↵
cin >> tt;↵
while(tt--) {↵
solve();↵
}↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
<spoiler summary="Rate the Problem">↵
Amazing problem: [likes:2039e,option1]↵
↵
Good problem: [likes:2039e,option2]↵
↵
Average problem: [likes:2039e,option3]↵
↵
Bad problem: [likes:2039e,option4]↵
↵
Didn't solve: [likes:2039e,option5]↵
</spoiler>↵
↵
↵
[F](https://mirror.codeforces.com/gym/105805/problem/F)↵
↵
Idea:[user:wuhudsm,2025-01-23]↵
↵
↵
<spoiler summary="solution">↵
↵
Note $b[i]$: Number of $j$'s with $a[j] >= i$.↵
↵
Let's see what happens when a move happens. ↵
↵
$oldb[i]=(number\ of\ olda[j]=i)+(number\ of\ olda[j]>i)$. ↵
↵
For all $L<=i<R$, all $a[j]=i$ has been decreased by $1$ so $newb[i]=(number\ of\ olda[j]>i)=oldb[i+1]$. This is left shift $b[L...R]$. ↵
↵
What about $b[R]$? Since we can choose any $a[j]=R$, the value range of $newb[R]$ is $[oldb[R+1],oldb[R]]$. ↵
↵
Generally, doing an operation in $[L,R]$ is to set $b[L]:=\ a\ value\ in\ [b[R+1],b[R]]$, then left shift $b[L...R]$. ↵
↵
Consider different $R$ (including $+\infty$), the value range of $b[L]$ is $[0,b[L]-1]$, this corresponds to "taking any number ($>0$) of stones from the pile of stones in $b[L]$". ↵
↵
Overall, the game is classical nim game on array $b$.↵
↵
</spoiler>↵
↵
↵
<spoiler summary="code(C++)">↵
↵
↵
~~~~~↵
#include <map>↵
#include <set>↵
#include <cmath>↵
#include <ctime>↵
#include <queue>↵
#include <stack>↵
#include <cstdio>↵
#include <cstdlib>↵
#include <vector>↵
#include <cstring>↵
#include <algorithm>↵
#include <iostream>↵
#include <bitset>↵
using namespace std;↵
typedef double db; ↵
typedef long long ll;↵
typedef unsigned long long ull;↵
const int N=1000010;↵
const int LOGN=28;↵
const ll TMD=0;↵
const ll INF=2147483647;↵
int T,n;↵
int a[N],b[N];↵
↵
int main()↵
{↵
scanf("%d",&T);↵
while(T--)↵
{↵
scanf("%d",&n);↵
for(int i=1;i<=n;i++) scanf("%d",&a[i]);↵
int NIM_SUM=0,cur=0;↵
vector<int> v;↵
map<int,int> cnt;↵
v.push_back(0);↵
for(int i=1;i<=n;i++)↵
{↵
if(!cnt[a[i]]) v.push_back(a[i]);↵
cnt[a[i]]++;↵
}↵
sort(v.begin(),v.end());↵
for(int i=v.size()-1;i;i--)↵
{↵
cur+=cnt[v[i]];↵
if((v[i]-v[i-1])&1) NIM_SUM^=cur;↵
}↵
printf("%s\n",NIM_SUM?"YES":"NO");↵
}↵
↵
return 0;↵
}↵
↵
~~~~~↵
↵
↵
↵
</spoiler>↵
↵
<spoiler summary="Rate the Problem">↵
Amazing problem: [likes:2039f,option1]↵
↵
Good problem: [likes:2039f,option2]↵
↵
Average problem: [likes:2039f,option3]↵
↵
Bad problem: [likes:2039f,option4]↵
↵
Didn't solve: [likes:2039f,option5]↵
</spoiler>↵
↵
