Nasser və permütasiya (Həll təhlili)

Həll

Ümumi Fikir: Qoşaq hissələrinin ümumi böləninin $1$-dən böyük olmasını təmin etmək üçün bütün fərqlərin ən azı $2$ ortaq böləni olmalıdır.

Ən sadə strategiya eyni pariteliyə malik olan rəqəmləri birlikdə olan permutasiya qurmaqdır. Məsələn:

Hər pariteli qrup içindəki hər bir qoşaq fərqi cütlükdür, yəni $2$ ilə bölünəndir. Bu səbəbdən bu fərqlərin ümumi böləni ən azı $2$-dir.

Bu şəkildə qurula bilən ən uzun mümkün alt sıra sadəcə daha böyük pariteli qrupun ölçüsüdür.

— $1$ dən $n$-ə qədər olan tək rəqəmlərin sayı $\lceil n/2\rceil$.

— Cüt rəqəmlərin sayı $\lfloor n/2\rfloor$.

Bu səbəbdən cavab:

Həll hər test üçün $\mathcal{O}(1)$ vaxtda çalışır.

#include <bits/stdc++.h>
using namespace std;
#define int long long 

void solve(){
    int n;
    cin>>n;
    cout<<(n+1)/2;
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin>>t;
    while(t--){
        solve();
        cout<<'\n';
    }
}