# Codeforces Round #560 (Div. 3)

## A. Remainder

time limit per test1 second memory limit per test256 megabytes

You are given a huge decimal number consisting of 𝑛n digits. It is guaranteed that this number has no leading zeros. Each digit of this number is either 0 or 1.

You may perform several (possibly zero) operations with this number. During each operation you are allowed to change any digit of your number; you may change 0 to 1 or 1 to 0. It is possible that after some operation you can obtain a number with leading zeroes, but it does not matter for this problem.

You are also given two integers 0≤𝑦<𝑥<𝑛0≤y<x<n. Your task is to calculate the minimum number of operations you should perform to obtain the number that has remainder 10𝑦10y modulo 10𝑥10x. In other words, the obtained number should have remainder 10𝑦10y when divided by 10𝑥10x.Input

The first line of the input contains three integers 𝑛,𝑥,𝑦n,x,y (0≤𝑦<𝑥<𝑛≤2⋅1050≤y<x<n≤2⋅105) — the length of the number and the integers 𝑥x and 𝑦y, respectively.

The second line of the input contains one decimal number consisting of 𝑛n digits, each digit of this number is either 0 or 1. It is guaranteed that the first digit of the number is 1.Output

Print one integer — the minimum number of operations you should perform to obtain the number having remainder 10𝑦10y modulo 10𝑥10x. In other words, the obtained number should have remainder 10𝑦10y when divided by 10𝑥10x.
Examplesinput

11 5 2
11010100101

output

1

input

11 5 1
11010100101

output

3

Note

In the first example the number will be 1101010010011010100100 after performing one operation. It has remainder 100100 modulo 100000100000.

In the second example the number will be 1101010001011010100010 after performing three operations. It has remainder 1010 modulo 100000100000.

#### 题目挺唬人的，其实就是截取原串的最后y位，然后从后往前第x位是1，其他都是0，看看有几个不一样就好了

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)2e5+100;
const int INF=0x3f3f3f3f;
int a[maxn];
int main(){
int n,x,y;cin>>n>>x>>y;
string s;cin>>s;
int ans=0;
for(int i=n-1;i>=n-x;--i){
if(i==n-1-y){
if(s[i]=='0') ans++;
}
else{
if(s[i]=='1') ans++;
}
}
printf("%d\n",ans);
}


## B. Polycarp Training

time limit per test2 seconds memory limit per test256 megabytes

Polycarp wants to train before another programming competition. During the first day of his training he should solve exactly 11 problem, during the second day — exactly 22 problems, during the third day — exactly 33 problems, and so on. During the 𝑘k-th day he should solve 𝑘k problems.

Polycarp has a list of 𝑛n contests, the 𝑖i-th contest consists of 𝑎𝑖ai problems. During each day Polycarp has to choose exactly one of the contests he didn’t solve yet and solve it. He solves exactly 𝑘k problems from this contest. Other problems are discarded from it. If there are no contests consisting of at least 𝑘k problems that Polycarp didn’t solve yet during the 𝑘k-th day, then Polycarp stops his training.

How many days Polycarp can train if he chooses the contests optimally?Input

The first line of the input contains one integer 𝑛n (1≤𝑛≤2⋅1051≤n≤2⋅105) — the number of contests.

The second line of the input contains 𝑛n integers 𝑎1,𝑎2,…,𝑎𝑛a1,a2,…,an (1≤𝑎𝑖≤2⋅1051≤ai≤2⋅105) — the number of problems in the 𝑖i-th contest.Output

Print one integer — the maximum number of days Polycarp can train if he chooses the contests optimally.
Examplesinput

4
3 1 4 1

output

3

input

3
1 1 1

output

1

input

5
1 1 1 2 2

output

2

#### 签到

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=(int)2e5+100;
int a[maxn];
int main(){
int n;
scanf("%d",&n);
rep(i,1,n) scanf("%d",&a[i]); sort(a+1,a+1+n);
int k=1;
rep(i,1,n) if(a[i]>=k) k++;
printf("%d\n",k-1);
}


## C. Good String

time limit per test1 second memory limit per test256 megabytes

Let’s call (yet again) a string good if its length is even, and every character in odd position of this string is different from the next character (the first character is different from the second, the third is different from the fourth, and so on). For example, the strings good, stringand xyyx are good strings, and the strings bad, aa and aabc are not good. Note that the empty string is considered good.

You are given a string 𝑠s, you have to delete minimum number of characters from this string so that it becomes good.Input

The first line contains one integer 𝑛n (1≤𝑛≤2⋅1051≤n≤2⋅105) — the number of characters in 𝑠s.

The second line contains the string 𝑠s, consisting of exactly 𝑛n lowercase Latin letters.Output

In the first line, print one integer 𝑘k (0≤𝑘≤𝑛0≤k≤n) — the minimum number of characters you have to delete from 𝑠s to make it good.

In the second line, print the resulting string 𝑠s. If it is empty, you may leave the second line blank, or not print it at all.
Examplesinput

4
good

output

0
good

input

4
aabc

output

2
ab

input

3
aaa

output

3

#### 删除字符的策略是，当前字符和下一个一样的话把当前的删掉，记录删除字符的总数，如果和原串的奇偶性不相同则再删掉最后一个字符

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)2e5+100;
const int INF=0x3f3f3f3f;
int main(){
int n;cin>>n;
string s;cin>>s;
int tot=0;
for(int i=0;i+1<n;i+=2) if(s[i]==s[i+1]) s[i]='#',i--,tot++;
if((n%2==0&&tot%2)||(n%2&&tot%2==0)) s[n-1]='#',tot++;
printf("%d\n",tot);
for(int i=0;i<n;++i) if(s[i]!='#') cout<<s[i];
}


## D. Almost All Divisors

time limit per test2 seconds memory limit per test256 megabytes

We guessed some integer number 𝑥x. You are given a list of almost all its divisors. Almost all means that there are all divisors except 11and 𝑥x in the list.

Your task is to find the minimum possible integer 𝑥x that can be the guessed number, or say that the input data is contradictory and it is impossible to find such number.

You have to answer 𝑡t independent queries.Input

The first line of the input contains one integer 𝑡t (1≤𝑡≤251≤t≤25) — the number of queries. Then 𝑡t queries follow.

The first line of the query contains one integer 𝑛n (1≤𝑛≤3001≤n≤300) — the number of divisors in the list.

The second line of the query contains 𝑛n integers 𝑑1,𝑑2,…,𝑑𝑛d1,d2,…,dn (2≤𝑑𝑖≤1062≤di≤106), where 𝑑𝑖di is the 𝑖i-th divisor of the guessed number. It is guaranteed that all values 𝑑𝑖di are distinct.Output

For each query print the answer to it.

If the input data in the query is contradictory and it is impossible to find such number 𝑥x that the given list of divisors is the list of almost all its divisors, print -1. Otherwise print the minimum possible 𝑥x.
Exampleinput

2
8
8 2 12 6 4 24 16 3
1
2

output

48
4

#### 很容易想到，假设序列是合法的，那么给原数列排个序，a*a[n]=a*a[n-1]=a*a[n-2]=….=ans对于所有i都成立这样判断完之后再看看我们得到的ans分解出来的因数个数和题目给的一不一样

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(ll i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)2e5+100;
const int INF=0x3f3f3f3f;
ll a;
int main(){
int T;cin>>T;
while(T--){
int n;cin>>n;
rep(i,1,n) scanf("%lld",&a[i]); sort(a+1,a+1+n);
ll ans=a*a[n];
int flag=0;
rep(i,2,(n+1)/2){
if(a[i]*a[n-i+1]!=ans){flag=1;break;}
}
int num=0;
rep(i,2,sqrt(ans)){
if(ans%i==0){
if(i*i==ans) num++;
else num+=2;
}
}
if(num!=n) flag=1;
if(flag) puts("-1");
else printf("%lld\n",ans);
}
}


## E. Two Arrays and Sum of Functions

time limit per test2 seconds memory limit per test256 megabytes

You are given two arrays 𝑎a and 𝑏b, both of length 𝑛n.

Let’s define a function 𝑓(𝑙,𝑟)=∑𝑙≤𝑖≤𝑟𝑎𝑖⋅𝑏𝑖f(l,r)=∑l≤i≤rai⋅bi.

Your task is to reorder the elements (choose an arbitrary order of elements) of the array 𝑏b to minimize the value of ∑1≤𝑙≤𝑟≤𝑛𝑓(𝑙,𝑟)∑1≤l≤r≤nf(l,r). Since the answer can be very large, you have to print it modulo 998244353998244353. Note that you should minimize the answer but not its remainder.Input

The first line of the input contains one integer 𝑛n (1≤𝑛≤2⋅1051≤n≤2⋅105) — the number of elements in 𝑎a and 𝑏b.

The second line of the input contains 𝑛n integers 𝑎1,𝑎2,…,𝑎𝑛a1,a2,…,an (1≤𝑎𝑖≤1061≤ai≤106), where 𝑎𝑖ai is the 𝑖i-th element of 𝑎a.

The third line of the input contains 𝑛n integers 𝑏1,𝑏2,…,𝑏𝑛b1,b2,…,bn (1≤𝑏𝑗≤1061≤bj≤106), where 𝑏𝑗bj is the 𝑗j-th element of 𝑏b.Output

Print one integer — the minimum possible value of ∑1≤𝑙≤𝑟≤𝑛𝑓(𝑙,𝑟)∑1≤l≤r≤nf(l,r) after rearranging elements of 𝑏b, taken modulo 998244353998244353. Note that you should minimize the answer but not its remainder.
Examplesinput

5
1 8 7 2 4
9 7 2 9 3

output

646

input

1
1000000
1000000

output

757402647

input

2
1 3
4 2

output

20

#### 因为a不能换位置，所以对于每个a[i]，它对于答案的贡献次数就是 (n-i+1)*i ；又由于b是可以换位置的，那么将a乘上贡献次数的权值之后降序排列，再把b升序排列，两两相乘得到的结果必然最小(反证法证明)

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)2e5+100;
const int INF=0x3f3f3f3f;
const int mod=998244353;
ll a[maxn],b[maxn],n;
int main(){
cin>>n;
for(ll i=1;i<=n;++i){
scanf("%lld",&a[i]);
a[i]*=((n-i+1)*i);
}
rep(i,1,n) scanf("%lld",&b[i]);
sort(b+1,b+1+n,greater<int>());
sort(a+1,a+1+n);
ll ans=0;
rep(i,1,n){
ans+=((a[i]%mod)*(b[i]%mod))%mod;
}
ans=(ans+mod)%mod;
printf("%lld\n",ans);
}


## F2. Microtransactions (hard version)

time limit per test3 seconds memory limit per test256 megabytes

The only difference between easy and hard versions is constraints.

Ivan plays a computer game that contains some microtransactions to make characters look cooler. Since Ivan wants his character to be really cool, he wants to use some of these microtransactions — and he won’t start playing until he gets all of them.

Each day (during the morning) Ivan earns exactly one burle.

There are 𝑛n types of microtransactions in the game. Each microtransaction costs 22 burles usually and 11 burle if it is on sale. Ivan has to order exactly 𝑘𝑖ki microtransactions of the 𝑖i-th type (he orders microtransactions during the evening).

Ivan can order any (possibly zero) number of microtransactions of any types during any day (of course, if he has enough money to do it). If the microtransaction he wants to order is on sale then he can buy it for 11 burle and otherwise he can buy it for 22 burles.

There are also 𝑚m special offers in the game shop. The 𝑗j-th offer (𝑑𝑗,𝑡𝑗)(dj,tj) means that microtransactions of the 𝑡𝑗tj-th type are on sale during the 𝑑𝑗dj-th day.

Ivan wants to order all microtransactions as soon as possible. Your task is to calculate the minimum day when he can buy all microtransactions he want and actually start playing.Input

The first line of the input contains two integers 𝑛n and 𝑚m (1≤𝑛,𝑚≤2⋅1051≤n,m≤2⋅105) — the number of types of microtransactions and the number of special offers in the game shop.

The second line of the input contains 𝑛n integers 𝑘1,𝑘2,…,𝑘𝑛k1,k2,…,kn (0≤𝑘𝑖≤2⋅1050≤ki≤2⋅105), where 𝑘𝑖ki is the number of copies of microtransaction of the 𝑖i-th type Ivan has to order. It is guaranteed that sum of all 𝑘𝑖ki is not less than 11 and not greater than 2⋅1052⋅105.

The next 𝑚m lines contain special offers. The 𝑗j-th of these lines contains the 𝑗j-th special offer. It is given as a pair of integers (𝑑𝑗,𝑡𝑗)(dj,tj) (1≤𝑑𝑗≤2⋅105,1≤𝑡𝑗≤𝑛1≤dj≤2⋅105,1≤tj≤n) and means that microtransactions of the 𝑡𝑗tj-th type are on sale during the 𝑑𝑗dj-th day.Output

Print one integer — the minimum day when Ivan can order all microtransactions he wants and actually start playing.
Examplesinput

5 6
1 2 0 2 0
2 4
3 3
1 5
1 2
1 5
2 3

output

8

input

5 3
4 2 1 3 2
3 5
4 2
2 5

output

20

#### 显然可以二分答案，那么难点就在于如何判断这个答案的合理性我们贪心的去想，最坏情况下需要sum*2天，所以只有用到了优惠才能减小答案，也就是说优惠的商品数量越多越好所以显然，如果同一个商品在不同几天都有优惠政策，肯定是最后一天用情况更优，因为我需要用到更多的优惠次数，如果之前有优惠就用掉了，可能会有后面的优惠钱不够的情况

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)4e5+100;
const int INF=0x3f3f3f3f;
int n,m,sum=0,M;
int a[maxn];
vector<int> v[maxn];
int ck(int x){
int last[maxn]={0,},tem[maxn]={0,},mon=0,tot=0;
rep(i,1,x) for(auto j:v[i]) last[j]=max(last[j],i);
rep(i,1,x){
++mon;
for(auto j:v[i])
while(tem[j]<a[j]&&mon&&last[j]==i) --mon,tem[j]++,tot++;
}
return mon>=(sum-tot)*2;
}
int main(){
cin>>n>>m;
rep(i,1,n) scanf("%d",&a[i]),sum+=a[i];
rep(i,1,m){
int d,t;scanf("%d%d",&d,&t);M=max(M,d);
v[d].pb(t);
}
int l=0,r=sum*2,m=(l+r)>>1,ans=0;
while(l<=r){
if(ck(m)) ans=m,r=m-1;
else l=m+1;
m=(l+r)>>1;
}
printf("%d\n",ans);
}