O(1)

#include <bits/stdc++.h> // Nya
#define all(x) x.begin(),x.end() // Nya
#define rll(x) x.rbegin(),x.rend() // Nya
#define sz(x) x.size()
using ll = long long;
using namespace std;
void Solve()
{
    ll a,b,c;
    cin >> a >> b >> c;
    if (a < b && b < c)
    {
        cout << "STAIR\n";
        return;
    }
    if (a < b && b > c)
    {
        cout << "PEAK\n";
        return;
    }
    cout << "NONE\n";
}
int main()
{
    cin.tie(nullptr)->sync_with_stdio(false);
    ll tt = 1;
    cin >> tt;
    while (tt-->0)
    {
        Solve();
    }
}

O((n * 2) ^ 2) In this problem it was possible to notice that when numbers (i/2) and (j/2) that they had to be of the same parity

#include <bits/stdc++.h> // Nya
#define all(x) x.begin(),x.end() // Nya
#define rll(x) x.rbegin(),x.rend() // Nya
#define sz(x) x.size()
using ll = long long;
using namespace std;
void Solve()
{
    ll n;
    cin >> n;
    n*=2;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            if ((i / 2 + j / 2) % 2 == 0)
            {
                cout << "#";
            }
            else
            {
                cout << ".";
            }
        }
        cout << '\n';
    }

}
int main()
{
    cin.tie(nullptr)->sync_with_stdio(false);
    ll tt = 1;
    cin >> tt;
    while (tt-->0)
    {
        Solve();
    }
}

This code can be considered in O(1) complexity. I break this line that is given for hours and minutes if the time is on the clock less than 12 or equal to 24, then it will always be AM in other cases PM. And then look at the clock

#include <bits/stdc++.h> // Nya
#define all(x) x.begin(),x.end() // Nya
#define rll(x) x.rbegin(),x.rend() // Nya
#define sz(x) x.size()
using ll = long long;
using namespace std;
void Solve()
{
    string s;
    cin >> s;
    ll hh = stoll(s.substr(0, 2));
    string t = (hh < 12 || hh == 24 ? "AM" : "PM");
    if (hh == 0)
        hh = 12;
    else if (hh > 12)
        hh -= 12;
    cout << (hh < 10 ? "0" : "") << hh << s.substr(2, 3) << " " << t << '\n';

}
int main()
{
    cin.tie(nullptr)->sync_with_stdio(false);
    ll tt = 1;
    cin >> tt;
    while (tt-->0)
    {
        Solve();
    }
}

My logic consisted of creating an array that would store all binary decimal numbers. 1. I considered if the number consists only of the digits 1 and 0 then if it consisted it displayed "YES" If not then I took the number n and divided it by all binary numbers, if the cycle cannot divide anymore then the answer is NO, otherwise if it came to the cycle n == 1 then the answer is YES

#include <bits/stdc++.h> // Nya
#define all(x) x.begin(),x.end() // Nya
#define rll(x) x.rbegin(),x.rend() // Nya
#define sz(x) x.size()
using ll = long long;
using namespace std;
set <ll> pr;
void Rec(ll sum)
{
    if (sum > 1e5)
        return;
    pr.insert(sum);
    Rec(sum * 10);
    Rec(sum * 10 + 1);
}
void Solve()
{
    ll n; cin >> n;
    ll p  = n;
    ll null = 0;
    ll one = 0;
    string s = to_string(n);
    while (p > 0)
    {
        null+=(p % 10 == 0);
        one+=(p % 10 == 1);
        p/=10;
    }
    if (null + one == sz(s))
    {
        cout << "YES\n";
        return;
    }
    bool ans = true;
    while (n > 1)
    {
        bool q = false;
        for (auto & it : pr)
        {
            if (it == 1)
                continue;
            while (n % it == 0)
            {
                n/=it;
                q = true;
            }
        }
        if (!q && n > 1)
        {
            ans = false;
            break;
        }
    }
    cout << (ans ? "YES\n" : "NO\n");
}
int main()
{
    cin.tie(nullptr)->sync_with_stdio(false);
    ll tt = 1;
    cin >> tt;
    Rec(1);
    while (tt-->0)
    {
        Solve();
    }
}

Let's note that the length of the string k — can only be a divisor of n — the size of the string. In my logic I went by the size that it might be. Then I took cycle 2 which one might say created substrings from i to i + d i — where we are d is the divisor, which we consider to be the length . 3 in a loop I simply checked whether the string matches the condition. I remind you of the condition “Find the length of the shortest string k, such that several (possibly one) copies of k can be concatenated together to form a string the same length as s, and there is at most one different character". Complexity of the algorithm that is implemented sqrt(n) * log(n) * n

#include <bits/stdc++.h> // Nya
#define all(x) x.begin(),x.end() // Nya
#define rll(x) x.rbegin(),x.rend() // Nya
#define sz(x) x.size()
using ll = long long;
using namespace std;
void Solve()
{
     ll n; cin >> n;
    string s; cin >> s;
    vector <ll> divs;
    for (int i = 1; i * i <= n ; i++)
    {
        if (n % i == 0)
        {
            divs.push_back(i);
            if (i != n / i)
                divs.push_back(n/i);
        }
    }
    sort(all(divs));
    for (auto& d : divs)
    {
        bool ok = false;
        for (int i = 0; i < n; i += d)
        {
            bool q = true;
            string t = s.substr(i,d);
            ll len = 0;
            ll cnt = 0;
            for (int j = 0; j < n; j++)
            {
                if (t[len % d] != s[j])
                {
                    cnt++;
                }
                if (cnt > 1)
                {
                    q = false;
                    break;
                }
                len++;
            }
            if (q)
            {
                ok = true;
                break;
            }
        }
        if (ok)
        {
            cout << d << '\n';
            return;
        }
    }
}
int main()
{
    cin.tie(nullptr)->sync_with_stdio(false);
    ll tt = 1;
    cin >> tt;
    while (tt-->0)
    {
        Solve();
    }
}

In this problem it is more difficult to implement dp than to come up with logic. In this problem you just need to go through all the permutations.

Even the authors gave hints that this is due to permutations. Problem limits

1 <= n <= 16

2^n < 2^16

^ — degree

#include <bits/stdc++.h> // Nya
#define all(x) x.begin(),x.end() // Nya
#define rll(x) x.rbegin(),x.rend() // Nya
#define sz(x) x.size()
using ll = long long;
using namespace std;
void Solve()
{
    ll n;
    cin >> n;
    map<string, ll> mp;
    vector<pair<string, string>> par(n);
    for(ll i = 0; i < n; i++)
    {
        cin >> par[i].first >> par[i].second;
        mp[par[i].first]++;
        mp[par[i].second]++;
    }
    ll cnt = 0;
    vector<pair<ll, ll>> kol(n);
    for (auto & [x,y] : mp)
        y = ++cnt + 1;
    for(ll i = 0; i < n; i++)
        kol[i].first = mp[par[i].first],kol[i].second = mp[par[i].second];
    ll ans = 0;
    ll TwoLenMask = (1<<n)-1;
    vector<vector<ll>> dp(1 + n + 1 , vector<ll>(1 + TwoLenMask + 1, -1));
    function <ll(ll, ll, ll)> rec = [&] (ll TwoLenMask,ll len,ll n)
    {
        if(TwoLenMask == 0) return 0LL;
        if(len != -1 && dp[len][TwoLenMask] != -1) return dp[len][TwoLenMask];
        pair<ll,ll> cnt = {-1,-1};
        if (len != -1)
            cnt = kol[len];
        ll ans = 0;
        for(ll i = 0; i<n; i++)
            if(TwoLenMask & (1LL << i))
            {
                if(len == -1 ||  kol[i].first == cnt.first ||  kol[i].second == cnt.second)
                    ans = max(ans,1+rec((TwoLenMask^(1<<i)), i, n));
            }

        if(len == -1) return ans;
        return dp[len][TwoLenMask] = ans;
    };
    cout << n - rec(TwoLenMask, -1, n) << '\n';
}

int main()
{
    cin.tie(nullptr)->sync_with_stdio(false);
    ll tt = 1;
    cin >> tt;
    while (tt-->0)
    {
        Solve();
    }
}