logoChat01.ai

Имя входного файла: стандартный ввод Имя выходного...

Creado el: 31 de marzo de 2026

Respondido usando GPT-5.4 Thinking por Chat01

Pregunta

Имя входного файла: стандартный ввод
Имя выходного файла: стандартный вывод
Ограничение по времени: 2 секунды
Ограничение по памяти: 512 мегабайт
Марсианские профессора — настоящие мастодонты своего дела. Они завоевали не один десяток
наград во всевозможных сферах — от антропологии, биологии и социологии до физики и информатики. И сегодня марсианские ученые представляют научному комитету свою новую монументальную работу в области математики. Они изобрели концептуально новый вид последовательностей —
марсианский ряд !
Марсианский ряд обозначается буквой M. Первое число марсианского ряда равно M0 = 0. Число
Mi определяется как минимальное целое неотрицательное число, которое не встречается в марсианском ряду на отрезке от 
i
2

до i − 1 включительно. Более формально,
Mi = MEX
Mj по всем 
i
2

⩽ j ⩽ i − 1

,
где MEX — минимальное целое неотрицательное число, не представленное в данном множестве.
Комиссия с интересом выслушала доклад марсианских профессоров, после которого у неё появилось целых q вопросов. По забавному совпадению, все вопросы имели одинаковый формат:
«Подскажите, а если мы для некоторых l и r возьмём числа Ml
, Ml+1, . . . , Mr и отсортируем их
в порядке неубывания, какое число будет находиться на k-й позиции слева?»
Вопросы весьма интересны, однако из-за короткого периода концентрации внимания в будущем
марсианским профессорам отводится всего одна минута на весь доклад и ответы на вопросы, и они
боятся не успеть произвести все вычисления вовремя. Сможете ли вы им помочь?
Формат входных данных
В первой строке находится одно целое число q (1 ⩽ q ⩽ 105
) — количество вопросов от комиссии.
Далее следуют параметры вопросов.
В каждой из следующих q строк находятся три целых числа l, r и k (0 ⩽ l ⩽ r ⩽ 109
,
1 ⩽ k ⩽ r − l + 1) — параметры вопроса комиссии.
Формат выходных данных
Для каждого вопроса выведите одно целое число в отдельной строке — ответ на очередной вопрос
комиссии.
Страница 3 из 9
Заключительный этап республиканской олимпиады по учебному предмету «Информатика»
2 тур. Вариант 1., 2025/2026 учебный год
Система оценки
№ Дополнительные ограничения Баллы за подзадачу Необходимые подзадачи
1 q, l, r ⩽ 200 5
2 q, l, r ⩽ 2000 13 1
3 l, r ⩽ 2 · 105 17 1-2
4 Сумма по всем r − l + 1 ⩽ 106 20 1
5 k = r − l + 1 5
6 k = 1 17
7 k ⩽ 5 11 6
8 Нет дополнительных ограничений 12 1-7
Пример
стандартный ввод стандартный вывод
4
0 1 1
1 4 2
0 5 6
0 4 4
0
1
3
1
Замечание
Первые шесть значений марсианского ряда принимают следующие значения:
M0 = 0
M1 = MEX (M0) = MEX (0) = 1
M2 = MEX (M1) = MEX (1) = 0
M3 = MEX (M1, M2) = MEX (1, 0) = 2
M4 = MEX (M2, M3) = MEX (0, 2) = 1
M5 = MEX (M2, M3, M4) = MEX (0, 2, 1) = 3
Для второго вопроса из тестового примера последовательность элементов равна 1, 0, 2, 1. Если
отсортировать в порядке неубывания, то получим 0, 1, 1, 2. Число на второй позиции равно 1 — ответ
на соответствующий вопрос.
Для третьего вопроса из тестового примера последовательность элементов равна 0, 1, 0, 2, 1, 3.
Если отсортировать в порядке неубывания, то получим 0, 0, 1, 1, 2, 3. Число на шестой позиции равно
3 — ответ на соответствующий вопрос.

#include <bits/stdc++.h>
#define int long long

using namespace std;

using ll = long long;
const int N = 1e9 + 7;
const int C = 380;
const int B = 128;

void solve() {
int l, r, j;
cin >> l >> r >> j;
vector< int > x1(28 + 1), x2(28 + 1), x3(28 + 1);
x1[0] = 0;
x2[0] = 1;
x3[0] = 2;
for (int i = 1; i <= 28; i++) {
x2[i] = x2[i - 1] * 2;
x3[i] = x3[i - 1] * 2;
x1[i] = x3[i] - 2;
if (x1[i] > r) {
break;
}
}
auto ok = [&](int x) {
int ans = 0;
for (int i = 0; i <= 28; i++) {
if (x1[i] > r) {
continue;
}
if (x1[i] >= l) ans++;

text
  int rr = r - x2[i];
  int ll = l - x2[i];

  if (rr < 0) rr = 0;
  if (ll < 0) ll = 0;

  ans += (rr / x3[i]);
  ans -= (ll / x3[i]);
}
return ans;

};
int l1 = -1, r1 = r / 2;
while (r1 - l1 > 1) {
int mid = (l1 + r1) / 2;
if (ok(mid) >= j) r1 = mid;
else l1 = mid;
}
cout<< r1 << "\n";
}

int32_t main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
srand(time(0));
int tests = 1;
cin>>tests;
while (tests--) {
solve();
}

return 0;

}
/*
0-1-2
2-2-4
6-4-8
14-8-16
30-16-32
62-32-64
////////////////////
0 1 3 5 7 9
2 4 8
6 10
*/
идея 100% правельная но есть пару ошибок в коде напиши где они и как исправить

Python

python
def mars(n):
    M=[0]
    for i in range(1,n+1):
        s=set(M[i//2:i])
        x=0
        while x in s: x+=1
        M.append(x)
    return M
M=mars(100)
M[:40]


[0,
 1,
 0,
 2,
 1,
 3,
 0,
 4,
 2,
 5,
 1,
 6,
 3,
 7,
 0,
 8,
 4,
 9,
 2,
 10,
 5,
 11,
 1,
 12,
 6,
 13,
 3,
 14,
 7,
 15,
 0,
 16,
 8,
 17,
 4,
 18,
 9,
 19,
 2,
 20]

Python

python
def run_query(l,r,j):
    x1=[0]*29;x2=[0]*29;x3=[0]*29
    x1[0]=0;x2[0]=1;x3[0]=2
    for i in range(1,29):
        x2[i]=x2[i-1]*2
        x3[i]=x3[i-1]*2
        x1[i]=x3[i]-2
        if x1[i]>r: break
    def ok(x):
        ans=0
        for i in range(29):
            if x1[i]>r: continue
            if x1[i]>=l: ans+=1
            rr=r-x2[i]
            ll=l-x2[i]
            if rr<0: rr=0
            if ll<0: ll=0
            ans += (rr // x3[i])
            ans -= (ll // x3[i])
        return ans
    l1=-1;r1=r//2
    while r1-l1>1:
        mid=(l1+r1)//2
        if ok(mid)>=j: r1=mid
        else: l1=mid
    return r1

for q in [(0,1,1),(1,4,2),(0,5,6),(0,4,4)]:
    print(q,run_query(*q))

Python

python
def run_query_fix(l,r,j):
    x1=[0]*29;x2=[0]*29;x3=[0]*29
    x1[0]=0;x2[0]=1;x3[0]=2
    mx=0
    for i in range(1,29):
        x2[i]=x2[i-1]*2
        x3[i]=x3[i-1]*2
        x1[i]=x3[i]-2
        mx=i
        if x1[i]>r: break
    def ok(x):
        ans=0
        for i in range(mx+1):
            if x1[i]>x: break
            if x1[i]>=l: ans+=1
            rr=r-x2[i]
            ll=l-x2[i]
            if rr<0: rr=0
            if ll<0: ll=0
            ans += (rr // x3[i])
            ans -= (ll // x3[i])
        return ans
    l1=-1;r1=r
    while r1-l1>1:
        mid=(l1+r1)//2
        if ok(mid)>=j: r1=mid
        else: l1=mid
    return r1

for q in [(0,1,1),(1,4,2),(0,5,6),(0,4,4)]:
    print(q,run_query_fix(*q))

Python

python
def ceil_div(a,b):
    return -((-a)//b)
def count_leq(l,r,x):
    if x<0:return 0
    ans=0
    # t=0: n=2*y-1, y>=1
    lo=max(1, ceil_div(l+1,2))
    hi=min(x, (r+1)//2)
    if lo<=hi: ans += hi-lo+1
    t=1
    while (1<<t)-2 <= r:
        step=1<<(t+1)
        base=(1<<t)-2
        lo=max(0, ceil_div(l-base, step))
        hi=min(x, (r-base)//step)
        if lo<=hi: ans += hi-lo+1
        t+=1
    return ans

def kth(l,r,k):
    L=-1;R=r
    while R-L>1:
        m=(L+R)//2
        if count_leq(l,r,m)>=k: R=m
        else: L=m
    return R

for q in [(0,1,1),(1,4,2),(0,5,6),(0,4,4)]:
    print(q, kth(*q))

Pensamiento

Explaining bugs and providing corrections

I can show the bugs and corresponding fixes. First, ok(x) should reflect the real count formula instead of ignoring x, with positions derived from n = (2v + 1)2^t - 2. Second, fix the precompute break causing zeros, and third, correct the upper bound by using r1 = r. I might provide the corrected solve() function as well. Let me share concise C++ code.

Thought for 6m 52s

Respuesta

Да, идея у тебя по сути правильная, но в коде есть 3 реальные ошибки.

1. ok(x) вообще не использует x

Сейчас функция

cpp
auto ok = [&](int x) {
    ...
};

возвращает одно и то же значение для любого x, потому что внутри x нигде не участвует.
Из-за этого бинарный поиск не имеет смысла.

То есть вот это:

cpp
if (ok(mid) >= j) r1 = mid;
else l1 = mid;

не может работать корректно, пока ok(mid) не считает именно
“сколько чисел на отрезке [l, r] не превосходят mid”.

2. После break у тебя хвост массивов остаётся нулевым

Вот тут:

cpp
for (int i = 1; i <= 28; i++) {
    x2[i] = x2[i - 1] * 2;
    x3[i] = x3[i - 1] * 2;
    x1[i] = x3[i] - 2;
    if (x1[i] > r) {
      break;
    }
}

после break элементы x2[i], x3[i], x1[i] для больших i остаются равны 0.

А потом в ok ты делаешь цикл до 28:

cpp
for (int i = 0; i <= 28; i++) {

и попадаешь на x3[i] == 0, после чего будет деление на 0:

cpp
ans += (rr / x3[i]);
ans -= (ll / x3[i]);

Как исправить

Либо запоминай последний валидный индекс, либо делай break и в ok тоже итерируйся только по валидным i.

Например:

cpp
int m = 0;
for (int i = 1; i <= 28; i++) {
    x2[i] = x2[i - 1] * 2;
    x3[i] = x3[i - 1] * 2;
    x1[i] = x3[i] - 2;
    m = i;
    if (x1[i] > r) break;
}

и потом:

cpp
for (int i = 0; i <= m; i++) {
    ...
}

3. Правая граница бинарного поиска r / 2 неверная

У тебя:

cpp
int l1 = -1, r1 = r / 2;

Но ответ вполне может быть больше r / 2.

Простейший пример:

  • l = 1, r = 1, k = 1
  • на отрезке только M1 = 1
  • ответ = 1

А ты ищешь только в диапазоне [-1, 0].

Как исправить

Нужно брать безопасную правую границу, например:

cpp
int l1 = -1, r1 = r;

Ещё маленький момент

Если бы массивы были инициализированы корректно, то здесь логичнее break, а не continue:

cpp
if (x1[i] > r) {
    continue;
}

так как x1[i] возрастает. То есть дальше смысла идти уже нет.

Что лучше сделать

Тут проще не латать старый ok, а сразу заменить его на корректный подсчёт.

У этого ряда есть удобная формула:

  • значение v встречается в позициях
    n = (2v + 1) * 2^t - 2

Из неё можно посчитать, сколько чисел <= x лежит на [l, r], а потом уже делать бинарный поиск по ответу.

Вот рабочая версия solve():

cpp
#include <bits/stdc++.h>
using namespace std;

using int64 = long long;

int64 ceil_div(int64 a, int64 b) { // b > 0
    if (a >= 0) return (a + b - 1) / b;
    return a / b; // в C++ деление отрицательных к 0, это и есть ceil для a<0
}

int64 count_leq(int64 l, int64 r, int64 x) {
    if (x < 0) return 0;
    int64 ans = 0;

    // t = 0: n = 2*v - 1, v >= 1
    {
        int64 L = max<int64>(1, ceil_div(l + 1, 2));
        int64 R = min<int64>(x, (r + 1) / 2);
        if (L <= R) ans += R - L + 1;
    }

    // t >= 1: n = v * 2^(t+1) + 2^t - 2, v >= 0
    for (int t = 1; t <= 30 && ((1LL << t) - 2 <= r); t++) {
        int64 base = (1LL << t) - 2;
        int64 step = (1LL << (t + 1));

        int64 L = max<int64>(0, ceil_div(l - base, step));
        int64 R = min<int64>(x, (r - base) / step);

        if (L <= R) ans += R - L + 1;
    }

    return ans;
}

void solve() {
    int64 l, r, k;
    cin >> l >> r >> k;

    int64 L = -1, R = r;
    while (R - L > 1) {
        int64 mid = (L + R) / 2;
        if (count_leq(l, r, mid) >= k) R = mid;
        else L = mid;
    }

    cout << R << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int q;
    cin >> q;
    while (q--) solve();
    return 0;
}

Если хочешь, я могу ещё отдельно объяснить, откуда берётся формула n = (2v+1) * 2^t - 2.

Compartir este Q&A