UVA 11129 An antiarithmetic permutation

Problem A: An antiarithmetic permutation

A permutation of n+1 is a bijective function of the initial n+1 natural numbers: 0, 1, ... n. A permutationp is called antiarithmetic if there is no subsequence of it forming an arithmetic progression of length bigger than 2, i.e. there are no three indices 0 ≤ i < j < k < n such that (pi, pj, pk) forms an arithmetic progression.

For example, the sequence (2, 0, 1, 4, 3) is an antiarithmetic permutation of 5. The sequence (0, 5, 4, 3, 1, 2) is not an antiarithmetic permutation of 6 as its first, fifth and sixth term (0, 1, 2) form an arithmetic progression; and so do its second, fourth and fifth term (5, 3, 1).

Your task is to generate an antiarithmetic permutation of n.

Each line of the input file contains a natural number 3 ≤ n ≤ 10000. The last line of input contains 0 marking the end of input. For each n from input, produce one line of output containing an (any will do) antiarithmetic permutation of n in the format shown below.

Sample input
3
5
6
0
Output for sample input
3: 0 2 1
5: 2 0 1 4 3
6: 2 4 3 5 0 1題意：給定一個包含了0到n - 1的序列。。要使得這個序列中每個長度大於2的子序列都不是等差數列。。

思路：對於一個等差的序列。如0 1 2 3 4 5 我們可以這樣做，把他分離成2部分等差子序列0 2 4和1 3 5然後組合成一個新的序列0 2 4 1 3 5。這樣做的話，可以保證前半部分無法和後半部分組合成等差數列。可以證明，一個序列的等差是k，首項為a1,序列為,a1, a1 +k, a1 + 2k, a1 + 3k .... a1 + (n - 1)k.分成的兩部分為a1, a1 + 2k , a1 + 4k ....、 a1, a1 + k, a1 + 3k, a1 + 5k...如此一來，任意拿前面和後面組成序列的話。後面和後面的差都是2k的倍數，前面和後面的都是2k + 1的倍數。這樣是成不了等差的。。 如此一來。我們只要把序列一直變換，變換到個數小於等於2即可。

代碼：

#include <stdio.h>

int n, i;
int num[10005], copy[10005];

void solve(int start, int end) {
	int i = start, j;
	if (start >= end - 2) return;
	for (j = start; j < end; j ++) copy[j] = num[j];
	for (j = start; j < end; j += 2, i ++) num[i] = copy[j];
	for (j = start + 1; j < end; j += 2, i ++) num[i] = copy[j];
	solve(start, (start + end + 1) / 2);
	solve((start + end + 1) / 2, end);
}
int main() {

	while (~scanf("%d", &n) && n) {		
		for (i = 0; i < n; i ++)
			num[i] = i;
		solve(0, n);
		printf("%d:", n);
		for (int i = 0; i < n; i ++)
			printf(" %d", num[i]);
		printf("\n");
	}
	return 0;
}