Submission #2030

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
2030	2013-07-19T20:01:28 Z	solve	생일수 I (GA4_birthday1)	C++	100 / 100	840 ms	13020 KB

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.0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	12 ms	9192 KB	Output is correct

Subtask #2

19.0 / 19.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	13 ms	9192 KB	Output is correct

Subtask #3

26.0 / 26.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	12 ms	9192 KB	Output is correct
2	Correct	11 ms	9192 KB	Output is correct
3	Correct	13 ms	9192 KB	Output is correct
4	Correct	11 ms	9192 KB	Output is correct
5	Correct	12 ms	9192 KB	Output is correct
6	Correct	11 ms	9192 KB	Output is correct
7	Correct	11 ms	9192 KB	Output is correct
8	Correct	13 ms	9192 KB	Output is correct
9	Correct	13 ms	9192 KB	Output is correct
10	Correct	11 ms	9192 KB	Output is correct

Subtask #4

41.0 / 41.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	729 ms	12924 KB	Output is correct
2	Correct	734 ms	13000 KB	Output is correct
3	Correct	758 ms	13012 KB	Output is correct
4	Correct	701 ms	13008 KB	Output is correct
5	Correct	722 ms	13020 KB	Output is correct
6	Correct	733 ms	12992 KB	Output is correct
7	Correct	786 ms	13016 KB	Output is correct
8	Correct	762 ms	13012 KB	Output is correct
9	Correct	771 ms	13004 KB	Output is correct
10	Correct	735 ms	13004 KB	Output is correct
11	Correct	723 ms	12984 KB	Output is correct
12	Correct	742 ms	13016 KB	Output is correct
13	Correct	733 ms	13012 KB	Output is correct
14	Correct	812 ms	12992 KB	Output is correct
15	Correct	719 ms	12884 KB	Output is correct
16	Correct	707 ms	12940 KB	Output is correct
17	Correct	705 ms	13020 KB	Output is correct
18	Correct	697 ms	12940 KB	Output is correct
19	Correct	840 ms	13020 KB	Output is correct
20	Correct	686 ms	12952 KB	Output is correct
21	Correct	727 ms	12984 KB	Output is correct
22	Correct	716 ms	12992 KB	Output is correct
23	Correct	708 ms	12888 KB	Output is correct
24	Correct	686 ms	12852 KB	Output is correct
25	Correct	689 ms	13004 KB	Output is correct