logoChat01.ai

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

Tạo vào: 31 tháng 3, 2026

Trả lời bằng GPT-5.4 Thinking bởi Chat01

Câu hỏi

Имя входного файла: стандартный ввод
Имя выходного файла: стандартный вывод
Ограничение по времени: 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 (ll < 0) ll = 0;
if (rr <= 0) continue;
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 3 4

x x x x
0 1 0 2
*/

решение должно работать но 0 баллов что не так?

Python

python
def gen(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=gen(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 ok_func(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 ll < 0: ll = 0
        if rr <= 0: continue
        ans += min(rr // x3[i] + 1, x)
        ans -= (ll // x3[i])
    return ans

def brute_ans(l,r,k):
    arr=sorted(M[l:r+1])
    return arr[k-1]

def code_ans(l,r,k):
    l1=-1;r1=r
    while r1-l1>1:
        mid=(l1+r1)//2
        if ok_func(l,r,mid)>=k:r1=mid
        else:l1=mid
    return r1

bad=[]
for l in range(20):
    for r in range(l,40):
        for k in range(1,r-l+2):
            b=brute_ans(l,r,k)
            c=code_ans(l,r,k)
            if b!=c:
                bad.append((l,r,k,b,c))
                break
        if bad: break
    if bad: break
bad[:10], len(bad)


([(0, 7, 7, 3, 2)], 1)

Python

python
l,r,k=0,7,7
arr=sorted(M[l:r+1]); arr


[0, 0, 0, 1, 1, 2, 3, 4]

Python

python
for x in range(6):
    print(x, ok_func(0,7,x))

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
    res=[]
    for i in range(33):
        if x1[i]>r:
            break
        add=0
        if x1[i]>=l:
            add+=1
        rr = r - (x2[i] + x1[i] - 1)
        ll = l - (x2[i] + x1[i] - 1)
        if ll < 0: ll = 0
        if rr > 0:
            add += min(rr // x3[i] + 1, x)
            add -= (ll // x3[i])
        ans += add
        res.append((i,x1[i],x2[i],x3[i],add,ans))
    return res
contribs(0,7,2)


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

Python

python
def F(n,x):
    N=n+2
    T=2*x+1
    ans=-1
    s=0
    while (1<<s)<=N:
        U=N>>s
        ans += (min(T,U)+1)//2
        s+=1
    return ans
for n in range(20):
    for x in range(10):
        brute=sum(1 for i in range(n+1) if M[i]<=x)
        if F(n,x)!=brute:
            print("bad",n,x,F(n,x),brute)
            raise SystemExit
print("ok")

Suy nghĩ

Adjusting solution with binary search and optimizing performance

The solution involves binary searching for x in the range [0, r], then using a prefix sum calculation to evaluate count(x, l, r). Although the complexity is about O(log²(r) * q), which could lead to many operations, it's likely manageable in C++ with proper optimization (-O2). I'll proceed with providing the corrected code.

Thought for 3m 21s

Trả lời

У вас не “мелкий баг”, а неверная формула в ok(x). Поэтому код уверенно проходит какие-то локальные тесты, но на реальных падает полностью.

Самый короткий ответ: вы неправильно считаете количество элементов <= x на отрезке.

Контрпример очень маленький:

  • запрос: l = 0, r = 7, k = 7
  • первые значения ряда: 0, 1, 0, 2, 1, 3, 0, 4
  • после сортировки: 0, 0, 0, 1, 1, 2, 3, 4

7-й элемент равен 3.

Ваш код выводит 2, потому что считает, что на [0,7] чисел <= 2 ровно 7, хотя их на самом деле 6.

Где именно ошибка

Вот эта часть неверна:

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

Проблема не только в x vs x+1. У вас вообще неверно описаны позиции, на которых стоят значения.

Вы исходите из некоторой структуры с массивами:

cpp
x1[i] = ...
x2[i] = ...
x3[i] = ...

но для марсианского ряда она не такая.

Правильная структура ряда

Если выписать первые члены:

0, 1, 0, 2, 1, 3, 0, 4, 2, 5, 1, 6, 3, 7, 0, 8, ...

то видно точную формулу:

Mi=odd⁡(i+2)−12,M_i = \frac{\operatorname{odd}(i+2)-1}{2},

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

Например:

  • i = 6, i+2 = 8, нечётная часть 1, значит M_6 = 0
  • i = 11, i+2 = 13, нечётная часть 13, значит M_11 = 6

То есть условие

Mi≤xM_i \le x

эквивалентно

odd⁡(i+2)≤2x+1.\operatorname{odd}(i+2) \le 2x+1.

Как правильно считать count(<= x) на префиксе

Пусть нужно посчитать количество индексов i от 0 до n, для которых M_i <= x.

Рассмотрим j = i + 2, тогда j пробегает [2, n+2].

Нужно посчитать, сколько чисел j имеют нечётную часть <= 2x+1.

Если фиксировать степень двойки, то получаем формулу:

cpp
pref(n, x):
    N = n + 2
    T = 2*x + 1
    ans = -1
    for p = 1; p <= N; p *= 2:
        ans += (min(T, N / p) + 1) / 2

-1 нужен, чтобы вычесть фиктивное j = 1, которого у нас нет.

Тогда на отрезке [l, r]:

cpp
cnt(l, r, x) = pref(r, x) - pref(l - 1, x)

А дальше обычный бинарный поиск по ответу.

Почему ваш ok ломается

У вас неверно зашиты “слои”:

  • шаги идут не там, где вы считаете,
  • отдельно не обработан случай нечётных индексов,
  • и количество значений в классе тоже съехало.

Из-за этого ok(x) не является настоящим количеством элементов <= x, а значит бинарный поиск ищет не то.

Рабочее решение

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

using int64 = long long;

int64 pref(int64 n, int64 x) {
    if (n < 0) return 0;
    int64 N = n + 2;
    int64 T = 2 * x + 1;
    int64 ans = -1; // вычитаем j = 1

    for (int64 p = 1; p <= N; p <<= 1) {
        ans += (min(T, N / p) + 1) / 2;
    }
    return ans;
}

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

    int q;
    cin >> q;

    while (q--) {
        int64 l, r, k;
        cin >> l >> r >> k;

        int64 lo = -1, hi = r; // ответ точно не больше r
        while (hi - lo > 1) {
            int64 mid = (lo + hi) / 2;
            int64 cnt = pref(r, mid) - pref(l - 1, mid);
            if (cnt >= k) hi = mid;
            else lo = mid;
        }

        cout << hi << '\n';
    }

    return 0;
}

Проверка на примере

Ввод:

text
4
0 1 1
1 4 2
0 5 6
0 4 4

Вывод:

text
0
1
3
1

совпадает с условием.

Итог

Причина 0 баллов:

  • не таймлимит,
  • не long long,
  • не бинарный поиск,

а именно неправильная математика в ok(x).

Если хотите, я могу ещё отдельно разобрать, как вывести формулу

Mi=odd⁡(i+2)−12M_i = \frac{\operatorname{odd}(i+2)-1}{2}

из определения через MEX.

Chia sẻ Q&A này