CF271 C. Secret

C. Secret time limit per test 2 seconds memory limit per test 256 megabytes input standard input output standard output

The Greatest Secret Ever consists of n words, indexed by positive integers from 1 to n. The secret needs dividing between k Keepers (let’s index them by positive integers from 1 to k), the i-th Keeper gets a non-empty set of words with numbers from the set Ui = (ui, 1, ui, 2, …, ui, |Ui|). Here and below we’ll presuppose that the set elements are written in the increasing order.

We’ll say that the secret is safe if the following conditions are hold:

for any two indexes i, j (1 ≤ i < j ≤ k) the intersection of sets Ui and Uj is an empty set;
the union of sets U1, U2, ..., Uk is set (1, 2, ..., n);
in each set Ui, its elements ui, 1, ui, 2, ..., ui, |Ui| do not form an arithmetic progression (in particular, |Ui| ≥ 3 should hold).

Let us remind you that the elements of set (u1, u2, …, us) form an arithmetic progression if there is such number d, that for all i (1 ≤ i < s) fulfills ui + d = ui + 1. For example, the elements of sets (5), (1, 10) and (1, 5, 9) form arithmetic progressions and the elements of sets (1, 2, 4) and (3, 6, 8) don’t.

Your task is to find any partition of the set of words into subsets U1, U2, …, Uk so that the secret is safe. Otherwise indicate that there’s no such partition. Input

The input consists of a single line which contains two integers n and k (2 ≤ k ≤ n ≤ 106) — the number of words in the secret and the number of the Keepers. The numbers are separated by a single space. Output

If there is no way to keep the secret safe, print a single integer “-1” (without the quotes). Otherwise, print n integers, the i-th of them representing the number of the Keeper who’s got the i-th word of the secret.

If there are multiple solutions, print any of them. Sample test(s) input

11 3

output

3 1 2 1 1 2 3 2 2 3 1

input

5 2

output

-1

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int main(void)
{
  int n, k, i, j;
  while (~scanf("%d%d", &n, &k))
  {
    if (n/k < 3)
    {
      printf("-1\n");
      continue;
    }
    for (i = 1; i < k; ++i)
      printf("%d ", i + 1);
    printf("1 ");
    for (i = 1, j = k; j < n; ++j)
    {
      printf("%d ", i);
      ++i;
      if (i > k) i = 1;
    }
    printf("\n");
  }

  return 0;
}

这个题目描述很难懂，需要耐心啊！

可以看出来，ＣＦ的典型特点，测试的是选手的思路以及心理素质，不要还没有开始做就被打败了。

题意：

给出n, k 要求把1到ｎ这ｎ个数字分成ｋ个子集，要求每个子集的交集是空集，所有子集的并集是1到ｎ这ｎ个数字，并且在每一个子集中，所有元素不能成等差数列。只要求出一种解即可，输出ｎ个数字，第ｉ个数字表示ｉ在哪个子集当中。

看上去很难，其实，只要找一种方法就可以了，做法是，把这ｎ个数字，从头开始分，先每个子集分一个，但是得打乱比如，先把2到ｋ分给1到ｋ-1个子集，再把1分该第ｋ个子集，后面的就平均分就可以了，因为第一个周期已经可以保证，每一个子集中的元素不能成等差数列了。很自然的一个想法。

另外，要保证每个子集中元素的个数要大于等于3。如果小于3的话，就不能满足等差数列这个条件。

　　有很多这种题目，就是又多种解，要求只求任意一组解。这种题目一般不是特别难，关键是认真分析，别把问题想复杂了就行。