A. Yellow Cards
time limit per test1 second memory limit per test256 megabytes
The final match of the Berland Football Cup has been held recently. The referee has shown nn yellow cards throughout the match. At the beginning of the match there were a1a1 players in the first team and a2a2 players in the second team.
The rules of sending players off the game are a bit different in Berland football. If a player from the first team receives k1k1 yellow cards throughout the match, he can no longer participate in the match — he's sent off. And if a player from the second team receives k2k2 yellow cards, he's sent off. After a player leaves the match, he can no longer receive any yellow cards. Each of nn yellow cards was shown to exactly one player. Even if all players from one team (or even from both teams) leave the match, the game still continues.
The referee has lost his records on who has received each yellow card. Help him to determine the minimum and the maximum number of players that could have been thrown out of the game.Input
The first line contains one integer a1a1 (1≤a1≤1000)(1≤a1≤1000) — the number of players in the first team.
The second line contains one integer a2a2 (1≤a2≤1000)(1≤a2≤1000) — the number of players in the second team.
The third line contains one integer k1k1 (1≤k1≤1000)(1≤k1≤1000) — the maximum number of yellow cards a player from the first team can receive (after receiving that many yellow cards, he leaves the game).
The fourth line contains one integer k2k2 (1≤k2≤1000)(1≤k2≤1000) — the maximum number of yellow cards a player from the second team can receive (after receiving that many yellow cards, he leaves the game).
The fifth line contains one integer nn (1≤n≤a1⋅k1+a2⋅k2)(1≤n≤a1⋅k1+a2⋅k2) — the number of yellow cards that have been shown during the match.Output
Print two integers — the minimum and the maximum number of players that could have been thrown out of the game.
ExamplesinputCopy
2 3 5 1 8
output
0 4
input
3 1 6 7 25
output
4 4
input
6 4 9 10 89
output
5 9
Note
In the first example it could be possible that no player left the game, so the first number in the output is 00. The maximum possible number of players that could have been forced to leave the game is 44 — one player from the first team, and three players from the second.
In the second example the maximum possible number of yellow cards has been shown (3⋅6+1⋅7=25)(3⋅6+1⋅7=25), so in any case all players were sent off.
签到
#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)1e3+100;
const int INF=0x7fffffff;
int a1,a2,k1,k2,n;
int main(){
scanf("%d%d%d%d%d",&a1,&a2,&k1,&k2,&n);
printf("%d ",max(n-a1*(k1-1)-a2*(k2-1),0));
int ans=0;
if(k1>=k2){
int num=n/k2;
ans+=min(a2,num);
n-=ans*k2;
ans+=n/k1;
}
else{
int num=n/k1;
ans+=min(a1,num);
n-=ans*k1;
ans+=n/k2;
}
printf("%d\n",ans);
}
B. The Number of Products
time limit per test2 seconds memory limit per test256 megabytes
You are given a sequence a1,a2,…,ana1,a2,…,an consisting of nn non-zero integers (i.e. ai≠0ai≠0).
You have to calculate two following values:
- the number of pairs of indices (l,r)(l,r) (l≤r)(l≤r) such that al⋅al+1…ar−1⋅aral⋅al+1…ar−1⋅ar is negative;
- the number of pairs of indices (l,r)(l,r) (l≤r)(l≤r) such that al⋅al+1…ar−1⋅aral⋅al+1…ar−1⋅ar is positive;
Input
The first line contains one integer nn (1≤n≤2⋅105)(1≤n≤2⋅105) — the number of elements in the sequence.
The second line contains nn integers a1,a2,…,ana1,a2,…,an (−109≤ai≤109;ai≠0)(−109≤ai≤109;ai≠0) — the elements of the sequence.Output
Print two integers — the number of subsegments with negative product and the number of subsegments with positive product, respectively.
Examplesinput
5 5 -3 3 -1 1
output
8 7
input
10 4 2 -4 3 1 2 -4 3 2 3
output
28 27
input
5 -1 -2 -3 -4 -5
output
9 6
记录乘积为正的段树s1和负的段数s2，最后答案就是s1*s2;
解释：因为我们可以选取任意一段负数段，在后面添加一段负段，因此s1*s2即为答案
#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=0x7fffffff;
int n;
int main(){
scanf("%d",&n);
ll op=1,s1=0,s2=1;
rep(i,1,n){
int x;scanf("%d",&x);
op*=(x>0?1:-1);
if(op>0) s2++;
else s1++;
}
printf("%lld %lld\n",s1*s2,1ll*n*(n+1)/2-s1*s2);
}
C. Swap Letters
time limit per test2 seconds memory limit per test256 megabytes
Monocarp has got two strings ss and tt having equal length. Both strings consist of lowercase Latin letters "a" and "b".
Monocarp wants to make these two strings ss and tt equal to each other. He can do the following operation any number of times: choose an index pos1pos1 in the string ss, choose an index pos2pos2 in the string tt, and swap spos1spos1 with tpos2tpos2.
You have to determine the minimum number of operations Monocarp has to perform to make ss and tt equal, and print any optimal sequence of operations — or say that it is impossible to make these strings equal.Input
The first line contains one integer nn (1≤n≤2⋅105)(1≤n≤2⋅105) — the length of ss and tt.
The second line contains one string ss consisting of nn characters "a" and "b".
The third line contains one string tt consisting of nn characters "a" and "b".Output
If it is impossible to make these strings equal, print −1−1.
Otherwise, in the first line print kk — the minimum number of operations required to make the strings equal. In each of the next kk lines print two integers — the index in the string ss and the index in the string tt that should be used in the corresponding swap operation.
Examplesinput
4 abab aabb
output
2 3 3 3 2
input
1 a b
output
-1
input
8 babbaabb abababaa
output
3 2 6 1 3 7 8
Note
In the first example two operations are enough. For example, you can swap the third letter in ss with the third letter in tt. Then s=s= "abbb", t=t= "aaab". Then swap the third letter in ss and the second letter in tt. Then both ss and tt are equal to "abab".
In the second example it's impossible to make two strings equal.
贪心，记录 s1[i]=='a'&&s2[i]=='b' 和 s1[i]=='b'&&s2[i]=='a' 的个数，显然对于相同类型的一对，只需要一次交换就可以，对于不同的需要两次
#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=0x7fffffff;
int n;
char s1[maxn],s2[maxn];
int v1[maxn],v2[maxn],pos1,pos2;
int main(){
scanf("%d",&n);getchar();
scanf("%s%s",s1+1,s2+1);
rep(i,1,n){
if(s1[i]=='a'&&s2[i]=='b') v1[++pos1]=i;
else if(s1[i]=='b'&&s2[i]=='a') v2[++pos2]=i;
}
if((pos1+pos2)%2) return puts("-1"),0;
if(pos1%2){
printf("%d\n",pos1/2+pos2/2+2);
for(int i=2;i<=pos1-1;i+=2) printf("%d %d\n",v1[i],v1[i-1]);
for(int i=2;i<=pos2-1;i+=2) printf("%d %d\n",v2[i],v2[i-1]);
printf("%d %d\n%d %d\n",v2[pos2],v2[pos2],v1[pos1],v2[pos2]);
}
else{
printf("%d\n",pos1/2+pos2/2);
for(int i=2;i<=pos1;i+=2) printf("%d %d\n",v1[i],v1[i-1]);
for(int i=2;i<=pos2;i+=2) printf("%d %d\n",v2[i],v2[i-1]);
}
}
D. Ticket Game
time limit per test1 second memory limit per test256 megabytes
Monocarp and Bicarp live in Berland, where every bus ticket consists of nn digits (nn is an even number). During the evening walk Monocarp and Bicarp found a ticket where some of the digits have been erased. The number of digits that have been erased is even.
Monocarp and Bicarp have decided to play a game with this ticket. Monocarp hates happy tickets, while Bicarp collects them. A ticket is considered happy if the sum of the first n2n2 digits of this ticket is equal to the sum of the last n2n2 digits.
Monocarp and Bicarp take turns (and Monocarp performs the first of them). During each turn, the current player must replace any erased digit with any digit from 00 to 99. The game ends when there are no erased digits in the ticket.
If the ticket is happy after all erased digits are replaced with decimal digits, then Bicarp wins. Otherwise, Monocarp wins. You have to determine who will win if both players play optimally.Input
The first line contains one even integer nn (2≤n≤2⋅105)(2≤n≤2⋅105) — the number of digits in the ticket.
The second line contains a string of nn digits and "?" characters — the ticket which Monocarp and Bicarp have found. If the ii-th character is "?", then the ii-th digit is erased. Note that there may be leading zeroes. The number of "?" characters is even.Output
If Monocarp wins, print "Monocarp" (without quotes). Otherwise print "Bicarp" (without quotes).
Examplesinput
4 0523
output
Bicarp
input
2 ??
output
Bicarp
input
8 ?054??0?
output
Bicarp
input
6 ???00?
output
Monocarp
Note
Since there is no question mark in the ticket in the first example, the winner is determined before the game even starts, and it is Bicarp.
In the second example, Bicarp also wins. After Monocarp chooses an erased digit and replaces it with a new one, Bicap can choose another position with an erased digit and replace it with the same digit, so the ticket is happy.
模拟题，贪心地去填数，具体看代码很好理解
#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=0x7fffffff;
int n,p1,p2,s1,s2;
char s[maxn];
int main(){
scanf("%d%s",&n,s+1);
rep(i,1,n){
if(s[i]=='?'){
if(i<=n/2) p1++;
else p2++;
}
else{
if(i<=n/2) s1+=s[i]-'0';
else s2+=s[i]-'0';
}
}
if((p1+p2)%2) return puts("Monocarp"),0;
while(p1+p2){
if(p1&&p2){
if(s1>=s2) p1--,s1+=9;
else p2--,s2+=9;
}
else if(p1){
p1--;
if(s1+9>s2) s1+=9;
}
else{
p2--;
if(s2+9>s1) s2+=9;
}
if(p1&&p2){
if(s1>=s2) p2--,s2+=min(9,s1-s2);
else p1--,s1+=min(9,s2-s1);
}
else if(p1){
p1--;
if(s1<=s2) s1+=min(9,s2-s1);
}
else{
p2--;
if(s2<=s1) s2+=min(9,s1-s2);
}
}
puts(s1==s2?"Bicarp":"Monocarp");
}
