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:
R3D3’s Summer Adventure
Beautiful Sequence
Dream Team
Distinct Paths
Giải Thuật Và Lập Trình - Lê Minh Hoàng
Security
Tricky Interactor
Longest increasing subsequence
Worms
Xenia and Colorful Gems
Numbers
Deduction Queries
Gennady and a Card Game
Nikita and stack
New Year Permutation
Envy
Awesome Substrings
Ramesses and Corner Inversion
Robot Rapping Results Report
Ehab and Path-etic MEXs
Antipalindrome
Snake
The Child and Binary Tree
Amity Assessment
Colorado Potato Beetle
Social Network
Tree and XOR
Huffman Coding on Segment
MP3
Finding area of simple polygon in $O(N)$
New Year Santa Network
The Door Problem