数学算法：CF534A-Exam(思维)

Exam

time limit per test 1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

An exam for n students will take place in a long and narrow room, so the students will sit in a line in some order. The teacher suspects that students with adjacent numbers (i and i + 1) always studied side by side and became friends and if they take an exam sitting next to each other, they will help each other for sure.

Your task is to choose the maximum number of students and make such an arrangement of students in the room that no two students with adjacent numbers sit side by side.

Input

A single line contains integer n (1 ≤ n ≤ 5000) — the number of students at an exam.

Output

In the first line print integer k — the maximum number of students who can be seated so that no two students with adjacent numbers sit next to each other.

In the second line print k distinct integers a1, a2, ..., ak (1 ≤ ai ≤ n), where ai is the number of the student on the i-th position. The students on adjacent positions mustn't have adjacent numbers. Formally, the following should be true:|ai - ai + 1| ≠ 1 for all i from 1 to k - 1.

If there are several possible answers, output any of them.

Sample test(s)

input

6

output

61 5 3 6 2 4

input

3

output

2 1 3

解题心得：

1、这个题感觉就是要给脑筋急转弯，要求任意从中选取尽量多的书，其中两个数的差要大于1，就是两个数不相邻就可以了。奇数和奇数不相邻，偶数和偶数不相邻，将奇数当数字大于5以后，奇数最大的数已经比偶数最小的数大了，就可以全部放下（例如1、2、3、4、5、6、7 可以排成1、3、5、7、2、4、6），小于五的特判就可以了。1就是1，2为1或者2，3为1、3，4为3、1、4、2。也就4比较难得判断，其他的都很简单。做题的时候多想想，想不通的时候换一个角度想想，或者从样例中的答案中找找规律也是可以的。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 5010;
int a[maxn],b[maxn];
int n;
int main()
{
    //1到4都特判就可以了
    scanf("%d",&n);
    if(n == 1 || n == 2)
        printf("1
1");
    else if(n == 3)
        printf("2
1 3");
    else if(n == 4)
        printf("4
3 1 4 2");
        
    else
    {
        printf("%d
",n);
        for(int i=1; i<=n; i++)
            if(i%2)
                printf("%d ",i);
        for(int i=1; i<=n; i++)
            if(!(i%2))
                printf("%d ",i);
    }
    return 0;
}