# Educational Codeforces Round 117 (Rated for Div. 2)(Educational Codeforces Round 117 (Rated for Div. 2))-其他

## Educational Codeforces Round 117 (Rated for Div. 2)(Educational Codeforces Round 117 (Rated for Div. 2))

### A. Distance

#include<bits/stdc++.h>
using namespace std;

#define ll long long
#define ld long double
const ld pi = acos(-1);
const int maxn = 1111;

signed main()
{
int t;cin >> t;
while(t--)
{
int x,y;
cin >> x >> y;
if((x+y)&1)
{
cout << "-1 -1" << endl;
continue;
}
int p = (x+y)/2;
if(p<=x){
cout << p << " 0" << endl;
}
else
{
cout << x << " " << p-x << endl;
}
}

return 0;
}


### B. Special Permutation

#include<bits/stdc++.h>
using namespace std;

#define ll long long
#define ld long double
const ld pi = acos(-1);
const int maxn = 1111;

int k[10004];

signed main()
{
int t;cin >> t;
while(t--)
{
int n;cin >> n;
for(int i=1;i<=n;++i)
k[i] = n-i+1;
int a,b;cin >> a >> b;
if(b<n/2||a>n/2+1||(a<=n/2&&b<=n/2)||(a>n/2&&b>n/2))
{
cout << -1 << endl;
continue;
}
if(a<b) swap(k[n-a+1],k[n-b+1]);
for(int i=1;i<n;++i)
cout  << k[i] << " ";
cout << k[n] << endl;
}

return 0;
}


### C. Chat Ban

#include<bits/stdc++.h>
using namespace std;

#define ll long long
#define ld long double
const ld pi = acos(-1);
const int maxn = 1111;

int k[10004];

signed main()
{
int t;cin >> t;
while(t--)
{
ll k,x;
cin >> k >> x;
ll l = 1,r = 2*k-1;
while(l<r)
{
ll mid = (l+r) >> 1;
bool ok = 1;
if(mid<=k){
ll emo = mid*(mid+1)/2;
if(emo>=x) ok = 0;
}
else{
ll emo = k*(k+1)/2+(mid-k)*(k-1+2*k-mid)/2;
if(emo>=x) ok = 0;
}
if(ok) l = mid + 1;
else r = mid;
//cout << "l " << l << "r "<< r << endl;
}
cout << l << endl;
}

return 0;
}


### D. X-Magic Pair

#include<bits/stdc++.h>
using namespace std;

#define ll long long
#define ld long double
const ld pi = acos(-1);
const int maxn = 1111;

int k[10004];

signed main()
{
int t;cin >> t;
while(t--)
{
ll a,b,x;
cin >> a >> b >> x;
while(1)
{
if(a<b) swap(a,b);
if(a==x){
cout << "YES" << endl;
break;
}
if(b==0)
{
cout << "NO" << endl;
break;
}
if(a<x){
cout << "NO" << endl;
break;
}
if(a%b==x%b)
{
cout << "YES" << endl;
break;
}
a = a % b;
}
}

return 0;
}


### E. Messages(补题)

#include<bits/stdc++.h>
using namespace std;

#define ll long long
#define ld long double
const ld pi = acos(-1);
const int maxn = 200005;

int n;
struct M
{
ll v;
int id;
} mes[maxn];
bool cmp(M a,M b)
{
return a.v > b.v;
}
int m[maxn];
int k[maxn];
double ans;
vector<int> ansv;

signed main()
{
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin >> n;
for(int i=1;i<=n;++i)
{
cin >> m[i] >> k[i];
}
for(int t=1;t<=20;++t)
{
for(int i=1;i<maxn;++i)
{
mes[i].v = 0;
mes[i].id = i;
}
for(int i=1;i<=n;++i)
{
if(k[i]>=t) mes[m[i]].v += t;
else mes[m[i]].v += k[i];
}
sort(mes+1,mes+maxn,cmp);
vector<int> tmp;
ll a = 0;
for(int i=1;i<=t;++i)
{
a += mes[i].v;
tmp.push_back(mes[i].id);
}
if((double)a/t>ans)
{
ans = (double)a/t;
ansv = tmp;
}
}
cout << ansv.size() << endl;
for(int i=0;i<ansv.size()-1;++i)
cout << ansv[i] << " ";
cout << ansv[ansv.size()-1] << endl;

return 0;
}


### F. Armor and Weapons(补题)

#include<bits/stdc++.h>
using namespace std;

#define ll long long
typedef pair<int,int> P;
const int maxn = 1000005;
const ll mod = 1e9+7;

int n,m,q;
set<P> s;
vector<P> v;

bool cmp(P a,P b)
{
if(a.first==b.first)
return a.second > b.second;
else
return a.first > b.first;
}

signed main()
{
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin >> n >> m ;
cin >> q;
int x,y;
for(int i=1;i<=q;++i)
{
cin >> x >> y;
s.insert(make_pair(x,y));
}

int step = 0;
v.push_back(make_pair(1,1));
while(1)
{
if(v[0]==make_pair(n,m)) break;
vector<P> tmp;
for(auto k : v)
{
int sum = k.first + k.second;
if(s.count(k)) sum++;

tmp.push_back(make_pair(min(sum,n),k.second));
tmp.push_back(make_pair(k.first,min(sum,m)));
}

sort(tmp.begin(),tmp.end(),cmp);
int y = 0;
vector<P> tmp2;
for(auto k : tmp)
{
if(k.second>y)
{
y = k.second;
tmp2.push_back(k);
}
}
step++;
v = tmp2;
/*cout << "step " << step << endl;
for(auto k : v)
{
cout << k.first << " " << k.second << endl;
}*/
}
cout << step << endl;

return 0;
}


### G. Max Sum Array(补题)

• 频率最大的数一定在两端，且它们对答案产生的贡献与除了两端之外其他的数的位置无关。
• 如果有多个频率最大的数，它们一定都排列在两端，且它们对答案的总贡献与它们在两端排列的相对位置无关。

#include<bits/stdc++.h>
using namespace std;

#define ll long long
const int maxn = 1000005;
const ll mod = 1e9+7;

int n;
ll num[maxn];
ll fac[maxn];
ll ansp = 1;
ll ansv = 0;

signed main()
{
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin >> n;
fac[0] = fac[1] = 1;
for(int i=2;i<maxn;++i)
fac[i] = (fac[i-1] * i) % mod;
int a;
ll total = 0;
for(int i=1;i<=n;++i)
{
cin >> a;
num[a]++;
total += a;
}
for(int i=maxn-1;i>=2;--i)
{
ansp = fac[num[i]] * fac[num[i]] % mod * ansp % mod;
ansv = (ansv + num[i]*(total-num[i])%mod*(i-1)%mod)%mod;
num[i-2] += num[i];
total -= 2 * num[i];
}
ansp = ansp * fac[num[1]] % mod;
cout << ansv << " " << ansp << endl;

return 0;
}

————————

### A. Distance

The problem requires finding the midpoint of Manhattan distance between \ ((0,0) \) and \ ((x, y) \).

First judge whether the distance exists, that is, whether the Manhattan distance is odd. If it exists, you can start from the origin, walk horizontally and then walk vertically to construct the position of the midpoint.

#include<bits/stdc++.h>
using namespace std;

#define ll long long
#define ld long double
const ld pi = acos(-1);
const int maxn = 1111;

signed main()
{
int t;cin >> t;
while(t--)
{
int x,y;
cin >> x >> y;
if((x+y)&1)
{
cout << "-1 -1" << endl;
continue;
}
int p = (x+y)/2;
if(p<=x){
cout << p << " 0" << endl;
}
else
{
cout << x << " " << p-x << endl;
}
}

return 0;
}


### B. Special Permutation

The problem is to give an arrangement with an even length. Given a and B, it is required that the minimum value of the left half of the arrangement is a and the maximum value of the right half is B.

First judge whether there is a solution. If B is smaller than half of the elements or a is larger than half of the elements, there is no solution. If a and B are on the same half, there is no solution.

If you have a solution, you can determine that a and B are on different halves. Using the method of construction, the arrangement is in descending order, and then exchange a and B (if necessary).

#include<bits/stdc++.h>
using namespace std;

#define ll long long
#define ld long double
const ld pi = acos(-1);
const int maxn = 1111;

int k[10004];

signed main()
{
int t;cin >> t;
while(t--)
{
int n;cin >> n;
for(int i=1;i<=n;++i)
k[i] = n-i+1;
int a,b;cin >> a >> b;
if(b<n/2||a>n/2+1||(a<=n/2&&b<=n/2)||(a>n/2&&b>n/2))
{
cout << -1 << endl;
continue;
}
if(a<b) swap(k[n-a+1],k[n-b+1]);
for(int i=1;i<n;++i)
cout  << k[i] << " ";
cout << k[n] << endl;
}

return 0;
}


### C. Chat Ban

It should belong to an obvious dichotomy.

#include<bits/stdc++.h>
using namespace std;

#define ll long long
#define ld long double
const ld pi = acos(-1);
const int maxn = 1111;

int k[10004];

signed main()
{
int t;cin >> t;
while(t--)
{
ll k,x;
cin >> k >> x;
ll l = 1,r = 2*k-1;
while(l<r)
{
ll mid = (l+r) >> 1;
bool ok = 1;
if(mid<=k){
ll emo = mid*(mid+1)/2;
if(emo>=x) ok = 0;
}
else{
ll emo = k*(k+1)/2+(mid-k)*(k-1+2*k-mid)/2;
if(emo>=x) ok = 0;
}
if(ok) l = mid + 1;
else r = mid;
//cout << "l " << l << "r "<< r << endl;
}
cout << l << endl;
}

return 0;
}


### D. X-Magic Pair

The question gives a and B, and you can choose an absolute value of A-B at a time, and ask if you can transform X.

Considering that each operation must replace the large number with the result, otherwise it will loop. Then consider direct subtraction, but if a number is large, it will definitely be t. At this time, I thought of taking the mold. Because it can be regarded as the effect of modulus until the end. If x appears in the process of subtraction, X must be congruent with the large number. So keep taking the mold, similar to GCD.

#include<bits/stdc++.h>
using namespace std;

#define ll long long
#define ld long double
const ld pi = acos(-1);
const int maxn = 1111;

int k[10004];

signed main()
{
int t;cin >> t;
while(t--)
{
ll a,b,x;
cin >> a >> b >> x;
while(1)
{
if(a<b) swap(a,b);
if(a==x){
cout << "YES" << endl;
break;
}
if(b==0)
{
cout << "NO" << endl;
break;
}
if(a<x){
cout << "NO" << endl;
break;
}
if(a%b==x%b)
{
cout << "YES" << endl;
break;
}
a = a % b;
}
}

return 0;
}


### E. Messages(补题)

Each student has a required message M and the maximum number of top messages K. ask which top messages make the maximum expected number of required messages to be read.

Assuming that the number of selected messages is fixed as t, the expectation of the contribution of each selected message to the result can be calculated. For each student {m, K}, message M can contribute more min (1, K / T) to the result. Then select the first t messages that contribute the most, which is the optimal solution when the number of messages is t.

Since K does not exceed 20, t is enumerated from 1 to 20 and compared to obtain the global optimal solution.

#include<bits/stdc++.h>
using namespace std;

#define ll long long
#define ld long double
const ld pi = acos(-1);
const int maxn = 200005;

int n;
struct M
{
ll v;
int id;
} mes[maxn];
bool cmp(M a,M b)
{
return a.v > b.v;
}
int m[maxn];
int k[maxn];
double ans;
vector<int> ansv;

signed main()
{
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin >> n;
for(int i=1;i<=n;++i)
{
cin >> m[i] >> k[i];
}
for(int t=1;t<=20;++t)
{
for(int i=1;i<maxn;++i)
{
mes[i].v = 0;
mes[i].id = i;
}
for(int i=1;i<=n;++i)
{
if(k[i]>=t) mes[m[i]].v += t;
else mes[m[i]].v += k[i];
}
sort(mes+1,mes+maxn,cmp);
vector<int> tmp;
ll a = 0;
for(int i=1;i<=t;++i)
{
a += mes[i].v;
tmp.push_back(mes[i].id);
}
if((double)a/t>ans)
{
ans = (double)a/t;
ansv = tmp;
}
}
cout << ansv.size() << endl;
for(int i=0;i<ansv.size()-1;++i)
cout << ansv[i] << " ";
cout << ansv[ansv.size()-1] << endl;

return 0;
}


### F. Armor and Weapons(补题)

At the beginning, there are equipment sets \ (a = \ {1 \}, B = \ {1 \} \) from which you can select \ (a_i, b_j \) each time, and put \ (a_i + b_j \) into a or B. for some given {\ (a_i, b_j \)}, you can put \ (a_i + b_j + 1 \) and ask how many times you can get \ (a_n, b_m \).

After reading the solution, it suddenly dawned on me. First, be sure to choose the most cost-effective of the two sets. Then this problem is equivalent to BFS, finding the shortest path from state {1,1} to {n, m}. In the problem solution, in order to optimize the time complexity, the layers (i.e. nodes with the same number of steps) searched each time are sorted from top right to bottom left, and the smaller points in the same column are eliminated to ensure that the number of nodes accessed by each layer is \ (O (M) \), so that the slowest speed is \ (O (\ log m) \) close to m, and then close to N at the speed of \ (\ frac {n}{m} \), and the complexity is \ (O (m) \ times o (\ log m + \ frac {n}) {m})=O(m\log m+n)\)。

#include<bits/stdc++.h>
using namespace std;

#define ll long long
typedef pair<int,int> P;
const int maxn = 1000005;
const ll mod = 1e9+7;

int n,m,q;
set<P> s;
vector<P> v;

bool cmp(P a,P b)
{
if(a.first==b.first)
return a.second > b.second;
else
return a.first > b.first;
}

signed main()
{
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin >> n >> m ;
cin >> q;
int x,y;
for(int i=1;i<=q;++i)
{
cin >> x >> y;
s.insert(make_pair(x,y));
}

int step = 0;
v.push_back(make_pair(1,1));
while(1)
{
if(v[0]==make_pair(n,m)) break;
vector<P> tmp;
for(auto k : v)
{
int sum = k.first + k.second;
if(s.count(k)) sum++;

tmp.push_back(make_pair(min(sum,n),k.second));
tmp.push_back(make_pair(k.first,min(sum,m)));
}

sort(tmp.begin(),tmp.end(),cmp);
int y = 0;
vector<P> tmp2;
for(auto k : tmp)
{
if(k.second>y)
{
y = k.second;
tmp2.push_back(k);
}
}
step++;
v = tmp2;
/*cout << "step " << step << endl;
for(auto k : v)
{
cout << k.first << " " << k.second << endl;
}*/
}
cout << step << endl;

return 0;
}


### G. Max Sum Array(补题)

The solution is wonderful. I feel there are two key points.

• The number with the largest frequency must be at both ends, and their contribution to the answer is independent of the position of other numbers except at both ends.
• If there are multiple numbers with the largest frequency, they must be arranged at both ends, and their total contribution to the answer is independent of their relative position at both ends.

According to the above two points, we use the idea of recursion to solve it.

#include<bits/stdc++.h>
using namespace std;

#define ll long long
const int maxn = 1000005;
const ll mod = 1e9+7;

int n;
ll num[maxn];
ll fac[maxn];
ll ansp = 1;
ll ansv = 0;

signed main()
{
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin >> n;
fac[0] = fac[1] = 1;
for(int i=2;i<maxn;++i)
fac[i] = (fac[i-1] * i) % mod;
int a;
ll total = 0;
for(int i=1;i<=n;++i)
{
cin >> a;
num[a]++;
total += a;
}
for(int i=maxn-1;i>=2;--i)
{
ansp = fac[num[i]] * fac[num[i]] % mod * ansp % mod;
ansv = (ansv + num[i]*(total-num[i])%mod*(i-1)%mod)%mod;
num[i-2] += num[i];
total -= 2 * num[i];
}
ansp = ansp * fac[num[1]] % mod;
cout << ansv << " " << ansp << endl;

return 0;
}