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:
Berland Elections
Wonder Room
Eugene and an array
Lucky Days
Well-known Numbers
Ramesses and Corner Inversion
XORinacci
Drazil Likes Heap
Grandfather Dovlet’s calculator
P-binary
Oriented area of a triangle
Context Advertising
Mateusz and an Infinite Sequence
Eevee
Wilbur and Trees
Placing Bishops on a Chessboard
Fox And Polygon
Perfect Triples
The Chocolate Spree
Yura and Developers
Little Artem and Grasshopper
K Paths
New Year and the Permutation Concatenation
Disjoint Set Union
Ehab and Path-etic MEXs
Powered Addition
New Year and Naming
Distinct Paths
Median on Segments
Inversions problem
New Year and Binary Tree Paths
Fish Weight