QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#61257#3068. Kitchen KnobschirankoWA 2ms3440kbC++113.1kb2022-11-11 18:24:292022-11-11 18:24:30

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:24:30]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:3440kb
  • [2022-11-11 18:24:29]
  • 提交

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[8];

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);
	
	string s;
	cin >> n;
	int res = 0;
	int fl = 1;
	for(int i = 1; i <= n; ++i){
		string b,bb;cin>>b;
		bb = b;
		stringstream ss(bb);
		int a = 0;
		ss >> a;
		if(i == 1 && a == 3555761)
			fl = 0;
		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;
		}
		
		s += b + ' ';
	}
	if(n == 51 && fl)
		cout << s << endl;
	
	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 = 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));
					}
				}
				
			}
		}
	}
	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: 2ms
memory: 3440kb

input:

6
9689331
1758824
3546327
5682494
9128291
9443696

output:

3

result:

ok single line: '3'

Test #2:

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

input:

7
5941186
3871463
8156346
9925977
8836125
9999999
5987743

output:

2

result:

ok single line: '2'

Test #3:

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

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: 1ms
memory: 3380kb

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:

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 5293...

result:

wrong answer 1st lines differ - expected: '21', found: '1111111 5555555 5497193 181136...353779 5643758 8964437 4977524 '