The solution testing model has been updated on the platform.

To solve this problem, an investigation was carried out, namely:

• If $$$n \in [0, 21)$$$, then output amazing!.
• Otherwise, if $$$n\in[21,\ 51)$$$, then output good!.
• Otherwise, if $$$n\in[51,\ 151)$$$, then output bad!.
• If there is $$$n \in [51,\ 1001)$$$, then it is necessary to output very bad!.

Final asymptotics of the solution: $$$\mathcal{O}(1)$$$

n = int(input())
if n < 21:
    print("amazing!")
elif n < 51 and n > 20:
    print("good!")
elif n < 151 and n > 50:
    print("bad!")
else:
    print("very bad!")

• Didn't solve
• Good task
• Average task
• Bad task

There are a lot of ways to solve this problem, so we will analyze the most optimal one.

The condition states that you need to find any interesting subsegment, the length of which is $$$\le n - 1$$$. Then it is not difficult to guess that it is enough to derive a segment from the $$$1$$$ element — the maximum of the $$$a$$$ array, which will satisfy the condition of the problem.

Final asymptotics of the solution: $$$\mathcal{O}(n)$$$

n = int(input())
print(max(list(map(int, input().split()))))

• Didn't solve
• Good task
• Average task
• Bad task

Calculating using this formula directly will most likely not work, since $$$n$$$ can reach $$$10^9$$$ and the numbers will be huge. But you can notice that $$$4 = 2 \times 2$$$, $$$21 = 3 \times 7$$$, $$$14 = 2\times 7$$$, $$$15 = 3 \times 5$$$, $$$6 = 2 \times 3$$$. Using standard rules for working with degrees, it is possible to represent the numerator and denominator as a product of prime numbers 2, 3, 5, 7 in some degrees. When dividing $$$a$$$ by $$$b$$$, the number $$$n$$$ will decrease everywhere and only the number 200 will remain. That is, $$$\frac{a}{b} = 200$$$. So $$$\cfrac{a \times n}{b} = 200 \times n$$$, so to solve the problem, you just need to count the number $$$n$$$ and output $$$200 \times n$$$. It is also worth noting that for large values of $$$n$$$ in some programming languages, the answer may not fit into a 32-bit integer data type, so it is necessary to use a 64-bit data type.

The final asymptotics of the solution: $$$\mathcal{O}(1)$$$

#include <bits/stdc++.h>
 
using namespace std;
 
int main() {
    int n;
    cin >> n;
    cout << 200ll * n << "\n";
    return 0;
}

n = int(input())
print(n * 200)

• Didn't solve
• Good task
• Average task
• Bad task

To solve this version of the problem, it was enough to go through all the possible numbers that Ilya could think of. Thus, for each inverse $$$i$$$-th number, you need to check it for the correspondence between the sums of numbers in even and odd positions, as well as the number of zeros, for the proposed $$$j$$$-th test case of the input. Since the numbers to be sorted out are quite small, the asymptotics of their verification can be neglected. If the hidden number is found successfully, print the answer YES for the $$$j$$$-th test case, otherwise, if such a number does not exist for the values $$$a$$$, $$$b$$$ and $$$k$$$ given by Ilya or is greater than $$$10 ^4$$$, the answer is NO.

The resulting asymptotics of the solution: $$$\mathcal{O}(t \cdot n)$$$, where $$$n$$$ ($$$1 \le n \le 10^4$$$) — Ilya's number.

for _ in range(int(input())):
    a, b, k = map(int, input().split())
    answer = False
    for i in range(1, 10 ** 4 + 1):
        s = str(i)[::-1]
        a_s = 0
        b_s = 0
        k_s = 0
        for j in range(len(s)):
            if j % 2 == 0:
                b_s += int(s[j])
                if s[j] == '0':
                    k_s += 1
            else:
                a_s += int(s[j])
                if s[j] == '0':
                    k_s += 1
        if a == a_s and b == b_s and k == k_s:
            print("YES")
            answer = True
            break
    if not answer:
        print("NO")

• Didn't solve
• Good task
• Average task
• Bad task

At the beginning, let's find all prime numbers from in the range [1, 100]. This can be done manually, using algorithms, for example, the sieve of Eratosthenes, brute force or any other way. We will get 25 primes from 1 to 100.

It can be understood that it makes no sense to make a query with the number $$$x$$$ if there are numbers greater than 100 in its decomposition into primes or the power of any of the primes exceeds 1.

Note that since $$$n$$$ is a prime number, if we want to check whether the number $$$n$$$ is some kind of prime number $$$x$$$ or $$$y$$$, we can check whether the number $$$x\times y$$$ is divisible by $$$n$$$. If it is divisible, then $$$n$$$ is either a number $$$x$$$ or a number $$$y$$$. Thus, in one query we can find out information whether $$$n$$$ is a number $$$x$$$ for several numbers $$$x$$$ at once.

Let's move on to the solution itself. Let's arrange all 25 primes from 1 to 100 in ascending order. And then you can apply a binpoisk. Initially, we assume that the number $$$n$$$ is in the segment from the first prime number to the last (from our list). Let's take a number $$$x$$$ equal to the product of the first half of our segment of prime numbers. Let's check with a query whether the number $$$n$$$ is included in this half of the segment. If it is included, we will shift the right border to the middle of the segment, otherwise the left one. And we will constantly reduce the segment by 2 times until we have only one number left. This number will be the answer.

It may seem that $$$x$$$ in some query may become more than $$$10^{18}$$$, but this is not the case: the product of the first half of the numbers is $$$7420738134810$$$, which is less than $$$10^{18}$$$. If we move the borders to the left, then the product will no longer be. If we shift to the right, we get the product of $$$15805487167$$$, which also fits the restrictions. Accordingly, the segments lying inside are also suitable, and on the right the product is $$$19657257924641$$$, and it is also less than $$$10^{18}$$$, which means the product of all subsequent segments of numbers is also less than $$$10^{18}$$$.

This means that the solution works and will make about $$$\log_2 25$$$ requests, that is, no more than $$$5$$$ requests.

The final asymptotics of the solution: $$$\mathcal{O}(1)$$$.

#include <bits/stdc++.h>
// #include "testlib.h"

using namespace std;
#define ll long long
#define vec vector

const ll INF = 1e9 + 7;
const ll NOT_INF = 1e9 + 7;
const string YES = "YES";
const string NO = "NO";

void rec(vec<int> v){
    ll L = 1;
    for(int i = 0; i < v.size() / 2 + v.size() % 2; i++){
        L *= v[i];
    }
    cout << "? " << L << '\n';
    cout.flush();
    int n; cin >> n;
    if (n){
        if (L == v[0]){ cout << "!" << " " << L; return;}
        else {
            vec<int> v4;
            for(int i = 0; i < v.size() / 2 + v.size() % 2; i++){
                v4.push_back(v[i]);
            }
            rec(v4);
            return;
        }
    }else {
        if (L == v[0]) {  cout << "!" << " " << v[1];}
        else {
            vec<int> v4;
            for(int i = v.size() / 2 + v.size() % 2; i < v.size(); i++){
                v4.push_back(v[i]);
            }
            rec(v4);
            return;
        }
    }
}

void test_case(){
    vector<int> v1 {
            2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43
    }, v2 {
            47, 53, 59, 61, 67, 71, 73, 79
    }, v3 {
            83, 89, 97
    };
    ll L = 1;
    for(auto i: v1){
        L *= i;
    }
    cout << "? " << L << '\n';
    cout.flush();
    int n; cin >> n;
    if (n){
        rec(v1);
    }else {
        L = 1;
        for (auto i: v2) {
            L *= i;
        }
        cout << "? " << L << '\n';
        cout.flush();
        cin >> n;
        if (n) {
            rec(v2);
        } else {
            rec(v3);
        }
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int t = 1;
    //cin >> t;
    while(t-->0){
        test_case();
    }
}

from functools import reduce
l, r, p = 0, 25, [*map(int, '2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97'.split())]
while r - l > 1:
    m = (l + r) // 2
    print('?', reduce(lambda x, y: x * y, p[l:m]))
    if input() == '1':
        r = m
    else: 
        l = m
print('!', p[l])

• Didn't solve
• Good task
• Average task
• Bad task

In the input data we have stops and for each of them the schedule of some $$$P$$$th bus. Then let's start a dictionary $$$a$$$, in which we will store the schedule for each $$$i$$$ stop, where the key will be the name of the stop, and the value will be an array of $$$a[i]$$$, which will consist of numbers denoting the schedule values in minutes (for convenience of using the data in later).

After converting the input data into a convenient way of using it, we need to answer $$$t$$$ queries, for which the answer is to find the nearest next flight of the $$$P$$$ bus for the $$$t_i$$$ stop at a given time.

Obviously, due to the possible large amount of data for each of the stops, sorting through and comparing the specified time with the schedule values for the current $$$t_i$$$ stop is by no means optimal, then binary search comes to our aid!

In order to implement a quick search for the nearest flight of the $$$P$$$ bus, we will need to initially sort the values of their schedules for each given $$$i$$$ stop. After that, responding to the $$$t_i$$$ request, we can search for the nearest next flight in the $$$a_{t_i}$$$ array using binary search, namely by applying a binary search algorithm called upper_bound through the array, which will return a reference to the value in minutes of the $$$P$$$ route we need. If the value of the result obtained belongs to $$$a_{t_i}$$$, then it remains to output the modulus of the difference between the specified and received time. Otherwise, output :(.

The resulting asymptotics of the solution: $$$\mathcal{O}(n \cdot q \cdot log \cdot q + t \cdot log \cdot q)$$$

#include <bits/stdc++.h>
//#include "testlib.h"

using namespace std;
#define ll long long
#define vec vector

const ll INF = 1e9 + 7;
const ll NOT_INF = 1e9 + 7;
const string YES = "YES";
const string NO = "NO";

void test_case(){
    ll n;
    cin >> n;
    map<string, vec<ll>> a;
    ll p = (ll)pow(10, 5);
    for(int i = 0; i < n; i++){
        string name; ll q;
        cin >> name >> q;
        while(q--){
            ll h, m;
            cin >> h >> m;
            a[name].push_back(h * p + m);
        }
    }
    for(auto &i: a){
        sort(i.second.begin(), i.second.end());
    }
//    for(auto &i: a){
//        cout << i.first << " ! ost\n";
//        for(auto j: i.second){
//            cout << "Schedule: " << j.h << " h. " << j.m << " m.\n";
//        }
//    }

    int t; cin >> t;
    while(t-->0){
        string name; ll h, w;
        cin >> name >> h >> w;
        auto mx = upper_bound(a[name].begin(), a[name].end(), h * p + w);
        if (mx != a[name].end()){
            // cout << *mx  << ' ' <<h * p + w<< '\n';
            cout << abs(*mx - (h * p + w)) << '\n';
        }else
            cout << ":(" << '\n';
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int test_c = 1;
    //cin >> test_c ;
    while(test_c-->0){
        test_case();
    }
}

• Didn't solve
• Good task
• Average task
• Bad task

The first thing that needed to be understood was the convenient principle of considering stations. It was not difficult to guess that one of the possible optimal solutions was to move from the station with the lowest load to the highest. Thus, it was enough to sort the array $$$a$$$ for subsequent actions ... (Also note that at the initial moment of time {by condition} the sum of the degrees of perturbation is $$$0$$$)

Further, in order to fully solve the problem, it is necessary to have solutions to its subtasks. Let's create an array of $$$dp$$$ for these purposes, in which we will store the smallest value of Ilya's perturbation after visiting the $i$th metro station. We will also introduce the notation:

Let's analyze the situation for $$$n\ =\ 1$$$, then it's not at all difficult to realize that Ilya will visit only one station and, accordingly, the degree of perturbation will be equal to one. Then the smallest sum of degrees will be equal to one. ($$$dp[1] = 1$$$)

Let's analyze the situation for $$$n\ =\ 2$$$, then we will consider two cases of changing the degree of perturbation of Ilya, namely:

• If the modulus of the difference between the congestion values of stations $$$a_1$$$ and $$$a_2$$$ is not greater than the value of the parameter $$$k$$$ ($$$|a_1 - a_2| \le k$$$), then after visiting these metro points, the total degree of disturbance for these stations will be equal to one. Then the smallest sum of the degrees of perturbation will be equal to one. ($$$dp[2] = 1$$$)

• Otherwise, for each of the stations, the degree of disturbance will be equal to one. Then, after visiting two stations, the degree of disturbance will be equal to two. ($$$dp[2] = 2$$$)

Let's analyze the situation for $$$n\ =\ 3$$$, then we will consider three cases of changing the degree of Ilya's perturbation, namely:

• If the difference between the maximum and minimum values of the segment $$$b\ = \ [a_1, a_2, a_3]$$$ does not exceed the value of the parameter $$$d$$$ ($$$b_{max} - b_{min} \le d$$$), then after visiting three metro stations, the total degree of disturbance of these stations will be equal to $$$1$$$. Then the smallest sum of degrees will be equal to one. ($$$dp[3] = 1$$$)

• Otherwise, if the modulus of the difference between the congestion values of stations $$$a_2$$$ and $$$a_3$$$ is not greater than the value of the parameter $$$k$$$ ($$$|a_2 - a_3| \le k$$$), then after visiting these metro stations, the total degree of disturbance of these stations will be equal to one. Then the smallest sum of powers will be equal to two ($$$dp[3] = 2$$$), since the following splitting into combinations will be obtained:

• Otherwise, the value of the degree of disturbance will increase by one and will be equal to $$$dp[3] = dp[2] + 1$$$. (Since we are also considering the value of $$$dp[2]$$$, which turned out when considering the first two elements of the sorted array $$$a$$$, based on the previous paragraph). Then we get the following combination:

To solve each subsequent subtask for which $$$n \gt 3$$$, we can safely use the default values of $$$dp[1],\ dp[2],\ dp[3]$$$. Thus, to determine the smallest sum of the degrees of perturbation of each subsequent $i$th subproblem, we need to consider the following effective combinations of obtaining the smallest sum of degrees:

• If the difference between the maximum and minimum values of the segment $$$b\ =\ [a_{i - 2}, a_{i - 1}, a_i]$$$ (visiting the last three stations) does not exceed the value of the parameter $$$d$$$ ($$$b_{max} - b_{min} \le d$$$), then consider the last two stations visited:

• • If the modulus of the difference between the congestion values of stations $$$a_{i - 1}$$$ and $$$a_{i}$$$ is not greater than the value of the parameter $$$k$$$ ($$$|a_{i - 1} - a_i| \le k$$$), then the value of the degree of disturbance for these metro points will be equal to one, and the smallest sum of degrees for the placed stations will be equal to $$$dp[i] = min(dp[i - 2] + 1, dp[i - 3] + 1)$$$.

• • Otherwise, for these metro points, the degree of disturbance will be equal to one, and the smallest sum of degrees for the stations visited will be equal to $$$dp[i] = dp[i - 3] + 1$$$ (It does not make sense to change the value of the degree of disturbance for each station separately for this case). The following combination of stations is obtained when measuring degrees:

• Otherwise, if the modulus of the difference between the station load values $$$a_{i - 1}$$$ and $$$a_{i - 2}$$$ is not greater than the value of the parameter $$$k$$$ ($$$|a_{i - 1} - a_{i - 2}| \le k$$$), then for of these metro points, the total degree of disturbance will be equal to one, and the smallest value of the sum of degrees for the current subtask is $$$dp[i] = dp[i - 2] + 1$$$. Thus we get the following combination:

• Otherwise, we consider the $$$i$$$-th station separately and the value of the degree of perturbation for it will be the only one, therefore the smallest value of the sum of degrees for the current subproblem is $$$dp[i] = dp[i - 1] + 1$$$. Thus we get the following combination:

After considering the final visited station, the final answer will be the value of $$$dp[n]$$$.

The resulting asymptotics of the solution: $$$\mathcal{O}(t\cdot(n\cdot log \cdot n +n))$$$

#include <bits/stdc++.h>
//#include "testlib.h"
using namespace std;
#define ll long long
#define vec vector

const ll INF = 1e9 + 7;
const string YES = "YES";
const string NO = "NO";

void test_case(int argc, char *argv[]){
    ll n, k, d; cin >> n >> k >> d;
    vec<ll> a(n);
    vec<ll> dp(n);
    cin >> a[0];
    for(int i = 1; i < n; i++){
        cin >> a[i];
    }
    sort(a.begin(), a.end());
    dp[0] = 1;
    if (n >= 2){
        if (abs(a[0] - a[1]) <= d){
            dp[1] = 1;
        }else {
            dp[1] = 2;
        }
    }
    if (n >= 3){
        if (abs(max(a[0], max(a[1], a[2])) - min(a[0], min(a[1], a[2]))) <= k){
            dp[2] = 1;
        }else if (abs(a[1] - a[2]) <= d){
            dp[2] = 2;
        }else {
            dp[2] = dp[1] + 1;
        }
    }
    if (n > 3){
        for(int i = 3; i < n; i++){
            if (max(a[i], max(a[i - 1], a[i - 2])) - min(a[i], min(a[i - 1], a[i - 2])) <= k){
                if (abs(a[i - 1] - a[i]) <= d) {
                    dp[i] = min(dp[i - 2] + 1, dp[i - 3] + 1);
                }else {
                    dp[i] = dp[i - 3] + 1;
                }
            }else if (abs(a[i - 1] - a[i]) <= d) {
                dp[i] = dp[i - 2] + 1;
            }else {
                dp[i] = dp[i - 1] + 1;
            }
        }
    }
    cout << dp[n - 1] << '\n';
}

int main(int argc, char *argv[]){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int t = 1; cin >> t;
    while(t-->0){
        test_case(argc, argv);
    }
}

• Didn't solve
• Good task
• Average task
• Bad task

More formally, in the problem it is necessary to find all natural numbers $$$n = 2 \times k^2 + 1$$$, where $$$k$$$ is a natural number, and $$$n$$$ is a palindrome. We can assume that there are not very many such numbers, and try to run a search for such numbers.

Iterating over the number $$$n$$$ will take too long, since $$$n$$$ can reach $$$10^{18}$$$. We need to come up with a better way. Note that since $$$n \le 10^{18}$$$, then $$$k \le \sqrt{\cfrac{10^{18} - 1}{2}}$$$, that is, $$$k$$$ does not exceed $$$10^9$$$. So, you can iterate over the number $$$k$$$ instead of $$$n$$$, calculate $$$n$$$ and check whether it is a palindrome.

Search asymptotics: $$$\mathcal{O}(\sqrt{N} \log{N})$$$, where $$$N$$$ is the maximum possible $$$n$$$, in our case $$$N = 10^{18}$$$. (We assume that checking whether a number is a palindrome is performed for its length, that is, for $$$\mathcal{O}(\log{N})$$$)

It may seem that this iteration will take quite a long time, but in practice it takes from 40 seconds to 15 minutes, depending on the programming language and the implementation of the algorithm.

As a result of the search, it can be understood that there are only numbers suitable for the condition of the problem 21: $$$3$$$, $$$9$$$, $$$33$$$, $$$99$$$, $$$393$$$, $$$969$$$, $$$38211283$$$, $$$91044019$$$, $$$95855859$$$, $$$357727753$$$, $$$10284648201$$$, $$$91637373619$$$, $$$93323232339$$$, $$$100083380001$$$, $$$3119172719113$$$, $$$100540454045001$$$, $$$302791646197203$$$, $$$982885848588289$$$, $$$9188622002268819$$$, $$$150434127721434051$$$, $$$355553961169355553$$$.

Now we know all the suitable numbers and that there are not so many of them. This means that we can write all these numbers as an array in the program code and then work with them without trying to count them every time we run.

There are different ways to respond to requests. You can search using bin search for the index of the minimum number that is not less than $$$l$$$ and the index of the minimum number that is greater than $$$r$$$. And then the answer is the difference of these indices. Then the asymptotics of the solution will be $$$\mathcal{O}(t \log{B})$$$, where $$$B$$$ is the number of suitable numbers, $$$B = 21$$$.

But you can do it easier, since we have only 21 numbers, for each request you can iterate over each number and check whether it lies in the required range. Then the asymptotics of the solution will be $$$\mathcal{O}(tB)$$$, where $$$B$$$ is the number of suitable numbers, $$$B = 21$$$.

There should probably be ways to optimize the iteration of numbers so that you can iterate over them right in the solution, before answering queries, or even find them all without iterating, but the task involves solving in the described way.

#include <bits/stdc++.h>
 
using namespace std;
typedef long long ll;
 
ll max_n = 1'000'000'000'000'000'000ll;
 
bool is_palindrome(ll x) {
    ll y = 0;
    for (ll t = x; t > 0; t /= 10) {
        y = 10 * y + t % 10;
    }
    return x == y;
}
 
int main() {
    for (ll x = 1, d = 3; 2 * x + 1 <= max_n; x += d, d += 2) {
        ll n = 2 * x + 1;
        if (is_palindrome(n)) {
            cout << n << "\n";
        }
    }
}

#include <bits/stdc++.h>
 
using namespace std;
typedef long long ll;
 
vector<ll> nums = {
        3ll, 9ll, 33ll, 99ll, 393ll, 969ll, 38211283ll, 91044019ll, 95855859ll,
        357727753ll, 10284648201ll, 91637373619ll, 93323232339ll, 100083380001ll,
        3119172719113ll, 100540454045001ll, 302791646197203ll, 982885848588289ll,
        9188622002268819ll, 150434127721434051ll, 355553961169355553ll
};
 
void solve() {
    ll l, r, ans = 0;
    cin >> l >> r;
 
    for (ll x: nums) {
        if (l <= x && x <= r) {
            ans++;
        }
    }
 
    cout << ans << "\n";
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
 
    ll t = 1;
    cin >> t;
    for (ll i = 0; i < t; ++i) {
        solve();
    }
}

• Didn't solve
• Good task
• Average task
• Bad task