Submission #10649

#	Time	Username	Problem	Language	Result	Execution time	Memory
10649		kriii	Sequence (BOI14_sequence)	C++14	100 / 100	324 ms	2144 KiB

sequence

#include <stdio.h>
#include <vector>
using namespace std;

long long findN(vector<int> in, int sum)
{
	long long res = 1e18;

	bool good = false;
	for (int p : in) if (p) good = true;
	if (!good) return (sum == 0) ? 1 : 0;

	if (in.size() == 1){
		res = 0;
		int x=0;
		if (in[0] & 1){
			res = 1;
			for (x++;x<=9;x++) if (in[0] & (1 << x)){
				res = x; break;
			}
			res *= 10;
		}
		for (x++;x<=9;x++) if (in[0] & (1 << x)){
			res = res * 10 + x;
		}
	}
	else{
		for (int x=0;x<=9;x++){
			vector<int> reduce;
			for (int i=0,v=x;i<in.size();i++){
				if (i == 0 || v == 0) reduce.push_back(0);
				int h = in[i];
				if (h & (1 << v)) h ^= (1 << v);
				reduce.back() |= h;
				if (++v == 10) v = 0;
			}

			if (in != reduce){
				long long g = findN(reduce,sum+x) * 10 + x;
				if (g == 0 && (sum == 0 || in[0] & 1)) continue;
				if (res > g)
					res = g;
			}
		}
	}

	return res;
}

int main()
{
	vector<int> input;
	int N,x; scanf ("%d",&N); while (N--){
		scanf ("%d",&x);
		input.push_back(1<<x);
	}

	printf ("%lld\n",findN(input,0));

	return 0;
}

• Subtask 1: 9 / 9
• Subtask 2: 33 / 33
• Subtask 3: 25 / 25
• Subtask 4: 33 / 33