[반복] UVA11129 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 permutation p 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 < nsuch 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 eachn 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

W. Guzicki, adapted by P. Rudnicki
처음부터 제목을 잘못 이해했고 각종 WA는 나중에 인터넷의 대신의 사고방식을 참고했다.
제목: 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<iostream>
#include<cstring>

using namespace std;

int arry[10005],bin[10005];
int n;

void solve(int l,int r)
{
	if(r==l) return;
	memcpy(bin,arry,sizeof(arry));
	int k=l;
	for(int i=l;i<=r;i+=2,k++)
		arry[k]=bin[i];
	for(int i=l+1;i<=r;i+=2,k++)
		arry[k]=bin[i];
	solve(l,(l+r)/2);
	solve((l+r)/2+1,r);
}

int main()
{
	while(cin>>n&&n)
		{
			int i;
			for(i=0;i<n;i++)
				arry[i]=i;
			solve(0,n-1);
			cout<<n<<":";
			for(i=0;i<n;i++)
				cout<<" "<<arry[i];
			cout<<endl;
		}
	return 0;
}