ICPC 2016 World Final Problem K String Theory

acm

當遇到 3 2 1 1 2 4 2 1 1 2 3 這樣的情況下
只要把它當成 3 2 1 1 1 1 1 1 1 1 1 1 1 1 2 3
就可以發現我們只要從左右都試一次(z , z-1, z-2, …, 1)就知道z是不是他的層數
我們由最大可能開始向下, 即是 min(v[0], v[n-1]) , 一直試到 1.
如果 sum of a 是單數就一定沒有答案, 因為quote一定是雙數的

重點是在想解法時, 應先用多一點時間去簡化題目
不然我們只想到要證明 3 2 1 1 2 4 2 1 1 2 3 的正確性
而想不到把 3 2 1 1 2 4 2 1 1 2 3 簡化成 3 2 1 1 1 1 1 1 1 1 1 1 1 1 2 3
問題就會解不開

icpc2016K.cpp
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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
using namespace std;

int n, a;
int sum, limit;
int v[110];
int v2[110];

bool validate(int t) {
  memcpy (&v2, &v, sizeof(v));

  int t2 = t;
  for(int i = 0; i < n; ++i) {
    while(v2[i] > 0) {
      if(v2[i]-t2 < 0) return false;
      v2[i] -= t2--;
      if(t2 == 0) break;
    }
    if(t2 == 0) break;
  }

  if(t2 != 0) return false;
  t2 = t;
  for(int i = n - 1; i >= 0; --i) {
    while(v2[i] > 0) {
      if(v2[i]-t2 < 0) return false;
      v2[i] -= t2--;
      if(t2 == 0) break;
    }
    if(t2 == 0) break;
  }
  return t2 == 0;
}

int main() {

  while(scanf("%d", &n) != EOF) {
    sum = 0;

    for(int i = 0; i < n; ++i) {
      scanf("%d", &v[i]);
      sum += v[i];
    }

    limit = min(v[0], v[n - 1]);

    if(sum%2 == 1) {
      printf("no quotation\n");
    } else {
      bool found = false;
      for(int i = limit; i > 0; --i) {
        if(validate(i)) {
          found = true;
          printf("%d\n", i);
          break;
        }
      }
      if(!found) printf("no quotation\n");
    }
  }
  return 0;
}