Сбалансированный класс

@Yaroslaw_Winlot · Регистрация: 15.05.2023

Студворк — интернет-сервис помощи студентам

Дан набор из n
ребят. Необходимо набрать "Е" класс из этих ребят. Однако нам важно, чтобы все чувствовали себя комфортно, поэтому необходимо сделать сбалансированный класс.

Уровень знаний i
-го ребенка равна ai
. Гарантируется, что все уровни различны и заданы в возрастающем порядке.

Класс, который вы хотите собрать, должен быть подмножеством ребят из заданного набора. Чтобы класс оказался сбалансированный, должно быть соблюдено только одно условие: для каждого учащегося, кроме самого сильного (ученик с максимальным уровнем знаний), должен быть учащийся с уровнем знаний больше уровня знаний этого учащегося, но не больше, чем удвоенный уровень этого учащегося. Другими словами, пусть ai1,ai2,…,aip
— уровень знаний ученика в собранном классе в возрастающем порядке. Тогда для каждого j
от 1
до p−1
должно выполняться a_ij+1≤a_ij⋅2
. Это означает, что класс, состоящий из одного ученика всегда является сбалансированным.

Среди всех Е классов, удовлетворяющих ограничению, описанному выше, вы хотите собрать Е класс, содержащий максимальное количество ребят. Вам необходимо найти это количество ребят.

Входные данные
Первая строка входных данных содержит одно целое число n
(1≤n≤2⋅10⁵
) — количество ребят в изначальном множестве.

Вторая строка входных данных содержит n
целых чисел a¹,a²,…,aⁿ
(1≤a_i≤10⁹
) — уровни знаний этих ребят. Гарантируется, что уровни различны и заданы в возрастающем порядке.

Выходные данные
Выведите одно целое число — максимальное количество ребят в Е классе, удовлетворяющем ограничению, описанному в условии задачи.

Примеры
входные данные
10
1 2 5 6 7 10 21 23 24 49
выходные данные
4
входные данные
5
2 10 50 110 250
выходные данные
1
входные данные
6
4 7 12 100 150 199
выходные данные
3

@Red white socks · 17.06.2023, 17:35

Yaroslaw_Winlot, вот вы пишите:

Сообщение от Yaroslaw_Winlot

Вторая строка входных данных содержит n
целых чисел a1,a2,…,an
(1≤ai≤109)

А затем приводите входные данные

Сообщение от Yaroslaw_Winlot

входные данные
5
2 10 50 110 250

Я не доктор физ-мат наук, но мне кажется, что 250 > 109, что противоречит условию.

@idealist · 17.06.2023, 17:59

Сообщение от Red white socks

Yaroslaw_Winlot, вот вы пишите:

Вторая строка входных данных содержит n
целых чисел a1,a2,…,an
(1≤ai≤109)

Ну, здесь модно 10⁹ писать как 109...

YuS_2 · 17.06.2023, 18:03

Сообщение от Red white socks

что противоречит условию.

надо делать скидку на малограмотность пользователей (ну а чем ещё объяснить их нежелание что-либо читать?)...
там не 109, а 10⁹

@Red white socks · 18.06.2023, 11:20

Сообщение от YuS_2

надо делать скидку на малограмотность пользователей

Больше удручает не малограмотность, а отсутствие хоть какой-то заинтересованности.

@eaa · 18.06.2023, 11:35

Сообщение от Red white socks

отсутствие хоть какой-то заинтересованности

ну задача не сложная, наверное где-то уже списал или дедлай уже прошел.

@idealist · 27.08.2023, 00:13

Python
1
2
3
4
5
6
7
8
9
10
11
n = int(input('n = '))
arr = [int(k) for k in input('->').split()]
res = 0
i_prev = 0
for i in range(n-1):
    if arr[i] * 2 < arr[i+1]:
        i_cur = i+1
        res = max(res, i_cur - i_prev)
        i_prev = i_cur
res = max(res, n - i_prev)
print(res)

Новые блоги и статьи Все статьи Все блоги /
Камера Toupcam IUA500KMA Eddy_Em 12.02.2026 Т. к. у всяких "хикроботов" слишком уж мелкий пиксель, для подсмотра в ESPriF они вообще плохо годятся: уже 14 величину можно рассмотреть еле-еле лишь на экспозициях под 3 секунды (а то и больше),. . .	И ясному Солнцу zbw 12.02.2026 И ясному Солнцу, и светлой Луне. В мире покоя нет и люди не могут жить в тишине. А жить им немного лет.	«Знание-Сила» zbw 12.02.2026 «Знание-Сила» «Время-Деньги» «Деньги -Пуля»	SDL3 для Web (WebAssembly): Подключение Box2D v3, физика и отрисовка коллайдеров 8Observer8 12.02.2026 Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами и вызывать обработчики событий столкновения. . . .
SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL_LoadPNG (без SDL3_image) 8Observer8 11.02.2026 Содержание блога Библиотека SDL3 содержит встроенные инструменты для базовой работы с изображениями - без использования библиотеки SDL3_image. Пошагово создадим проект для загрузки изображения. . .	SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL3_image 8Observer8 10.02.2026 Содержание блога Библиотека SDL3_image содержит инструменты для расширенной работы с изображениями. Пошагово создадим проект для загрузки изображения формата PNG с альфа-каналом (с прозрачным. . .	Установка Qt-версии Lazarus IDE в Debian Trixie Xfce volvo 10.02.2026 В общем, достали меня глюки IDE Лазаруса, собранной с использованием набора виджетов Gtk2 (конкретно: если набирать текст в редакторе и вызвать подсказку через Ctrl+Space, то после закрытия окошка. . .	SDL3 для Web (WebAssembly): Работа со звуком через SDL3_mixer 8Observer8 08.02.2026 Содержание блога Пошагово создадим проект для загрузки звукового файла и воспроизведения звука с помощью библиотеки SDL3_mixer. Звук будет воспроизводиться по клику мышки по холсту на Desktop и по. . .

@Yaroslaw_Winlot 0 / 0 / 0 Регистрация: 15.05.2023 Сообщений: 5

	Сбалансированный класс 16.06.2023, 13:15. Показов 765. Ответов 6 Метки нет (Все метки) Дан набор из n ребят. Необходимо набрать "Е" класс из этих ребят. Однако нам важно, чтобы все чувствовали себя комфортно, поэтому необходимо сделать сбалансированный класс. Уровень знаний i -го ребенка равна ai . Гарантируется, что все уровни различны и заданы в возрастающем порядке. Класс, который вы хотите собрать, должен быть подмножеством ребят из заданного набора. Чтобы класс оказался сбалансированный, должно быть соблюдено только одно условие: для каждого учащегося, кроме самого сильного (ученик с максимальным уровнем знаний), должен быть учащийся с уровнем знаний больше уровня знаний этого учащегося, но не больше, чем удвоенный уровень этого учащегося. Другими словами, пусть ai1,ai2,…,aip — уровень знаний ученика в собранном классе в возрастающем порядке. Тогда для каждого j от 1 до p−1 должно выполняться a_ij+1≤a_ij⋅2 . Это означает, что класс, состоящий из одного ученика всегда является сбалансированным. Среди всех Е классов, удовлетворяющих ограничению, описанному выше, вы хотите собрать Е класс, содержащий максимальное количество ребят. Вам необходимо найти это количество ребят. Входные данные Первая строка входных данных содержит одно целое число n (1≤n≤2⋅10⁵ ) — количество ребят в изначальном множестве. Вторая строка входных данных содержит n целых чисел a¹,a²,…,aⁿ (1≤a_i≤10⁹ ) — уровни знаний этих ребят. Гарантируется, что уровни различны и заданы в возрастающем порядке. Выходные данные Выведите одно целое число — максимальное количество ребят в Е классе, удовлетворяющем ограничению, описанному в условии задачи. Примеры входные данные 10 1 2 5 6 7 10 21 23 24 49 выходные данные 4 входные данные 5 2 10 50 110 250 выходные данные 1 входные данные 6 4 7 12 100 150 199 выходные данные 3 0