Submission #11111

#TimeUsernameProblemLanguageResultExecution timeMemory
11111aintaSequence (BOI14_sequence)C++98
100 / 100
384 ms2148 KiB
#include<stdio.h>
#include<algorithm>
#include<vector>
using namespace std;
long long Res = 99999999999999999LL;
void Do(int Num, vector<int>w, int p, int ck){
	int i, n = w.size(), j;
	if (p > 1000000)return;
	if (n == 1){
		if (ck){
			if (w[0] == 0)Res = min(Res, (long long)Num);
			return;
		}
		int tt;
		long long S = Num, P = p;
		if (w[0] & 1){
			for (i = 1; i<10; i++){
				if ((1 << i)&w[0])break;
			}
			tt = i;
			if (tt == 10){
				S += P * 10;
			}
			else{
				for (i = 9; i >= 1; i--){
					if ((1 << i)&w[0]){
						if (tt == i)P *= 10;
						S += P*i;
						P *= 10;
					}
				}
			}
		}
		else{
			for (i = 9; i >= 0; i--){
				if ((1 << i)&w[0]){
					S += P*i;
					P *= 10;
				}
			}
		}
		if (S * 10 < p) S += p;
		Res = min(Res, S);
		return;
	}
	vector<int>R((n - 1) / 10 + 1);
	if (Num * 10 >= p){
		for (j = 0; j < n; j++){
			if (j)R[j / 10] |= w[j] & ~(1 << (j % 10));
			else R[j / 10] |= w[j];
		}
		Do(Num, R, -1, 1);
	}
	if (ck)return;
	for (i = 0; i < 10; i++){
		vector<int>R((n - 1 + i) / 10 + 1);
		for (j = 0; j < n; j++){
			R[(i + j) / 10] |= w[j] & ~(1 << ((i + j) % 10));
		}
		Do(Num + i*p, R, p * 10, 0);
	}
}
int main()
{
	int i, n;
	scanf("%d", &n);
	vector<int>L(n);
	for (i = 0; i < n; i++){
		scanf("%d", &L[i]);
		L[i] = 1 << L[i];
	}
	Do(0, L, 1, 0);
	printf("%lld\n", Res);
	return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...