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[1]*a[n]=a[2]*a[n-1]=a[3]*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[330];
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[1]*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);
}


0 评论