C - 1 2 1 3 1 2 1 || AtCoder Beginner Contest 247

 LINK: C - 1 2 1 3 1 2 1

প্রব্লেম স্টেইট্মেন্টঃ একটি ভ্যালু N দেয়া থাকবে। আমাদের নিচের মত করে একটি সিকুয়েঞ্জ জেনারেট করতে হবে।

IF N = 1 : 1

IF N = 2 : 1 2 1

IF N = 3 : 1 2 1 3 1 2 1

IF N = 4 : 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1

অবসারবেশন ঃ একটু ভালোভাবে খেয়াল করলেই বোঝা যায় সিকুয়েন্সটি একটি সার্টেইন প্যাটার্ন ফলো করে এগোচ্ছে।

যেমন-

 1 এর ইনিশিয়াল পজিশন হচ্ছে POW(2, 1 - 1)

 2 এর ইনিশিয়াল পজিশন হচ্ছে POW(2, 2 - 1)

 3 এর ইনিশিয়াল পজিশন হচ্ছে POW(2, 3 - 1) 

 4 এর ইনিশিয়াল পজিশন হচ্ছে  POW(2, 4 - 1)

এখন শুধু পজিশনগুলোর সাথে POW(2, X) যোগ করে সামনে এগোতে হবে। X  হচ্ছে প্রত্যেকটা ভ্যালুর মান।

উপরের সিকুয়েন্স গুলো থেকে আরো বোঝা যাচ্ছে সিকুয়েন্সের দৈর্ঘ হবে POW(2, N)  - 1. 

CODE:

#include<bits/stdc++.h>

using namespace std;

#define ll long long

const ll N = 6e5 + 7;

ll arr[N];

int32_t main(){

ios_base::sync_with_stdio(false);cin.tie(NULL);

fill(arr, arr + N, -1);

ll x, y;

ll ans = 0;

ll n;

cin >> n;

for(ll i = 1; i <= n; i++){

x = pow(2, i - 1);

y = pow(2, i);

ans = x;

arr[x] = i;

while(ans <= (2 * pow(2, n - 1)) - 1){

ans+=y;

arr[ans] = i;

}

   

}

for(ll i = 1; i <= (2 * pow(2, n - 1)) - 1; ++i){

cout << arr[i] << ' ';

}

cout << '\n';

}