Нассер і перестановка (Розбір)

Розв'язок

Загальна ідея: Щоб найбільший спільний дільник сусідніх різниць був більший за $1$, усі різниці повинні мати спільний дільник щонайменше $2$.

Найпростішою стратегією є побудова перестановки, в якій числа з однаковою парністю згруповані разом. Наприклад:

У середині кожної групи парності кожна сусідня різниця є парною, тобто ділиться на $2$. Тому найбільший спільний дільник цих різниць щонайменше $2$.

Найдовша можлива підпослідовність, яку можемо таким чином сформувати, це просто розмір більшої групи за парністю.

— Кількість непарних чисел від $1$ до $n$ дорівнює $\lceil n/2\rceil$.

— Кількість парних чисел дорівнює $\lfloor n/2\rfloor$.

Таким чином, відповідь:

Розв'язання виконується за $\mathcal{O}(1)$ часу на кожен тестовий випадок.

#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';
    }
}