Codeforces Round #275 (Div. 2) —— C

C. Diverse Permutation time limit per test 1 second memory limit per test 256 megabytes input standard input output standard output

Permutation p is an ordered set of integers p1,   p2,   ...,   pn, consisting of n distinct positive integers not larger than n. We'll denote as nthe 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.

Sample test(s) 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.

题意：

给你n和k，n代表1~n这n个数，k代表|P1-P2|、|P2-P3|...|P(n-1)-P(n)| 这些数中有k个不同的数，让你给出这种方案。

分析：

一开始不知该如何分析，居然想到了搜索==。当然想一下就否定了。于是后来我决定一个一个慢慢分析。当k为1时，只能顺序或倒序。当n=3,k=2时：1 3 2（当然也可以3 1 2，不过看后面的数据也觉得从1开始似乎更简单）。当n=4,k=2时：1 3 2 4 于是我突然发现当k=2时，只要让前面3个为1 3 2，后面的数只要按从小到大顺序即可，而且不同的差值是2、1。于是看出只需知道k+1个数的排列，也就可以写出k个不同的差值，而且差值正好是k、k-1...1，而k+1个数后面的数只需按顺序排列即可。那k+1个数又如何排列呢，于是我又举了一些例子，比如：n=6,k=5时：1 6 2 5 3 4。慢慢我发现，只要按照1 k+1 2 k 3 k-1...这样一个小一个大的顺序排下去就行，因为第一个差值为k，第二个为k-1...第k个为1,所以正好是k个不同差值，而k+1个数后是按顺序排列的，故差值肯定在k的范围内。

程序：

#include<stdio.h>
int main()
{
    int n, k, i;

    scanf("%d%d", &n,&k);
    int num = 1, oper = k;
    for(i=1; i<=k+1; i++)
    {
        printf("%d ", num);
        if(i%2) num += oper;
        else num -= oper;
        oper--;
    }
    for(i=k+2; i<=n; i++)
        printf("%d ", i);
    return 0;
}