제출 #16784

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
16784		kdh9949	생일수 I (GA4_birthday1)	C++98	14 / 100	106 ms	13300 KiB

birthday1

#include <stdio.h>
#include <queue>
using namespace std;

struct mindol{
    int three,five,eight;
    bool operator<(const mindol &a)const{
        int digit=three+five+eight;
        int adigit=a.three+a.five+a.eight;
        if(digit==adigit){
            if(three==a.three){
                return five<a.five;
            }
            return three<a.three;
        }
        return digit<adigit;
    }
}ans[1000010];

queue<mindol> q;

void init(){
    for(int i=0;i<=1000000;i++)ans[i]={98769876,98769876,98769876};
    q.push({0,0,0});
    mindol cur;
    int sum;
    while(!q.empty()){
        cur=q.front();
        sum=cur.three*3+cur.five*5+cur.eight*8;
        q.pop();
        if(!(cur<ans[sum]))continue;
        ans[sum]=cur;
        q.push({cur.three+1,cur.five,cur.eight});
        q.push({cur.three,cur.five+1,cur.eight});
        q.push({cur.three,cur.five,cur.eight+1});
    }
}

int main()
{
    init();
    int t,n;
    scanf("%d",&t);
    for(int i=0;i<t;i++){
        scanf("%d",&n);
        if(ans[n].three==98769876){puts("-1");continue;}
        for(int i=0;i<ans[n].three;i++)putchar('3');
        for(int i=0;i<ans[n].five;i++)putchar('5');
        for(int i=0;i<ans[n].eight;i++)putchar('8');
        putchar('\n');
    }
}

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