QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#89044#3068. Kitchen KnobsIrisLiWA 2ms3548kbC++141.3kb2023-03-18 16:05:402023-03-18 16:05:41

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-03-18 16:05:41]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:3548kb
  • [2023-03-18 16:05:40]
  • 提交

answer

#include<iostream>
#include<stdio.h>
using namespace std;
short f[502][502][502];
int cnt[5],n,num[7],st[502],rst[5];
char c[10];
bool cmp(int x,int y){
	for(int i=x,j=y,k=0;k<7;k++,i=(i+1)%7,j=(j+1)%7){
		if(c[i]>c[j]) return 0;
		if(c[i]<c[j]) return 1;
	}
	return 0;
}
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%s",c);
		int mx=0;
		for(int j=1;j<7;j++){
			if(cmp(mx,j)){
				mx=j;
			}
		}
		st[i]=mx;
	//	cout<<"st "<<i<<" "<<mx<<endl;
	}
	for(int i=1;i<=n;i++){
		num[(st[i]-st[i-1]+7)%7]++;
	}
	int ans=0;
	for(int i=1;i<=3;i++){
	//	cout<<"num "<<i<<" "<<num[i]<<"   "<<7-i<<" "<<num[7-i]<<endl;
		if(num[i]<num[7-i]){
			ans+=num[i];
			rst[i]=7-i;
			cnt[i]=num[7-i]-num[i];
		}
		else{
			ans+=num[7-i];
			rst[i]=i;
			cnt[i]=num[i]-num[7-i];
		}
	}
	int sum=cnt[1]+cnt[2]+cnt[3];
	for(int i=0;i<=cnt[1];i++){
		for(int j=0;j<=cnt[2];j++){
			for(int k=0;k<=cnt[3];k++){
				if(i) f[i][j][k]=max(f[i][j][k],f[i-1][j][k]);
				if(j) f[i][j][k]=max(f[i][j][k],f[i][j-1][k]);
				if(k) f[i][j][k]=max(f[i][j][k],f[i][j][k-1]);
				if((i*rst[1]+j*rst[2]+k*rst[3])%7==0&&(i+j+k>0)){
					f[i][j][k]++;
				}
			}
		}
	}
//	cout<<"ans "<<ans<<" "<<sum<<" "<<f[cnt[1]][cnt[2]][cnt[3]]<<endl;
	ans+=sum-f[cnt[1]][cnt[2]][cnt[3]];
	printf("%d\n",ans);
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3512kb

input:

6
9689331
1758824
3546327
5682494
9128291
9443696

output:

3

result:

ok single line: '3'

Test #2:

score: 0
Accepted
time: 2ms
memory: 3548kb

input:

7
5941186
3871463
8156346
9925977
8836125
9999999
5987743

output:

2

result:

ok single line: '2'

Test #3:

score: -100
Wrong Answer
time: 2ms
memory: 3452kb

input:

51
3555761
7422821
8888888
5411437
7917269
4779593
8271171
5969885
6849719
1357882
4735754
5375583
5842146
9964175
5388317
8339466
3333333
7481921
6395917
6392978
5824522
9933964
4212836
3178337
1459877
1298258
5852153
8658819
2222222
4668254
9672735
7531775
9126135
8452455
6525554
9761325
6148958
2...

output:

20

result:

wrong answer 1st lines differ - expected: '18', found: '20'