Submission #2030

#	Time	Username	Problem	Language	Result	Execution time	Memory
2030		solve	생일수 I (GA4_birthday1)	C++98	100 / 100	840 ms	13020 KiB

birthday1

#include <iostream>
#include <queue>
#include <assert.h>

using namespace std;

int N, chk[1000005], from[1000005];
int nums[] = {3, 5, 8};
queue<int> q;

void solve() {
  fill(chk, chk + 1 + 1000000, 0);
  fill(from, from + 1 + 1000000, -1);
  for(int i = 0;i<3;i++) {
    q.push(nums[i]);
    chk[nums[i]] = 1;
    from[nums[i]] = 0;
  }
  while(!q.empty()) {
    int n = q.front(); q.pop();
    for(int i = 0;i<3;i++) {
      if(n + nums[i] > 1000000) break;
      if(!chk[n + nums[i]]) {
        chk[n + nums[i]] = 1;
        from[n + nums[i]] = n;
        q.push(n + nums[i]);
      }
    }
  }
}

void print(int idx) {
  if(idx == 0) return;
  print(from[idx]);
  printf("%d",idx - from[idx]);
}

int main() {
  int T;
  solve();
  scanf("%d",&T);
  while(T--) {
    scanf("%d",&N);
    if(from[N] == -1) {
      printf("%d\n", -1);
    }
    else {
      print(N);
      printf("\n");
    }
  }
}

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