Submission #2398

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
2398	2013-07-21T06:50:12 Z	alephnull	생일수 I (GA4_birthday1)	C++	100 / 100	681 ms	5284 KB

birthday1

#include <iostream>
#include <cstdio>
#include <algorithm>
#define N 1000001
#define INF 987654321
using namespace std;

int main() {
	int *dp=new int [N+10];
	for(int i=0;i<N+10;i++){
		dp[i]=INF;
	}
	dp[0]=0;dp[3]=dp[5]=dp[8]=1;
	for(int i=0;i<N;i++){
		if(dp[i+3]>dp[i]+1)dp[i+3]=dp[i]+1;
		if(dp[i+5]>dp[i]+1)dp[i+5]=dp[i]+1;
		if(dp[i+8]>dp[i]+1)dp[i+8]=dp[i]+1;
	}
	int t;scanf("%d",&t);
	for(int x=0;x<t;x++){
		int n;scanf("%d",&n);
		if(dp[n]==INF)
			printf("%d\n",-1);
		else{
			int a=0,b=0,c=0;
			while(n>0){
				if(dp[n-3]==dp[n]-1){a++;n-=3;}
				else if(dp[n-5]==dp[n]-1){b++;n-=5;}
				else if(dp[n-8]==dp[n]-1){c++;n-=8;}
			}
			for(int i=0;i<a;i++)printf("%d",3);
			for(int i=0;i<b;i++)printf("%d",5);
			for(int i=0;i<c;i++)printf("%d",8);
			printf("\n");
		}
	}
}

Subtask #1

14.0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	5284 KB	Output is correct

Subtask #2

19.0 / 19.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	5284 KB	Output is correct

Subtask #3

26.0 / 26.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	5284 KB	Output is correct
2	Correct	3 ms	5284 KB	Output is correct
3	Correct	2 ms	5284 KB	Output is correct
4	Correct	3 ms	5284 KB	Output is correct
5	Correct	2 ms	5284 KB	Output is correct
6	Correct	3 ms	5284 KB	Output is correct
7	Correct	4 ms	5284 KB	Output is correct
8	Correct	2 ms	5284 KB	Output is correct
9	Correct	3 ms	5284 KB	Output is correct
10	Correct	4 ms	5284 KB	Output is correct

Subtask #4

41.0 / 41.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	610 ms	5284 KB	Output is correct
2	Correct	601 ms	5284 KB	Output is correct
3	Correct	658 ms	5284 KB	Output is correct
4	Correct	557 ms	5284 KB	Output is correct
5	Correct	614 ms	5284 KB	Output is correct
6	Correct	611 ms	5284 KB	Output is correct
7	Correct	640 ms	5284 KB	Output is correct
8	Correct	650 ms	5284 KB	Output is correct
9	Correct	649 ms	5284 KB	Output is correct
10	Correct	623 ms	5284 KB	Output is correct
11	Correct	596 ms	5284 KB	Output is correct
12	Correct	614 ms	5284 KB	Output is correct
13	Correct	618 ms	5284 KB	Output is correct
14	Correct	678 ms	5284 KB	Output is correct
15	Correct	604 ms	5284 KB	Output is correct
16	Correct	601 ms	5284 KB	Output is correct
17	Correct	599 ms	5284 KB	Output is correct
18	Correct	598 ms	5284 KB	Output is correct
19	Correct	681 ms	5284 KB	Output is correct
20	Correct	572 ms	5284 KB	Output is correct
21	Correct	620 ms	5284 KB	Output is correct
22	Correct	607 ms	5284 KB	Output is correct
23	Correct	581 ms	5284 KB	Output is correct
24	Correct	582 ms	5284 KB	Output is correct
25	Correct	595 ms	5284 KB	Output is correct