A. Diverse Permutation
Permutation p is an ordered set of integers p1, p2, ..., pn, consisting of n distinct positive integers not larger than n. We'll denote as nthe length of permutation p1, p2, ..., pn.
Your task is to find such permutation p of length n, that the group of numbers |p1 - p2|, |p2 - p3|, ..., |pn - 1 - pn| 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.
Sample test(s)
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
**************************************code****************
#include<iostream>
using namespace std;
typedef long long int lli;
int main()
{
int n;
cin>>n;
int k;
cin>>k;
int start=1;
int end=n;
int arr[n+10];
int f=0;
for(int i=1;i<=k;i++)
{
// cout<<" k is "<<k<<endl;
if(f==0)
{
// cout<<" fill start"<<endl;
arr[i]=start;
start++;
f=1;
}
else
{
// cout<<" fill end"<<endl;
f=0;
arr[i]=end;
end--;
}
}
// cout<<"start"<<start<<endl;
if(k%2==1)
for(int i=k+1;i<=n;i++)
{
arr[i]=start;
start++;
}
else
{
for(int i=k+1;i<=n;i++)
{
arr[i]=end;
end--;
}
}
for(int i=1;i<=n;i++)
cout<<arr[i]<<" ";
cout<<endl;
}
No comments:
Post a Comment