Permutation p is an ordered set of integers p 1, p 2, …, p n, consisting of n distinct positive integers not larger than n. We’ll denote as n the length of permutation p 1, p 2, …, p n.
Your task is to find such permutation p of length n, that the group of numbers |p 1 - p 2|, |p 2 - p 3|, …, |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 ≤ 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.
Solution:
#include <cstring> #include <vector> #include <list> #include <map> #include <set> #include <deque> #include <stack> #include <bitset> #include <algorithm> #include <functional> #include <numeric> #include <utility> #include <sstream> #include <iostream> #include <iomanip> #include <cstdio> #include <cmath> #include <cstdlib> #include <ctime> #include <memory.h> #include <cassert> using namespace std; int a[1234567]; int main() { int n, k; scanf("%d %d", &n, &k); a[0] = 1; int low = 1, high = 1; for (int i = 1; i <= k; i++) { if (i % 2 == 1) { a[i] = ++high; } else { a[i] = --low; } } for (int i = k + 1; i < n; i++) { if (a[k] == low) { a[i] = a[i - 1] - 1; } else { a[i] = a[i - 1] + 1; } } int smallest = a[0]; for (int i = 1; i < n; i++) { if (a[i] < smallest) { smallest = a[i]; } } for (int i = 0; i < n; i++) { if (i > 0) printf(" "); printf("%d", a[i] - smallest + 1); } printf("\n"); return 0; }
Related posts:
Preorder Test
Hidden Bipartite Graph
TorCoder
Andrey and Problem
Primal Sport
Color the Carpet
Dijkstra on sparse graphs
Rock Is Push
Exercising Walk
Serega and Fun
Random Function and Tree
Sorting by Subsequences
Sherlock and the Encrypted Data
Train Hard, Win Easy
Pearls in a Row
Gena and Second Distance
Team Rocket Rises Again
Dungeons and Candies
Longest increasing subsequence
Bear and Polynomials
The Great Game
Pumping Stations
Looksery Party
Vladislav and a Great Legend
Let's Play Osu!
Curious Array
Buy Low Sell High
Kuroni and the Gifts
Ternary Search
Feed with Candy
Mergesort Strikes Back
Yet Another Array Queries Problem