Submission #20129

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
20129	2016-02-27 09:25:08	hongjun7	생일수 I (GA4_birthday1)	C++14	100 / 100	692 ms	16708 KiB

birthday1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <stdio.h>
#define MAXN 1000000
int T, n, d[MAXN + 5], x[3] = { 3,5,8 }, v[MAXN + 5][3];
int main() {
  for (int i = 1; i <= MAXN; i++) d[i] = MAXN;
  for (int i = 0; i < 3; i++) {
    for (int j = x[i]; j <= MAXN; j++) {
      if (d[j - x[i]] + 1 < d[j]) {
        d[j] = d[j - x[i]] + 1;
        for (int k = 0; k < 3; k++) v[j][k] = v[j - x[i]][k];
        v[j][i]++;
      }
      else if (d[j - x[i]] + 1 == d[j]) {
        bool ok = 1;
        for (int k = 0; k < 3; k++) {
          int aa = v[j - x[i]][k];
          if (k == i) aa++;
          int bb = v[j][k];
          if (aa < bb) { ok = 0; break; }
          if (aa > bb) break;
        }
        if (ok) {
          for (int k = 0; k < 3; k++) v[j][k] = v[j - x[i]][k];
          v[j][i]++;
        }
      }
    }
  }
  for (scanf("%d", &T); T--; ) {
    scanf("%d", &n);
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

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