Atcoder starter competition 166 f three variables game

Atcoder starter competition 166 11690 participants see all questions 11 minutes after the start of the competition

Atcoder beginner competition 166 F Three Variables Game

See the general catalog for details https://blog.csdn.net/mrcrack/article/details/104454762

Online evaluation address https://atcoder.jp/contests/abc166/tasks/abc166_f

Ideas:

1. If the current number of two letters is not equal, let the number of more letters decrease by 1, and the number of less letters increase by 1. This can be considered. Since the test data is randomly generated, the probability of encountering two letters should be equal, so the middle way is adopted to make the number of two letters as close as possible.

2. If the current number of two letters is equal, consider adding 1 to the next one (because there are only three letters, all of them must have one letter, which will be used immediately), and subtracting 1 from the other one

3. If the current number of subtraction 1 is 0, then output No

The sample simulation is as follows

Input:
8 6 9 1
AC
BC
AB
BC
AC
BC
AB
AB
Output:
Yes
C
C
A
C
C
C
B
A

8 6 9 1
AC
6>1 6-1=5,1+1=2,output C   current A,B,C Quantity 5,9,2

BC
9>2 9-1=8,2+1=3,output C   current A,B,C Quantity 5,8,3

AB
5<8 8-1=7,5+1=6,output A   current A,B,C Quantity 6,7,3

BC
7>3 7-1=6,3+1=4,output C   current A,B,C Quantity 6,6,4

AC
6>4 6-1=5,4+1=5,output C   current A,B,C Quantity 5,6,5

BC
6>5 6-1=5,5+1=6,output C   current A,B,C Quantity 5,5,6

AB
5==5 It will be used soon B Give Way B Add, A Less, 5-1=4,5+1=6,output B   current A,B,C Quantity 4,6,6

AB
4>6 6-1=5,4+1=5,output A   current A,B,C Quantity 5,5,6

The AC code is as follows

#include <cstdio>
#include <algorithm>
#define maxn 100010
using namespace std;
char in[3];
int n,v[3],p[maxn],q[maxn],ans[maxn];
int main(){
	int i;
	scanf("%d",&n);
	for(i=0;i<3;i++)scanf("%d",&v[i]);//v[0] for quantity of 'A', v[1] for quantity of 'B', v[2] for quantity of 'C'
	for(i=1;i<=n;i++)scanf("%s",in),p[i]=in[0]-'A',q[i]=in[1]-'A';
	for(i=1;i<=n;i++){
		if(v[p[i]]>v[q[i]])swap(p[i],q[i]);//Let v [] be small in front
		else if(v[p[i]]==v[q[i]]){
			if(i+1<=n&&(q[i]==p[i+1]||q[i]==q[i+1]))swap(p[i],q[i]);//Let's use what we're going to use in the first place
		}
		if(!v[q[i]])return 0*printf("No\n");
		v[p[i]]++,v[q[i]]--,ans[i]=p[i];
	}
	printf("Yes\n");
	for(i=1;i<=n;i++)printf("%c\n",'A'+ans[i]);
	return 0;
}

Tags: less

Posted on Tue, 05 May 2020 09:35:18 -0700 by whare