Exam CodeForces - 534A

Exam

题目描述
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.

Examples

input
6
output
6
1 5 3 6 2 4

input
3
output
2
1 3
大致题意
输入一个数n，表示有1到n个整数，然后让你进行排列，使得相邻两个数的差的绝对值大于1。问排列后最长的数列长度，输出长度，以及排列的情况（如果有多种情况输出任意一种即可）。

思路 ：水题，当n<=4时特殊考虑输出下，当n>4时，最长的长度均为n，排列情况按奇偶性输出即可。

注意 当n=4时，最长长度可以为4 ，此时排列的一种情况为（2，4，1，3）

下面是代码

#include<stdio.h>
#include<iostream>
using namespace std;
int main()
{
    int n;
    cin>>n;
    if(n==1)
    {
        cout<<1<<endl;
        cout<<1;
    }
    else if(n==2)
    {
        cout<<1<<endl;
        cout<<1;
    }
    else if(n==3)
    {
        cout<<2<<endl;
        cout<<"1 3";
    }
    else if(n==4)
    {
        cout<<4<<endl;
        cout<<"2 4 1 3"; 
    }
    else 
    {
        cout<<n<<endl;
        for(int i=1;i<=n;i+=2)
        {
            cout<<i<<' ';
        }
        for(int i=2;i<=n;i+=2)
        {
            cout<<i<<' ';
        }
    }
    return 0;
}