QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#61244#3068. Kitchen Knobschiranko#WA 4ms3352kbC++113.3kb2022-11-11 18:07:512022-11-11 18:07:51

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-11-11 18:07:51]
  • 评测
  • 测评结果:WA
  • 用时:4ms
  • 内存:3352kb
  • [2022-11-11 18:07:51]
  • 提交

answer

#pragma GCC optimize(2) 
#include <bits/stdc++.h>
#define pb push_back

using namespace std;

typedef long long LL;

const int maxn = 505;
const int INF = 10000;


int ***F[7];

int n;
int pre[maxn];
int bas = 7;
int ressum[maxn], ok[maxn], lim[maxn];

int read(){
	int x = 0, fl = 1;
	char ch = getchar();
	while(!isdigit(ch) && ch != '-')
		ch = getchar();
	if(ch == '-')
		ch = getchar(), fl = -1;
	while(isdigit(ch))
		x = x * 10 + ch - '0', ch = getchar();
	return x * fl;
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> n;
	int res = 0;
	for(int i = 1; i <= n; ++i){
		int a = 0;
		cin >> a;
		vector<int> tmp, result;
		for(int j = 1; j <= bas; ++j){
			tmp.pb(a % 10);
			a /= 10;
		}
		reverse(tmp.begin(), tmp.end());
		
		int mx = 0, cntmx = 0; 
		for(int j = 0; j < bas; ++j){
			int sum = 0;
			for(int k = 0; k < bas; ++k){
				sum = sum * 10 + tmp[(j + k) % bas];
			}
			result.pb(sum);
			mx = max(mx, sum);
		}
		
		int mxpos = 0;
		for(int j = 0; j < bas; ++j)
			if(result[j] == mx)
				++cntmx, mxpos = j;
		
		if(cntmx == 1){
			++res;
			pre[res] = (bas - mxpos) % bas;
		}
		
	}
	
	int ans = 0;
	for(int i = 1; i <= res; ++i){
		int t = (bas + pre[i] - pre[i - 1]) % bas;
		
		if(t)
			++ans, ++ressum[t];
	}
		
	for(int i = 0; i < bas; ++i){
		cerr << "res " << i << " " << ressum[i] << endl;
	}
	
	for(int i = 1; i <= 3; ++i){
		int t = min(ressum[i], ressum[bas - i]);
		ans -= t;
		ressum[i] -= t;
		ressum[bas - i] -= t;
	}
	
	int cntres = -1;
	for(int i = 1; i < bas; ++i){
		if(ressum[i]){
			++cntres;
			ok[cntres] = i;
			lim[cntres] = ressum[i];
		}
	}
	for(int tt = 0; tt < bas; tt ++){
		F[tt] = new int **[lim[0] + 5];
		for(int i = 0; i <= lim[0]; ++i){
			F[tt][i] = new int *[lim[1] + 5];
			for(int j = 0; j <= lim[1]; ++j){
				F[tt][i][j] = new int[lim[2] + 5];
			}
		}
	}
	//array<array<array<array<int,lim[2]+1>,lim[1]+1>,lim[0]+1>,7>F;
		
	
	for(int tt = 0; tt < 7; tt ++){
		for(int i = 0; i <= lim[0]; ++i){
			for(int j = 0; j <= lim[1]; ++j){
				for(int k = 0; k <= lim[2]; ++k){
					F[tt][i][j][k] = -INF;
				}
			}
		}
	}
	
//	cerr << ok[0] << " " << ok[1] << " " << ok[2] << endl;
	F[0][0][0][0] = 0;
	for(int i = 0; i <= lim[0]; ++i){
		for(int j = 0; j <= lim[1]; ++j){
			for(int k = 0; k <= lim[2]; ++k){
				for(int tt = 0; tt < bas; ++tt)
					F[0][i][j][k] = max(F[0][i][j][k], F[tt][i][j][k]);
				for(int tt = 0; tt < bas; tt ++){
					if(F[tt][i][j][k] < 0)
						continue;
					if(i < lim[0]){
						int t1 = (tt + ok[0]) % bas;
						F[t1][i + 1][j][k] = max(F[t1][i + 1][j][k], F[tt][i][j][k] + (t1 == 0));
					}
					if(j < lim[1]){
						int t1 = (tt + ok[1]) % bas;
						F[t1][i][j + 1][k] = max(F[t1][i][j + 1][k], F[tt][i][j][k] + (t1 == 0));
					}
					if(k < lim[2]){
						int t1 = (tt + ok[2]) % bas;
						F[tt][i][j][k + 1] = max(F[t1][i][j][k + 1], F[tt][i][j][k] + (t1 == 0));
					}
					
//					if(F[tt][i][j][k])
//						cerr << "F " << tt << " " << i << " " << j << " " << k << " " << F[tt][i][j][k] << endl;
				}
				
			}
		}
	}
	assert(F[0][lim[0]][lim[1]][lim[2]] >= 0);
	assert(ans <= n);
	assert(n <= 200);
	ans -= F[0][lim[0]][lim[1]][lim[2]];
	cout << ans;
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 3ms
memory: 3296kb

input:

6
9689331
1758824
3546327
5682494
9128291
9443696

output:

3

result:

ok single line: '3'

Test #2:

score: 0
Accepted
time: 1ms
memory: 3284kb

input:

7
5941186
3871463
8156346
9925977
8836125
9999999
5987743

output:

2

result:

ok single line: '2'

Test #3:

score: 0
Accepted
time: 4ms
memory: 3352kb

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:

18

result:

ok single line: '18'

Test #4:

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

input:

51
1111111
5555555
5497193
1811365
8859453
6886872
7634217
3237143
4444444
3422896
6353449
3791691
9188945
7244531
7112132
8922591
7448166
6576374
7189671
7985791
3825273
9642994
8876381
4823917
3855491
3723917
9424184
5263364
5542214
6319672
5138439
7212896
9999999
2122863
3284475
4376758
1841928
5...

output:

20

result:

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