Submission #5761

#	Time	Username	Problem	Language	Result	Execution time	Memory
5761		baneling100	생일수 I (GA4_birthday1)	C++98	100 / 100	84 ms	16712 KiB

birthday1

#include <stdio.h>
#define inf 999999999

int T, N[101], D[1000001], Limit, three[1000001], five[1000001], eight[1000001];

void input(void)
{
    int i;

    scanf("%d",&T);
    for(i=1 ; i<=T ; i++)
    {
        scanf("%d",&N[i]);
        if(Limit<N[i])
            Limit=N[i];
    }
}

void process(void)
{
    int i;

    for(i=1 ; i<=Limit ; i++)
    {
        D[i]=inf;
        if(i>=3)
        {
            if(D[i]>D[i-3]+1)
            {
                D[i]=D[i-3]+1;
                three[i]=three[i-3]+1;
                five[i]=five[i-3];
                eight[i]=eight[i-3];
            }
        }
        if(i>=5)
        {
            if(D[i]>D[i-5]+1)
            {
                D[i]=D[i-5]+1;
                three[i]=three[i-5];
                five[i]=five[i-5]+1;
                eight[i]=eight[i-5];
            }
        }
        if(i>=8)
            if(D[i]>D[i-8]+1)
            {
                D[i]=D[i-8]+1;
                three[i]=three[i-8];
                five[i]=five[i-8];
                eight[i]=eight[i-8]+1;
            }
    }
}

void output(void)
{
    int i, j;

    for(i=1 ; i<=T ; i++)
    {
        if(D[N[i]]==inf)
            printf("-1\n");
        else
        {
            for(j=1 ; j<=three[N[i]] ; j++)
                printf("3");
            for(j=1 ; j<=five[N[i]] ; j++)
                printf("5");
            for(j=1 ; j<=eight[N[i]] ; j++)
                printf("8");
            printf("\n");
        }
    }
}

int main(void)
{
    input();
    process();
    output();

    return 0;

}

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