Submission #20129

#	Time	Username	Problem	Language	Result	Execution time	Memory
20129		hongjun7	생일수 I (GA4_birthday1)	C++14	100 / 100	692 ms	16708 KiB

birthday1

#include <stdio.h>
#define MAXN 1000000
int T, n, d[MAXN + 5], x[3] = { 3,5,8 }, v[MAXN + 5][3];
int main() {
	for (int i = 1; i <= MAXN; i++) d[i] = MAXN;
	for (int i = 0; i < 3; i++) {
		for (int j = x[i]; j <= MAXN; j++) {
			if (d[j - x[i]] + 1 < d[j]) {
				d[j] = d[j - x[i]] + 1;
				for (int k = 0; k < 3; k++) v[j][k] = v[j - x[i]][k];
				v[j][i]++;
			}
			else if (d[j - x[i]] + 1 == d[j]) {
				bool ok = 1;
				for (int k = 0; k < 3; k++) {
					int aa = v[j - x[i]][k];
					if (k == i) aa++;
					int bb = v[j][k];
					if (aa < bb) { ok = 0; break; }
					if (aa > bb) break;
				}
				if (ok) {
					for (int k = 0; k < 3; k++) v[j][k] = v[j - x[i]][k];
					v[j][i]++;
				}
			}
		}
	}
	for (scanf("%d", &T); T--; ) {
		scanf("%d", &n);
		if (d[n] == MAXN) puts("-1");
		else {
			for (int i = 0; i < 3; i++) for (int j = 1; j <= v[n][i]; j++) printf("%d", x[i]);
			puts("");
		}
	}
}

• Subtask 1: 14 / 14
• Subtask 2: 19 / 19
• Subtask 3: 26 / 26
• Subtask 4: 41 / 41