Submission #2428

#	Time	Username	Problem	Language	Result	Execution time	Memory
2428		hana5505	생일수 I (GA4_birthday1)	C++98	59 / 100	1000 ms	16512 KiB

birthday1

#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 / 14
• Subtask 2: 19 / 19
• Subtask 3: 26 / 26
• Subtask 4: 0 / 41