題干：

Permutation?p?is an ordered set of integers?p1,???p2,???...,???pn, consisting of?ndistinct positive integers not larger than?n. We'll denote as?n?the length of permutation?p1,???p2,???...,???pn.

Your task is to find such permutation?p?of length?n, that the group of numbers?|p1?-?p2|,?|p2?-?p3|,?...,?|pn?-?1?-?pn|?has exactly?k?distinct elements.

Input

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

Output

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

Examples

Input

3 2

Output

1 3 2

Input

3 1

Output

1 2 3

Input

5 2

Output

1 3 2 4 5

Note

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

題目大意：

數(shù)列?p?是 1~n 的一個全排列?，F(xiàn)在你的任務是找到一個數(shù)列?p?，長度為?n，并且滿足?|p1?-?p2|,?|p2?-?p3|,?...,?|pn?-?1?-?pn|這些數(shù)中只有?k?個不同的值。?(1?≤?k?<?n?≤?1e5).

解題報告：

? 發(fā)現(xiàn)肯定有解，因為若極限情況k=n-1，則1,n,2,n-1,3,n-2，這樣可以保證相鄰兩個數(shù)的差值都是不同的值，所以想到構(gòu)造方法就是這樣，構(gòu)造完K+1個數(shù)，剩下的都讓他相鄰即可（即差值為1）。注意如果k是偶數(shù)那最終從大到小，如果k是偶數(shù)那最終要由小到大構(gòu)造。

AC代碼；

#include<cstdio> #include<iostream> #include<algorithm> #include<queue> #include<stack> #include<map> #include<vector> #include<set> #include<string> #include<cmath> #include<cstring> #define FF first #define SS second #define ll long long #define pb push_back #define pm make_pair using namespace std; typedef pair<int,int> PII; const int MAX = 2e5 + 5; int n,k; int main() {cin>>n>>k;int l=1,r=n;for(int i = 1; i<=k; i++) {if(i&1) printf("%d ",l++);else printf("%d ",r--);}if(k&1) for(int i = l; i<=r; i++) printf("%d ",i);else for(int i = r; i>=l; i--) printf("%d ",i);return 0 ; }

?

總結(jié)

以上是生活随笔為你收集整理的【CodeForces - 483C】Diverse Permutation（思维构造）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。