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:
Counting labeled graphs
Kaavi and Magic Spell
Preorder Test
Lingua Romana
Basic Geometry
Looksery Party
Pavel and barbecue
New Year and the Sphere Transmission
Chat Order
Prefix function. Knuth–Morris–Pratt algorithm
Finding Bridges Online
New Year and Forgotten Tree
Tidying Up
Dima and Game
Buy Low Sell High
Professor GukiZ and Two Arrays
Hongcow Builds A Nation
Circle of Numbers
EKG
Serega and Fun
Voting for Photos
Circle-Circle Intersection
Vertical decomposition
Flights
Bribes
Wrong Subtraction
New Year Book Reading
Xenia and Colorful Gems
Cow and Exercise
Let Them Slide
Underfail
New Year and the Permutation Concatenation