logoChat01.ai

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

Créé le : 31 mars 2026

Répondu en utilisant GPT-5.4 Thinking par Chat01

Question

Имя входного файла: стандартный ввод
Имя выходного файла: стандартный вывод
Ограничение по времени: 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(32 + 1), x2(32 + 1), x3(32 + 1);
x1[0] = 0;
x2[0] = 1;
x3[0] = 2;
for (int i = 1; i <= 32; 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 <= 32; i++) {
if (x1[i] > r) {
break;
}
if (x1[i] >= l) ans++;
int rr = r - (x2[i] + x1[i] - 1);
int ll = l - (x2[i] + x1[i] - 1);
if (rr < 0) rr = 0;
if (ll < 0) ll = 0;
ans += min(rr / x3[i] + 1, x);
ans -= (ll / x3[i]);
// cout<< x << ":" << i << ":" << ans << "\n";
}
return ans;
};
int l1 = -1, r1 = r;
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

1
0 5 6

2:3
x x x x 2 x
0 1 0 2 1 3
*/
логига +- норм 1 тест проходит но не все тесты проходят найди ошибкку и покажи как и где исправить минимально меняя код

Python

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


[0,
 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]

Python

python
def mars(n):
    M=[0]
    for i in range(1,n+1):
        s=set(M[i//2:i])  # floor(i/2)
        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
from collections import defaultdict
M=mars(200)
pos=defaultdict(list)
for i,v in enumerate(M):
    pos[v].append(i)
for v in range(10):
    print(v, pos[v][:20], 'len',len(pos[v]))

Python

python
def code_ok(l,r,x):
    x1=[0]*33;x2=[0]*33;x3=[0]*33
    x1[0]=0;x2[0]=1;x3[0]=2
    for i in range(1,33):
        x2[i]=x2[i-1]*2
        x3[i]=x3[i-1]*2
        x1[i]=x3[i]-2
        if x1[i]>r: break
    ans=0
    for i in range(33):
        if x1[i]>r: break
        if x1[i]>=l: ans+=1
        rr=r-(x2[i]+x1[i]-1)
        ll=l-(x2[i]+x1[i]-1)
        if rr<0: rr=0
        if ll<0: ll=0
        ans+=min(rr//x3[i]+1, x)
        ans-= (ll//x3[i])
    return ans

def brute_count(l,r,x):
    M=mars(r)
    return sum(v<=x for v in M[l:r+1])

for l in range(0,10):
    for r in range(l,20):
        for x in range(0,6):
            a=code_ok(l,r,x)
            b=brute_count(l,r,x)
            if a!=b:
                print("mismatch",l,r,x,a,b)
                raise SystemExit
print("all ok small")

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

def code_ok(l,r,x):
    x1=[0]*33;x2=[0]*33;x3=[0]*33
    x1[0]=0;x2[0]=1;x3[0]=2
    for i in range(1,33):
        x2[i]=x2[i-1]*2
        x3[i]=x3[i-1]*2
        x1[i]=x3[i]-2
        if x1[i]>r: break
    ans=0
    for i in range(33):
        if x1[i]>r: break
        if x1[i]>=l: ans+=1
        rr=r-(x2[i]+x1[i]-1)
        ll=l-(x2[i]+x1[i]-1)
        if rr<0: rr=0
        if ll<0: ll=0
        ans+=min(rr//x3[i]+1, x)
        ans-= (ll//x3[i])
    return ans

M = mars(50)
for x in range(5):
    print("x=",x," code=",code_ok(0,0,x)," brute=",sum(v<=x for v in M[0:1]))
print("M[0..10]=",M[:11])

Python

python
def code_answer(l,r,j):
    lo=-1; hi=r
    while hi-lo>1:
        mid=(lo+hi)//2
        if code_ok(l,r,mid)>=j: hi=mid
        else: lo=mid
    return hi
queries=[(0,1,1),(1,4,2),(0,5,6),(0,4,4)]
for q in queries:
    l,r,j=q
    M=mars(r)
    arr=sorted(M[l:r+1])
    print(q, code_answer(*q), arr[j-1], arr)

Python

python
def brute_answer(l,r,k):
    M=mars(r)
    arr=sorted(M[l:r+1])
    return arr[k-1]
bad=[]
for l in range(0,20):
    for r in range(l,40):
        for k in range(1,r-l+2):
            a=code_answer(l,r,k)
            b=brute_answer(l,r,k)
            if a!=b:
                bad.append((l,r,k,a,b,sorted(mars(r)[l:r+1])))
                if len(bad)>=20: break
        if len(bad)>=20: break
    if len(bad)>=20: break
len(bad), bad[:10]


(20,
 [(0, 3, 4, 1, 2, [0, 0, 1, 2]),
  (0, 6, 6, 1, 2, [0, 0, 0, 1, 1, 2, 3]),
  (0, 6, 7, 2, 3, [0, 0, 0, 1, 1, 2, 3]),
  (0, 7, 6, 1, 2, [0, 0, 0, 1, 1, 2, 3, 4]),
  (0, 7, 7, 2, 3, [0, 0, 0, 1, 1, 2, 3, 4]),
  (0, 7, 8, 2, 4, [0, 0, 0, 1, 1, 2, 3, 4]),
  (0, 8, 6, 1, 2, [0, 0, 0, 1, 1, 2, 2, 3, 4]),
  (0, 8, 8, 2, 3, [0, 0, 0, 1, 1, 2, 2, 3, 4]),
  (0, 8, 9, 3, 4, [0, 0, 0, 1, 1, 2, 2, 3, 4]),
  (0, 9, 6, 1, 2, [0, 0, 0, 1, 1, 2, 2, 3, 4, 5])])

Python

python
l,r=0,3
for x in range(5):
    print(x, code_ok(l,r,x), brute_count:=sum(v<=x for v in mars(r)[l:r+1]))

Python

python
def contribs(l,r,x):
    x1=[0]*33;x2=[0]*33;x3=[0]*33
    x1[0]=0;x2[0]=1;x3[0]=2
    for i in range(1,33):
        x2[i]=x2[i-1]*2
        x3[i]=x3[i-1]*2
        x1[i]=x3[i]-2
        if x1[i]>r: break
    ans=0
    arr=[]
    for i in range(33):
        if x1[i]>r: break
        cur=0
        if x1[i]>=l: cur+=1
        rr=r-(x2[i]+x1[i]-1)
        ll=l-(x2[i]+x1[i]-1)
        if rr<0: rr=0
        if ll<0: ll=0
        cur+=min(rr//x3[i]+1, x)
        cur-= (ll//x3[i])
        arr.append((i,cur,x1[i],x2[i]+x1[i]-1,x3[i]))
        ans+=cur
    return ans,arr
for x in [0,1,2]:
    a,arr=contribs(0,3,x)
    print('x',x,'ans',a,arr)

Python

python
def count_correct(l,r,x):
    ans=0
    pw=1
    while pw<=r+2:
        a=(l+2 + pw -1)//pw
        b=(r+2)//pw
        lo=max(a,1)
        hi=min(b,2*x+1)
        if lo<=hi:
            ans += (hi+1)//2 - (lo//2)
        pw*=2
    return ans

for l in range(0,20):
    for r in range(l,40):
        M=mars(r)
        for x in range(0,10):
            b=sum(v<=x for v in M[l:r+1])
            c=count_correct(l,r,x)
            if b!=c:
                print("mismatch",l,r,x,b,c)
                raise SystemExit
print("all good")

Réflexion

Diagnosing the bug and improving the formula

The main issue seems to be with the formula inside the ok function. The current approach has an error related to the arithmetic progression count, especially how it assumes exactly x suitable indices per layer. I can simplify it by adjusting the formula and replacing the ok lambda, and I'll mention that r <= 1e9 makes the 32-bit limit fine.

Thought for 3m 44s

Réponse

Да, ошибка у тебя именно в ok(x).

Твоя идея с бинарным поиском по ответу нормальная, но функция ok(x) неправильно считает количество элементов <= x на отрезке.
Из-за этого бинарный поиск иногда уезжает в меньший ответ.

Где именно ломается

Например, возьмём отрезок [0, 3].

Марсианский ряд там такой:

cpp
M = [0, 1, 0, 2]

Отсортировано:

cpp
[0, 0, 1, 2]

Значит:

  • элементов <= 0 — 2
  • элементов <= 1 — 3

А твоя функция считает:

  • ok(0) = 2 — нормально
  • ok(1) = 4 — ошибка

То есть она уже для x = 1 думает, что на отрезке все 4 элемента не больше 1, хотя это не так (2 > 1).

Почему так происходит

Вот эта строка неверная:

cpp
ans += min(rr / x3[i] + 1, x);

Она предполагает, что на каждом “слое” количество подходящих значений ограничивается просто числом x,
но у марсианского ряда распределение значений устроено иначе.

Правильное свойство ряда

Для марсианского ряда верна формула:

cpp
Mi = (odd(i + 2) - 1) / 2

где odd(n) — нечётная часть числа n
(то есть делим n на 2, пока оно чётное).

Примеры:

  • i = 0: i + 2 = 2, нечётная часть 1, получаем 0
  • i = 3: i + 2 = 5, нечётная часть 5, получаем 2
  • i = 5: i + 2 = 7, нечётная часть 7, получаем 3

Значит условие

cpp
Mi <= x

равносильно

cpp
odd(i + 2) <= 2 * x + 1

Это уже можно корректно посчитать за O(log r).

Минимальная правка

Нужно заменить только ok.
Остальной код, включая бинарный поиск, можно оставить как есть.

Было

cpp
  auto ok = [&](int x) {
    int ans = 0;
    for (int i = 0; i <= 32; i++) {
      if (x1[i] > r) {
        break;
      }
      if (x1[i] >= l) ans++;
      int rr = r - (x2[i] + x1[i] - 1);
      int ll = l - (x2[i] + x1[i] - 1);
      if (rr < 0) rr = 0;
      if (ll < 0) ll = 0;
      ans += min(rr / x3[i] + 1, x);
      ans -= (ll / x3[i]);
    // cout<< x << ":" << i << ":" << ans << "\n";
    }
    return ans;
  };

Надо заменить на

cpp
  auto ok = [&](int x) {
    int ans = 0;
    int lim = 2 * x + 1;   // odd(i+2) <= lim

    for (int pw = 1; pw <= r + 2; pw <<= 1) {
      // ищем числа i, для которых i+2 = pw * t, где t нечётное
      int L = (l + 2 + pw - 1) / pw;   // ceil((l+2)/pw)
      int R = (r + 2) / pw;            // floor((r+2)/pw)

      L = max(L, 1LL);
      R = min(R, lim);

      if (L <= R) {
        // количество нечётных чисел на [L, R]
        ans += (R + 1) / 2 - L / 2;
      }
    }
    return ans;
  };

Полный код с минимальными изменениями

cpp
#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;

  auto ok = [&](int x) {
    int ans = 0;
    int lim = 2 * x + 1;

    for (int pw = 1; pw <= r + 2; pw <<= 1) {
      int L = (l + 2 + pw - 1) / pw;
      int R = (r + 2) / pw;

      L = max(L, 1LL);
      R = min(R, lim);

      if (L <= R) {
        ans += (R + 1) / 2 - L / 2;
      }
    }
    return ans;
  };

  int l1 = -1, r1 = r;
  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);

  int tests = 1;
  cin >> tests;
  while (tests--) {
    solve();
  }

  return 0;
}

Что именно я поменял

Только это:

  • выкинул неверный подсчёт в ok
  • оставил твой бинарный поиск без изменений
  • формат ввода/вывода и структура программы не тронуты

Проверка на примере из условия

Для входа:

cpp
4
0 1 1
1 4 2
0 5 6
0 4 4

получится:

cpp
0
1
3
1

что совпадает с примером.

Если хочешь, я могу ещё очень коротко расписать, почему формула Mi = (odd(i+2)-1)/2 верна, чтобы ты мог защитить это решение на разборе.

Partager cette Q&R