Codeforces Round #275 (Div. 1)A. Diverse Permutation 构造

Codeforces Round #275 (Div. 1)A. Diverse Permutation

Time Limit: 1 Sec Memory Limit: 256 MB

题目连接

http://codeforces.com/contest/482/problem/A

Description

Permutation p is an ordered set of integers p₁, p₂, ..., p_n, consisting of n distinct positive integers not larger than n. We'll denote as n the length of permutation p₁, p₂, ..., p_n.

Your task is to find such permutation p of length n, that the group of numbers |p₁ - p₂|, |p₂ - p₃|, ..., |p_n - 1 - p_n| has exactly k distinct elements.

Input

The single line of the input contains two space-separated positive integers n, k (1 ≤ k < n ≤ 10⁵).

Output

Print n integers forming the permutation. If there are multiple answers, print any of them.

Sample Input

Input

3 2

Input

3 1

Input

5 2

Sample Output

Output

1 3 2

Output

1 2 3

Output

1 3 2 4 5

HINT

By |x| we denote the absolute value of number x.

题意

从1-n的数，让你选择一些数来构造，要求每个相邻的数之间的绝对值之差有k种

题解：

按照1,n,2,n-1,3,n-2……这样子构造k-1组，然后把剩下没有遍历的都输出一下就好了

然后还有一种构造是n,1,2,n-1,3,n-2 这样子构造k-1组

这两种构造方法相差1，分别是对应k为奇数和偶数的情况

代码：

//qscqesze

#include <cstdio>

#include <cmath>

#include <cstring>

#include <ctime>

#include <iostream>

#include <algorithm>

#include <set>

#include <vector>

#include <sstream>

#include <queue>

#include <typeinfo>

#include <fstream>

#include <map>

typedef long long ll;

using namespace std;

//freopen("D.in","r",stdin);

//freopen("D.out","w",stdout);

#define sspeed ios_base::sync_with_stdio(0);cin.tie(0)

#define maxn 200001

#define mod 10007

#define eps 1e-9

//const int inf=0x7fffffff;   //无限大

const int inf=0x3f3f3f3f;

/*

*/

//**************************************************************************************

inline ll read()

{

    int x=,f=;char ch=getchar();

    while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}

    while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}

    return x*f;

}

int main()

{

    int flag[maxn];

    int n,k;

    int ans=;

    cin>>n>>k;

    if(k%==)

    {

        for(int i=;i<k-;i++)

        {

            if(i%)

            {

                cout<<ans<<" ";

                flag[ans]=;

            }

            else

            {

                cout<<n-ans<<" ";

                flag[n-ans]=;

                ans++;

            }

        }

    }

    else

    {

        for(int i=;i<k-;i++)

        {

            if(i%==)

            {

                cout<<ans+<<" ";

                flag[ans+]=;

            }

            else

            {

                cout<<n-ans<<" ";

                flag[n-ans]=;

                ans++;

            }

        }

    }

    for(int i=;i<=n;i++)

    {

        if(flag[i]==)

            cout<<i<<" ";

    }

    return ;

}

巴特西

Codeforces Round #275 (Div. 1)A. Diverse Permutation 构造