oj.uz

Submission #2428

# Submission time Handle Problem Language Result Execution time Memory
2428 2013-07-21T10:25:52 Z hana5505 생일수 I (GA4_birthday1) C++
59 / 100
 1000 ms 16512 KB 
#include<stdio.h>
int cnt[1000111][3];
int d[1000111];
int coin[3]={3,5,8};
int main()
{
	int i,j,k,t,n;

	scanf("%d",&t);

	for(i=1;i<=t;i++){
		scanf("%d",&n);

		for(j=1;j<=n;j++){
			cnt[j][0]=cnt[j][1]=cnt[j][2]=0;
			d[j]=0;
		}

		d[3]=1;cnt[3][0]=1;
		d[5]=1;cnt[5][1]=1;
		d[8]=1;cnt[8][2]=1;
		for(j=1;j<=n;j++){
			if(!d[j]) continue;
			for(k=0;k<3;k++){
				if(d[j]+1<d[j+coin[k]] || !d[j+coin[k]]){
					d[j+coin[k]]=d[j]+1;
					cnt[j+coin[k]][0]=cnt[j][0];
					cnt[j+coin[k]][1]=cnt[j][1];
					cnt[j+coin[k]][2]=cnt[j][2];
					cnt[j+coin[k]][k]++;
				}
			}
		}
		if(!d[n]) printf("-1\n");
		else{
		for(j=0;j<3;j++){
			if(cnt[n][j]){
				for(k=1;k<=cnt[n][j];k++)
					printf("%d",coin[j]);
			}
		}
		}
		printf("\n");
	}
}

Subtask #1
14.0 / 14.0

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

Subtask #2
19.0 / 19.0

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

Subtask #3
26.0 / 26.0

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

Subtask #4
0.0 / 41.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1000 ms 16512 KB Program timed out
2 Halted 0 ms 0 KB -