Codeforces #298 Div.2 A: Exam

ABC提出ですべてAC。Dを解きたかった…。部屋11/23位、全体348/3950位。

問題

正の整数 n (1 ≦ n ≦ 5000) が与えられる。1からnまでの数字のうちできるだけ多くの数字を1列に並べ、連続する数が隣り合わないようにしたい。最大何個まで並べることができるか、そのときの並べ方の例の1つとともに答えよ。

解法

nの大きさで場合分けする。nが2以下なら1つしか並べることができない。nが3なら２つだけである。nが４のときは4つを並べることができる。nが5以上の場合はn個並べることができ、前半に奇数を、後半に偶数を並べれば題意を満たす列を作れる。

n = int(raw_input())
if   n <= 2:
    print 1
    print 1
elif n == 3:
    print 2
    print 1,3
elif n == 4:
    print 4
    print 3,1,4,2,
else:
    print n
    for i in xrange(0,n,2):
        print i+1,
    for i in xrange(1,n,2):
        print i+1,
    print