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:
Big Problems for Organizers
The Evil Temple and the Moving Rocks
New Year and the Permutation Concatenation
Koala and Lights
Maximum flow - Push-relabel algorithm
Divide Points
New Year and Permutation
Circle of Numbers
Manacher's Algorithm - Finding all sub-palindromes in $O(N)$
JYPnation
Segment Tree
Cookie Clicker
Little Artem and Grasshopper
Dream Team
Carrot Cakes
Permutation Partitions
Finding repetitions
Pudding Monsters
Modernization of Treeland
Three Integers Again
Connected Components
Fox and Box Accumulation
Looksery Party
Pick's Theorem - area of lattice polygons
Distinct Paths
Yui and Mahjong Set
Banners
Sereja ans Anagrams
Snake
Beautiful Bracket Sequence (easy version)
Maximum Xor Secondary
Love "A"