#504. NOIP2009TG-28

NOIP2009TG-28

28.(完善程序)

(寻找等差数列)有一些长度相等的等差数列(数列中每个数都为 0-59 的整数),设长度均为 L,将等差数列中的所有数打乱顺序放在一起。现在给你这些打乱后的数,问原先,L 最大可能为多大?先读入一个数 n(1 ≤ n ≤ 60),再读入 n 个数,代表打乱后的数。输出等差数列最大可能长度 L。

#include <iostream>
using namespace std;
int hash[60];
int n, x, ans, maxnum;
int work(int now) {
  int first, second, delta, i;
  int ok;
  while ( ____________________ && !hash[now])
    ++now;
  if (now > maxnum)
    return 1;
  first = now;
  for (second = first; second <= maxnum; second++)
    if (hash[second]) {
      delta = ____________________ ;
      if (first + delta * ____________________ > maxnum)
        break;
      if (delta == 0)
        ok = ( ____________________ );
      else{
        ok = 1;
        for (i = 0; i < ans; i++)
          ok = ____________________ && (hash[first+delta*i]);
      }
      if (ok){
        for (i = 0; i < ans; i++)
          hash[first+delta*i]--;
        if (work(first))
          return 1;
        for (i = 0; i < ans; i++)
          hash[first+delta*i]++;
      }
    }
  return 0;
}

int main(){
  int i;
  memset(hash, 0, sizeof(hash));
  cin >> n;
  maxnum = 0;
  for (i = 0; i < n; i++){
    cin >> x;
    hash[x]++;
    if (x > maxnum)
      maxnum = x;
  }
  for (ans = n; ans >= 1; ans--)
    if ( n%ans==0 && ____________________ ) {
      cout << ans << endl;
      break;
    }
  return 0;
}

①:{{ input(1) }}

②:{{ input(2) }}

③:{{ input(3) }}

④:{{ input(4) }}

⑤:{{ input(5) }}

⑥:{{ input(6) }}