333 Permutasiya#11838

333 Permutasiya (Həll təhlili)

Problem Müəllifi:	Hasan Saleh (MathModel)
Hazırlayan:	Hasan Saleh (MathModel)
Redaktə edən:	Hasan Saleh (MathModel)

Modlar vasitəsilə qurulmanı nəzərdən keçirək, yalnız 3 seçimimiz var ${0, 1, 2}$ \{0,1,2\}, bəzi sabit etibarlı naxışları qeyd edək, bundan əvvəl etibarlı üçlükləri müəyyən etməliyik

{(0, 0, 1) (0, 0, 2) (0, 1, 1) (0, 2, 2) (1, 1, 2) (1, 2, 2)}

\{ (0,0,1)\\ (0,0,2) \\ (0,1,1) \\ (0,2,2) \\ (1,1,2) \\ (1,2,2) \\ \}

və çox sayda haldan qaçmaq üçün etibarlı uzun təkrarlanan seqmenti nəzərdən keçirək, $[2, 2, 0, 0, 1, 1]$ [2,2,0,0,1,1] seqmentini nəzərdən keçirə bilərik, ən pis halda yalnız 5 element düzgün paylanacaq! Budur, sabit seqment:

[⌊ \frac{n}{6} ⌋ dəfə 0, 0, 1, 1, 2, 2]

[\underbrace{0,0,1,1,2,2}_{\left \lfloor \displaystyle \frac{n}{6} \right \rfloor \displaystyle \text{ dəfə}} ]

İndi qalan halları nəzərdən keçirək:

$n mod 6 = 0$ n \bmod 6=0 : Seqment özü hazırdır və düzgündür, hər şey yaxşıdır.
$n mod 6 = 1$ n \bmod 6=1 : Bu, $n mod 3 = 1$ n \bmod 3=1 deməkdir, yəni mod 1 olan əlavə bir elementimiz var, bu, qurulmanın önünə əlavə edilə bilər.
$n mod 6 = 2$ n \bmod 6=2 : Əvvəlki hal əsasında qurun, bu, $n mod 3 = 2$ n \bmod 3=2 deməkdir, yəni mod 2 olan əlavə bir elementimiz var, bu, arxaya əlavə edilə bilər.
$n mod 6 = 3$ n \bmod 6=3 : Burada hal fərqlidir çünki hər bir növ $(0, 1, 2)$ (0,1,2) üçün əlavə bir elementimiz var, burada $1$ və $2$ -ni önə, $0$ -ı isə arxaya itələyəcəyik, beləliklə qurulma $[2, 1, 1, 0, 0, 1, 1, ..., 0]$ [2,1,1,0,0,1,1,...,0] kimi olacaq.
$n mod 6 = 4$ n \bmod 6=4 : Əvvəlki hal əsasında qurun, əlavə $1$ -imiz olacaq, onu önə əlavə edə bilərik və hər şey yaxşıdır.
$n mod 6 = 5$ n \bmod 6=5 : Əvvəlki hal əsasında qurun, əlavə $2$ -miz olacaq, onu önə əlavə edə bilərik.

Bu, $deque$ ilə sürətlə edilə bilər, ümumi mürəkkəblik $O (n)$ .

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define pf push_front
int solve(int n){
    if(n==4){
        cout<<"3 4 1 2\n"; 
        return 0;
    }
    if(n==5){
        cout<<"3 4 1 2 5\n";
        return 0;
    }
    deque<int>p;
    stack<int>m0,m1,m2;
    for(int i=1;i<=n;i++){
        if(i%3==0)m0.push(i);
        if(i%3==1)m1.push(i);
        if(i%3==2)m2.push(i);
    }
    for(int i=0;i<n/6;i++){
        for(int i=0;i<2;i++){
            p.pb(m2.top());
            m2.pop();
        }
        for(int i=0;i<2;i++){
            p.pb(m0.top());
            m0.pop();
        }
        for(int i=0;i<2;i++){
            p.pb(m1.top());
            m1.pop();
        }
    }
    // qalanlar
    if(n%6==1 || n%6==2){
        p.pf(m1.top());
        m1.pop();
    }
    if(n%6==2){
        p.pb(m2.top());
        m2.pop();
    }
    if(n%6>=3){
        p.pf(m1.top());
        p.pf(m2.top());
        p.pb(m0.top());
        m1.pop();
        m2.pop();
        m0.pop();
    }
    if(n%6>=4){
        p.pb(m1.top());
    }
    
    if(n%6==5){
        p.pf(m2.top());
    }
    for(auto i:p){
        cout<<i<<" ";
    }
    cout<<"\n";
    return 0;
}  

int main() {
    int t;cin>>t;
    while(t--){
        int n;cin>>n;
        solve(n);
    }
    return 0;
}

C++