A. Qurbaqa

A toshdan B toshga sakrashning imkoni bormi degan savolni quyidagicha o'zgartirsa bo'ladi: B toshga borish uchun A toshdan o'tiladimi? Buni aniqlash uchun uni ikkiga bo'lish kerak.

Python

for i in range(int(input())):
    a,b=map(int,input().split())
    while a<b:
      b=b//2
    if a==b:
        print("Yes")
    else:
        print('No')

c++

#include <iostream>
using namespace std;

int main(){
    long long t, a, b;
    cin >> t;
    for(int i=0; i<t; ++i){
        cin >> a >> b;
        while(b>a){
            b=b/2;
        }
        cout << (a==b ? "Yes" : "No") << "\n";
    }
}

B.  String.

Shartga ko'ra bizga satrning faqatgina uzunligi kerak. Demak ikkala satrdagi barcha harflar soni teng bo'lsa, satrlar albatta tenglashadi.

python

a=input()
b=input()
s=0
for i in range(97,123):
  s+=min(a.count(chr(i)),b.count(chr(i)))
print(s)

c++

#include <bits/stdc++.h>
using namespace std;
int main(){
    string s, t;
    cin >> s >> t;
    int ans = 0;
    for (char x = 'a'; x <= 'z'; x++) {
        int cnt = count(s.begin(), s.end(), x);
        cnt = min(cnt, (int)count(t.begin(), t.end(), x));
        ans += cnt;
    }
    cout << ans;
}

C. Hosil to'plash

Biz har bir qadamda hajmni 2 baravar orttirishimiz yoki shundayligicha qoldirishimiz mumkin. Har bir hajmni kamida bir martadan ishlatishga to'g'ri keladi. Bu degani biz har bir hajmdan 2 martadan ortiq foydalanmaymiz. Asos: 2 marta 8 ni ishlatish o'rniga 1 marta 16 ni ishlatish yaxshiroq.

python

x = int(input())
cnt = 0
d = 0
while x > 0:
    cnt += 1
    x -= pow(2, d)
    if x % pow(2, d+1) != 0:
        cnt += 1
        x -= pow(2, d)
    d += 1
print(cnt)

c++

#include <bits/stdc++.h>
using namespace std;
int main(){
    long long x; cin >> x;
    int cnt = 0;
    int d = 0;
    while(x > 0){
        cnt ++;
        x -= (1ll<<d);
        if(x % (1ll<<(d+1)) != 0){
            cnt ++;
            x -= (1ll<<d);
        }
        d ++;
    }
    cout << cnt;
}

D. K MEX

Ushbu masalada set yoki shunga o'xshash ma'lumotlar tuzilmasidan foydalanish mumkin edi, lekin ularni ta'qiqlash uchun vaqtni kamaytirdik. Masala faqatgina \(O(n)\) vaqtda yechilishi lozim. Agar mex nimaligini bilmasangiz bu saytdan o'qishingiz mumkin: https://cp-algorithms.com/sequences/mex.html

K ga karrali barcha sonlarni massivda index sifatida saqlaymiz va birinchi uchramagan K ga karrali sonni chop etamiz.

python

n, k = map(int, input().split())
a = [0]*int(1e6+5)
b = list(map(int, input().split()))
for x in b:
    if x % k == 0 and x // k < len(a):
        a[x//k] = 1
for i in range(1, len(a)):
    if a[i] == 0:
        print(i*k)
        break

c++

#include <iostream>
#include <vector>

using namespace std;
#define ll long long


int main(){
    cin.tie(nullptr)->sync_with_stdio(false);
    int n;
    long long k;
    cin >> n >> k;
    vector<int> a(1e6+5);
    long long x;
    for(int i = 0; i < n; ++i){
        cin >> x;
        if(x % k == 0 && x/k < a.size()) a[x/k] = 1;
    }
    for(int i = 1; i < a.size(); ++i){
        if(!a[i]){
            cout << k*i;
            return 0;
        }
    }
}

E. Robotlar

Vaqtim bo'sa to'ldirib qo'yaman :)

c++

#include <iostream>
#include <algorithm>
#include <vector>
#include <cassert>
using namespace std;

const int MAXN = 55;
const int MAXM = 4005;

struct Person {
    int from, to, budget;
    Person() {}
    Person(int from, int to, int budget) : from(from), to(to), budget(budget) {}
    bool operator<(const Person& otherPerson) const { return budget < otherPerson.budget; }
};

int n, m;
int pr[MAXN][MAXN][MAXM];
int dp[MAXN][MAXN][MAXM];
int opt[MAXN][MAXN][MAXM];
int result[MAXN];
vector<Person> people(MAXM);

void preprocess() {
    for (int i = m - 1; i >= 0; --i) {
        for (int from = 0; from < n; ++from) {
            for (int to = 0; to < n; ++to) {
                pr[from][to][i] = pr[from][to][i + 1];
            }
        }

        for (int from = 0; from <= people[i].from; ++from) {
            for (int to = people[i].to; to < n; ++to) {
                pr[from][to][i]++;
            }
        }
    }
}

int compute(int from, int to, int priceIdx) {
    if (from > to) return 0;
    if (dp[from][to][priceIdx] != -1) return dp[from][to][priceIdx];

    int resval = 0;
    int bestPosition = from;

    for (int pos = from; pos <= to; ++pos) {
        int lres = compute(from, pos - 1, priceIdx);
        int rres = compute(pos + 1, to, priceIdx);
        int peopleCount = pr[from][to][priceIdx];

        if (pos - 1 >= from) peopleCount -= pr[from][pos - 1][priceIdx];
        if (pos + 1 <= to) peopleCount -= pr[pos + 1][to][priceIdx];

        int currentRes = lres + rres + peopleCount * people[priceIdx].budget;

        if (currentRes > resval) {
            resval = currentRes;
            bestPosition = pos;
        }
    }

    if (priceIdx + 1 < m) {
        int nextRes = compute(from, to, priceIdx + 1);
        if (nextRes > resval) {
            resval = nextRes;
            bestPosition = -1;
        }
    }

    dp[from][to][priceIdx] = resval;
    opt[from][to][priceIdx] = bestPosition;

    return resval;
}

void reconstruct(int from, int to, int priceIdx) {
    if (from > to) return;
    if (priceIdx >= m) return;

    if ((from == to) && (opt[from][to][priceIdx] == from)) {
        result[from] = priceIdx;
        return;
    }

    int bestPosition = opt[from][to][priceIdx];

    if (bestPosition == -1) {
        reconstruct(from, to, priceIdx + 1);
    } else {
        result[bestPosition] = priceIdx;
        reconstruct(from, bestPosition - 1, priceIdx);
        reconstruct(bestPosition + 1, to, priceIdx);
    }
}

int main() {
    cin >> n >> m;

    for (int i = 0; i < m; ++i) {
        int from, to, budget;
        cin >> from >> to >> budget;
        --from;
        --to;
        people[i] = Person(from, to, budget);
    }

    sort(people.begin(), people.begin() + m);

    preprocess();

    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            for (int k = 0; k < m; ++k) {
                dp[i][j][k] = -1;
            }
        }
    }

    cout << compute(0, n - 1, 0) << endl;

    reconstruct(0, n - 1, 0);

    for (int i = 0; i < n; ++i) {
        cout << people[result[i]].budget << ' ';
    }

    return 0;
}