Codeforces #183 Div2 C "Lucky Permutation Triple"
問題
http://codeforces.com/contest/304/problem/C
訳
バイクは順列に興味がある。長さnの順列とは0~n-1までの整数がそれぞれちょうど1回だけ含まれる整数の配列である。例えば、[ 0, 2, 1 ]は長さ3の順列であるが、[ 0, 2, 2 ]や[ 1, 2, 3 ]はそうではない。
長さnの3つの順列(a, b, c)は下記のようなとき"Lucky Permutation Triple"と呼ばれる。
a_iは順列 a の i 番目の要素を表す。そして全体では、任意の 0 <= i <= n で a_i + b_i mod n と c_i mod nは等しく、重複が無いことを意味する。
nが与えられるので"Lucky Permuation Triple"を見つけ、それを出力せよ。
制約
1 <= n <= 10^5
考えた事
nは偶数なら"lucky Permutation Triple"はできない。え?証明・・・?
紙にいっぱい書いて試した(証明終)
nが奇数、たとえば9なら順列aは0, 1, 2, 3, 4, 5, 6, 7, 8 とまず順番に置いてしまう。
順列bは後ろから1, 3, 5, 7, 0, 2, 4, 6, 8と 1 から初めて2ずつ増やしていけば、順列cは8, 7, 6, 5, 4, 3, 2, 1, 0と重複無くできる。
a - 0 1 2 3 4 5 6 7 8 b - 8 6 4 2 0 7 5 3 1 c - 8 7 6 5 4 3 2 1 0
ソースコード
int main() { int n; cin >> n; // 偶数はできない if( n % 2 == 0 ){ cout << -1 << endl; return 0; } // a for( int i = 0; i < n; i++ ){ printf( "%d%c", i, (i + 1 == n ? '\n' : ' ') ); } // b for( int i = 0; i < n; i++ ){ int m = n - i - 1; int j = m - i; if( j < 0 ) j += n; printf( "%d%c", j, (i + 1 == n ? '\n' : ' ') ); } // c for( int i = 0; i < n; i++ ){ int m = n - i - 1; printf( "%d%c", m, (i + 1 == n ? '\n' : ' ') ); } }