В оптимальном ответе максимальное количество цифр, так что нужно использовать только цифры $$$1,2$$$.

Чередуйте эти цифры, чтобы не было соседних одиннаковых цифр.

Так как мы хотим максимизировать нужное нам число, найдем сначало самое длинное подходящее число. Очевидно, что для этого лучше использовать только цифры $$$1$$$ и $$$2$$$. Поэтому ответ всегда имеет вид $$$2121\ldots$$$ или $$$1212\ldots$$$. Первый вариант оптимален, когда $$$n$$$ имеет остаток $$$2$$$ или $$$0$$$ по модулю $$$3$$$, в противном случае оптимален второй вариант.

Ниже приведен пример аккуратной реализации.

#include <bits/stdc++.h>
 
using namespace std;
 
void solve() {
    int n;
    cin >> n;
    int type;
    if (n % 3 == 1)
        type = 1;
    else
        type = 2;
    int sum = 0;
    while (sum != n) {
        cout << type;
        sum += type;
        type = 3 - type;
    }
    cout << '\n';
}
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
 
    int t;
    cin >> t;
    while (t--)
        solve();
}

Что представляет собой картинка, если ответ на задачу "YES".

Подумайте над квадратом размера $$$2 \times 2$$$.

Заметим, что ответ на задачу "YES" тогда и только тогда, когда картинка предствляет из себя какое-то количество непересекающихся прямоугольников. Теперь посмотрим в этом случае на все квадраты размера $$$2 \times 2$$$, заметим, что в каждом из них не может быть ровно $$$3$$$ закрашенных клетки.

Также понятно, что если найдутся $$$3$$$ таких клетки, то найдутся два пересекающихся прямоугольника. Поэтому нужно просто проверить, есть ли квадрат $$$2 \times 2$$$, в котором ровно $$$3$$$ закрашенных клетки.

#include <bits/stdc++.h>
 
using namespace std;
 
void solve() {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> a(n, vector<int> (m));
    for (int i = 0; i < n; ++i) {
        string s;
        cin >> s;
        for (int j = 0; j < m; ++j) {
            a[i][j] = s[j] - '0';
        }
    }
    for (int i = 0; i < n - 1; ++i) {
        for (int j = 0; j < m - 1; ++j) {
            int sum = a[i][j] + a[i][j + 1] + a[i + 1][j] + a[i + 1][j + 1];
            if (sum == 3) {
                cout << "NO\n";
                return;
            }
        }
    }
    cout << "YES\n";
}
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
 
    int t;
    cin >> t;
    while (t--)
        solve();
}

Ответ всегда есть, когда правая верхняя клетка покрашена в белый цвет.

Представьте, что у вас есть только прямоугольники размера $$$1 \times 2$$$.

Закрашивайте клетки с "конца".

По условию, если левая верхняя клетка покрашена в черный цвет, то мы не можем так покрасить. Иначе можно. Давайте будем красить клетки в следующем порядке: $$$(n, m), (n, m - 1), \ldots, (n, 1), (n - 1, m), \ldots (1, 1)$$$.

Пусть клетку $$$(i, j)$$$ нужно покрасить в черный цвет, тогда если $$$j > 1$$$, то просто покрасим прямоугольник $$$(i, j - 1)$$$, $$$(i, j)$$$. Иначе, если $$$j = 1$$$, то мы покрасим прямоугольник $$$(i - 1, j)$$$.

После такой операции никакие клетки, которые мы красили до этого, не перекрасятся, так как у них одна координата больше нашей, а сама клетка покрасится в черный цвет.

Таким образом мы умеем красить таблицу за максимум $$$n \cdot m - 1$$$ операций.

#include <bits/stdc++.h>
 
using namespace std;
 
void solve() {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> a(n, vector<int> (m));
    for (int i = 0; i < n; ++i) {
        string s;
        cin >> s;
        for (int j = 0; j < m; ++j)
            a[i][j] = s[j] - '0';
    }
    vector<array<int, 4>> ans;
    if (a[0][0] == 1) {
        cout << -1<< '\n';
        return;
    }
    
    for (int j = m - 1; j >= 0; --j) {
        for (int i = n - 1; i >= 0; --i) {
            if (a[i][j]) {
                if (i != 0) {
                    ans.push_back({i, j + 1, i + 1, j + 1});
                } else {
                    ans.push_back({i + 1, j, i + 1, j + 1});
                }
            }
        }
    }
    cout << ans.size() << '\n';
    for (auto i : ans) {
        cout << i[0] << ' ' << i[1] << ' ' << i[2] << ' ' << i[3] << '\n';
    }
}
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
 
    int t;
    cin >> t;
    while (t--)
        solve();
}

Число красивое только в том случае, если оно кратно $$$d$$$, но не кратно $$$d^2$$$

Давайте решим более общую задачу: посчитать количество таких разбиений.

Эта задача решается динамическим программированием.

Храните в динамике оставшееся число, а также последний делитель.

Давайте решим более сложную задачу: посчитать количество разбиений на такие множители.

Заметим, что это несложно решается диническим программированием. Пусть $$$dp_{n, d}$$$ — количество разложений на множители, если у нас осталось число разложить число $$$n$$$, а до этого мы поделили на число $$$d$$$. Перебирем все такие красивые числа $$$i \geq d$$$, которые делят $$$n$$$, тогда $$$dp_{n / i, i} += dp_{n, d}$$$.

Заметим, что в это случае мы каждый вариант учли ровно один раз, поскольку мы считаем делители в порядке их увеличения.

Пусть $$$C$$$ — это количество делителей числа $$$x$$$, а $$$V$$$ — это количество красивых делителей числа $$$x$$$. Тогда это работает за $$$O(С \cdot V)$$$ или $$$O(C \cdot V^2 \cdot log)$$$ в зависимости от реализации (так как $$$n$$$ всегда является делителем числа $$$x$$$), но все это легко заходит, так как $$$V$$$ не больше (посчитать максимальное значение).

#include <bits/stdc++.h>
 
using namespace std;
 
bool good(int i, int d) {
    return i % d == 0 && i % (1ll * d * d) != 0;
}
 
void solve() {
    int x, d;
    cin >> x >> d;
    map<pair<int, int>, int> dp;
    dp[{x, 1}] = 1;
    int res = 0;
    vector<int> del;
    for (int i = 1; i * i <= x; ++i) {
        if (x % i == 0) {
            if (good(i, d))
                del.push_back(i);
            if (x != i * i && good(x / i, d))
                del.push_back(x / i);
        }
    }
    while (dp.size()) {
        auto z = *dp.rbegin();
        if (z.first.first == 1) {
            res += z.second;
        }
        for (auto i : del) {
            if (z.first.first % i == 0 && i >= z.first.second) {
                dp[{z.first.first / i, i}] = min(dp[{z.first.first / i, i}] + z.second, 2);
            }
        }
        dp.erase(z.first);
    }
    if (res == 1)
        cout << "NO\n";
    else
        cout << "YES\n";
}
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
 
    int t;
    cin >> t;
    while (t--)
        solve();
}

Рассмотрим случаи

Пусть $$$x = d^a \cdot b$$$. Где $$$b$$$ не кратно $$$d$$$.

Тогда рассмотрим несколько случаев:

• $$$a = 1$$$. Тогда $$$a$$$ — это красивое число, поскольку любое число кратное $$$d^2$$$ можно разложить на $$$d \cdot (a / d)$$$, каждое из которых красиове, а число кратное только $$$d$$$, очевидно, разложить нельзя. Значит в этом случае ровно один вариант.

• $$$b$$$ — составное, тогда, очевидно, мы можем разложить несколькими вариантами, если $$$a \neq 1$$$.

• $$$d$$$ — простое. Если $$$b$$$ простое, то утверждение — у нас только один вариант разложить число. Так как каждый красивый множитель вида $$$d \cdot k$$$. Но поскольку $$$d$$$ простое, то никаких других способов разложить нет, кроме как добавить множитель из $$$b$$$, а поскольку $$$b$$$ простое, то все эти варианты будут равны до перестановки.

• $$$d$$$ — составное и не является степенью простого. Если $$$a \leq 2$$$, то этот случай никак не отличается от прошлого, так как мы все равно должны получить два красивых множителя и все они будут просто равны $$$d$$$. Иначе пусть $$$d = p \cdot q$$$, где $$$gcd(p, q) = 1$$$. Тогда мы можем сделать число $$$p \cdot q^{b - 1}$$$ и $$$p^{b - 1} \cdot q$$$. А также $$$q \cdot p, q \cdot p, \ldots , q \cdot p$$$, в этом случае у нас разное количество делителей, так что эти варианты будут разные, а значит у нас несколько вариантов в этом случае.

• $$$d$$$ — степень простого числа. Тогда $$$d = p^k$$$. Утверждение, если $$$d = p^2$$$, а $$$x = p^7$$$, то нельзя разложить несколькими способами, иначе, если $$$a > 2$$$ и $$$k > 1$$$, то посмотрим на разбиение $$$p^{2k - 1}, p^{k + 1}, p^k, \ldots , p^k$$$, понятно, что если $$$k > 2$$$, то даже если $$$b = p$$$, то множитель $$$p^{k + 2}$$$ до сих пор будет красивым, поэтому это не отличается от составного $$$d$$$ в прошлом случае. Иначе, если $$$k = 2$$$, то если $$$a = 3$$$ и $$$b = p$$$, то ничего добавить нельзя, а иначе у нас будет возможность выбрать $$$3$$$ множителя $$$p^k$$$, а остальное как-то разложить (так как в этом случае $$$a > 3$$$, то хотя бы еще один множитель будет) и добавить туда $$$b$$$. А эти 3 множителя мы можем разложить на $$$2$$$ или $$$3$$$ множителя, как написано выше. Поэтому единственный уникальный случай, когда $$$d$$$ — степень простого, это $$$d = p^2, x = p^7$$$.

#include <bits/stdc++.h>
 
using namespace std;
 
int prime(int x) {
    for (int i = 2; i * i <= x; ++i) {
        if (x % i == 0)
            return i;
    }
    return -1;
}
 
void solve() {
    int x, d;
    cin >> x >> d;
    int cnt = 0;
    while (x % d == 0) {
        ++cnt;
        x /= d;
    }
    if (cnt == 1) {
        cout << "NO\n";
        return;
    }
    if (prime(x) != -1) {
        cout << "YES\n";
        return;
    }
    if (prime(d) != -1 && d == prime(d) * prime(d)) {
        if (x == prime(d) && cnt == 3) {
            cout << "NO\n";
            return;
        }
    }
    if (cnt > 2 && prime(d) != -1) {
        cout << "YES\n";
        return;
    }
    cout << "NO\n";
}
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    int t;
    cin >> t;
    while (t--)
        solve();
}

После каждой операции максимальный номер всегда увеличивается на конкретное число.

Ученики с номером большим $$$n$$$ нас не интересуют.

Представьте, что школьников не выгоняют, но в каждый момент времени нас просто интересует школьник с минимальным номером. Очевидно, что ответ в этом случае никак не поменяется.

Поймите, что каждый школьник после всех операций перейдет за одну конкретную парту.

Напишите жадник

После каждого урока номер человека с максимального номера увеличивается на количество парт, куда никто не переходит. Поэтому можно легко вычислить сколько прошло времени с самого начала, пусть это число $$$k$$$.

Тогда давайте представим, что школьников не выгоняют, а в каждый момент времени нас просто интересует школьник с минимальным номером. Очевидно, что ответ в этом случае никак не поменяется.

Пусть $$$to_i$$$ — это парта, в которую перейдет школьник после $$$k$$$ пересадок, изначально сидевший за $$$i$$$ партой. Это стандартная задача, которую можно решить при помощи бинарный подъемов или не самого приятного dfs c выделением циклов и подобным. (но последнее мы не рекомендуем вам писать), Определим множество $$$V_i$$$, как множество всех чисел $$$j$$$, где $$$to_j = i$$$.

Пусть стартовая расстановка школьника — это перестановка $$$b$$$, тогда поймем, что если за $$$i$$$ парту кто-то пересаживается после $$$k$$$ операций, то значение в ней это — минимальное значение в $$$V_i$$$. А если за нее никто не пересаживается, то в ней просто будет всегда сидеть школьник с одиннаковым номером, вне зависимости от начальной рассадки. После этого не сложно покзаать оптимальную стартовую рассадку школьников.

Пусть $$$s$$$ — это множество школьников, для которых мы пока не выбрали парту за которой они сидят. Будем перебирать $$$i$$$ от $$$1$$$ до $$$n$$$ по возрастанию. Тогда нужно понять, кто должен сидеть за $$$i$$$ партой.

Если мы знаем, что существует парта, для которой должно выполняться $$$min(V_i) = i$$$, то мы должны посадить за $$$i$$$ парту школьника с минимальным номером из $$$V_i$$$, а оставшихся людей мы можем садить за любые парты с номером большим $$$i$$$, поэтому добавим в множество $$$s$$$ всех остальных школьников. А иначе нам нужно просто взять человека из $$$s$$$ с минимальным номером и посадить его за место под номером $$$i$$$, а затем просто удалить его из множества $$$s$$$.

#include <bits/stdc++.h>
 
using namespace std;
 
const int K = 30;
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
 
    int n;
    cin >> n;
    vector<int> cnt(n);
    vector<vector<int>> up(n, vector<int> (K));
    for (int i = 0; i < n; ++i) {
        int a;
        cin >> a;
        --a;
        ++cnt[a];
        up[i][0] = a;
    }
    for (int k = 1; k < K; ++k) {
        for (int i = 0; i < n; ++i) {
            up[i][k] = up[up[i][k - 1]][k - 1];
        }
    }
    vector<int> a(n);
    int cnt_bad = 0;
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
        if (!cnt[i]) {
            ++cnt_bad;
        }
    }
    int k = (*max_element(a.begin(), a.end()) - n) / cnt_bad;
    vector<vector<int>> add(n);
 
    for (int i = 0; i < n; ++i) {
        int v = i, level = k;
        for (int j = K - 1; j >= 0; --j) {
            if (level >= (1 << j)) {
                level -= (1 << j);
                v = up[v][j];
            }
        }
        add[a[v] - 1].push_back(i);
    }
    set<int> now;
    vector<int> ans(n);
    for (int i = 0; i < n; ++i) {
        if (add[i].size()) {
            int res = *min_element(add[i].begin(), add[i].end());
            for (int j : add[i]) {
                if (j != res) {
                    now.emplace(j);
                }
            }
            ans[res] = i + 1;
        } else {
            ans[*now.begin()] = i + 1;
            now.erase(*now.begin());
        }
    }
    for (int i : ans)
        cout << i << ' ';
    cout << '\n';
}

Осознайте, что максимальный элемент всегда является "перегибом" первой последовательности.

Можно предположить, что "перегиб" второй подпоследовательности всегда будет левее максимального элемента (если что, можно будет потом просто развернуть массив).

Всего у нас существует $$$3$$$ момента времени — обе подпоследовательности возрастают, первая убывает, а вторая возрастает, или обе подпоследовательности убывают.

Первый и третий случай решаются очевидной жадностью.

Для второго можно просто написать динамику.

Перегиб последовательности — это максимальное число в подпоследовательности. Тогда заметим, что в первой подпоследовательности перегибом будет максимальное число в нашем массиве, пусть его позиция в массиве — $$$ind$$$.

Тогда давайте для удобства скажем, что перегиб второй подпоследовательности будет правее максимального элемента. (потом развернем массив и запустим решение еще один раз).

В этом случае у нас будет $$$3$$$ состояния: обе подпоследовательности возрастают, первая убывает, а вторая возрастает или обе подпоследовательсности убывают.

Решим для начала первый случай:

Пусть $$$dp1_i$$$ — минимально возможный максимальный элемент в подпоследовательности, которая не содержит $$$i$$$ элемент. Она считается не сложно. Если $$$dp1_{i - 1} < a_{i}$$$, то $$$dp1_{i} = min(dp1_{i}, a_{i - 1})$$$, так как в этом случае мы можем добавить $$$i$$$ элемент в подпоследовательность, которая не содержит элемент $$$i - 1$$$. Аналогично, если $$$a_{i - 1} < a_{i}$$$, то $$$dp1_{i} = min(dp1_{i}, dp1_{i - 1})$$$.

Третий случай считается анологично, но только его нужно считать с конца. (Этот массив будет $$$dp3$$$)

Теперь разберемся со вторым случаем:

Пусть $$$dp2_{i, 0}$$$ — минимально возможный последний элемент во второй подпоследовательности, если $$$i$$$ элемент принадлежит первой подпоследовательности. И $$$dp2_{i, 1}$$$ — максимально возможный последний элемент в первой подпоследовательности, если $$$i$$$ элемент принадлежит второй подпоследовательности. Есть несколько вариантов. Если $$$i$$$ и $$$i - 1$$$ лежат в одинаковых и разных подпоследовательностях. И мы будем считать для $$$i \leq ind$$$, поскольку до этого участка обе подследовательности возрастают, а это уже другой посчитанный случай. И тогда не сложно получить формулы пересчета:

• $$$dp2_{ind, 0} = dp1_{ind}$$$, по определению $$$dp2_{ind, 0}$$$
• Если $$$a_{i - 1} > a_i$$$, то $$$dp2_{i, 0} = min(dp2_{i, 0}, dp2_{i - 1, 0})$$$.
• Если $$$dp2_{i - 1, 1} > a_i$$$, то $$$dp2_{i, 0} = min(dp2_{i, 0}, a_{i - 1})$$$.
• Если $$$a_{i - 1} < a_{i}$$$, то $$$dp2_{i, 1} = max(dp2_{i, 1}, dp3_{i - 1, 1})$$$.
• Если $$$dp2_{i - 1, 0} < a_i$$$, то $$$dp2_{i, 1} = max(dp2_{i, 1}, a_{i - 1})$$$.

Теперь поймем, что элемент с номером $$$i$$$ может быть перегибом второй подпоследовательности, если $$$i > ind$$$, а также $$$dp2_{i, 1} > dp3_{i}$$$. То есть мы можем перейти из второго состояния в третье.

#include <bits/stdc++.h>
 
using namespace std;
 
const int inf = 1e9 + 228;
 
int solve (int n, vector<int> a) {
    int ind = max_element(a.begin(), a.end()) - a.begin();
    vector<int> dp1(n, inf);
    dp1[0] = -1;
    for (int i = 1; i <= ind; ++i) {
        if (a[i] > dp1[i - 1])
            dp1[i] = min(dp1[i], a[i - 1]);
        if (a[i] > a[i - 1])
            dp1[i] = min(dp1[i], dp1[i - 1]);
    }
 
    vector<int> dp2(n, inf);
    dp2[n - 1] = -1;
    for (int i = n - 2; i >= ind; --i) {
        if (a[i] > dp2[i + 1])
            dp2[i] = min(dp2[i], a[i + 1]);
        if (a[i] > a[i + 1])
            dp2[i] = min(dp2[i], dp2[i + 1]);
    }
 
    vector<array<int, 2>> dp3(n, {inf, -inf});
    dp3[ind][0] = dp1[ind];
    int ans = 0;
    for (int i = ind + 1; i < n; ++i) {
        if (a[i - 1] > a[i])
            dp3[i][0] = min(dp3[i][0], dp3[i - 1][0]);
        if (dp3[i - 1][1] > a[i])
            dp3[i][0] = min(dp3[i][0], a[i - 1]);
        
        if (a[i - 1] < a[i])
            dp3[i][1] = max(dp3[i][1], dp3[i - 1][1]);
        if (dp3[i - 1][0] < a[i])
            dp3[i][1] = max(dp3[i][1], a[i - 1]);
        
        if (dp3[i][1] > dp2[i])
            ++ans;
    }
    return ans;
}
 
signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
 
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; ++i)
        cin >> a[i];
    int ans = solve(n, a);
    reverse(a.begin(), a.end());
    cout << ans + solve(n, a) << '\n';
}