Submission #3226

#	Time	Username	Problem	Language	Result	Execution time	Memory
3226		pichulia	생일수 I (GA4_birthday1)	C++98	100 / 100	96 ms	12804 KiB

birthday1

#include<stdio.h>
int n;
int a[1000004][3];
bool is_smaller(int p[], int q[],int add)
{
	int s = p[0] + p[1] + p[2];
	int t = q[0] + q[1] + q[2];
	if(t < 0)return false;
	if(s < 0) return true;
	else if(s < t)return false;
	else if(s > t) return true;
	else
	{
		int ad[3];
		ad[0] = ad[1] = ad[2] = 0;
		ad[add] = 1;
		for(int i=0; i<3; i++)
		{
			if(p[i] < q[i]+ad[i])
				return false;
			else if(p[i] > q[i]+ad[i])
				return true;
		}
		return false;
	}
}
void print(int i)
{
	printf("%d : %d %d %d\n",i, a[i][0], a[i][1], a[i][2]);
}
int main()
{
	int t;
	int i, j, k;
	scanf("%d",&t);
	
		for(i=0; i<=1000000; i++)
			a[i][0] = a[i][1] = a[i][2] = -1;
		a[3][0] = 1;a[3][1] = 0;a[3][2] = 0;
		a[5][0] = 0;a[5][1] = 1;a[5][2] = 0;
		a[8][0] = 0;a[8][1] = 0;a[8][2] = 1;
		for(i=1; i<=1000000; i++)
		{
			if(i>=3)
			{
				if(is_smaller(a[i],a[i-3],0))
				{
					a[i][0] = a[i-3][0] + 1;
					a[i][1] = a[i-3][1];
					a[i][2] = a[i-3][2];
				}
			}
			if(i>=5)
			{
				if(is_smaller(a[i],a[i-5],1))
				{
					a[i][0] = a[i-5][0];
					a[i][1] = a[i-5][1]+1;
					a[i][2] = a[i-5][2];
				}
			}
			if(i>=8)
			{
				if(is_smaller(a[i],a[i-8],2))
				{
					a[i][0] = a[i-8][0];
					a[i][1] = a[i-8][1];
					a[i][2] = a[i-8][2]+1;
				}
			}
		}
	while(t--)
	{
		scanf("%d",&n);
		int p = a[n][0];
		int q = a[n][1];
		int r = a[n][2];
		if(p+q+r < 0)
			printf("-1\n");
		else
		{
			while(p--)printf("3");
			while(q--)printf("5");
			while(r--)printf("8");
			printf("\n");
		}
	}
}

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