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

@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)

Новые блоги и статьи Все статьи Все блоги /
Ритм жизни kumehtar 27.02.2026 Иногда приходится жить в ритме, где дел становится всё больше, а вовлечения в происходящее — всё меньше. Плотный график не даёт вниманию закрепиться ни на одном событии. Утро начинается с быстрых,. . .	[В процессе разработки] SDL3 для Web (WebAssembly): Сборка библиотек SDL3 и Box2D из исходников с помощью CMake и Emscripten 8Observer8 27.02.2026 Недавно вышла версия 3. 4. 2 библиотеки SDL3. На странице официальной релиза доступны исходники, готовые DLL (для x86, x64, arm64), а также библиотеки для разработки под Android, MinGW и Visual Studio. . . .	SDL3 для Web (WebAssembly): Реализация движения на Box2D v3 - трение и коллизии с повёрнутыми стенами 8Observer8 20.02.2026 Содержание блога Box2D позволяет легко создать главного героя, который не проходит сквозь стены и перемещается с заданным трением о препятствия, которые можно располагать под углом, как верхнее. . .	Конвертировать закладки radiotray-ng в m3u-плейлист damix 19.02.2026 Это можно сделать скриптом для PowerShell. Использование . \СonvertRadiotrayToM3U. ps1 <path_to_bookmarks. json> Рядом с файлом bookmarks. json появится файл bookmarks. m3u с результатом. # Check if. . .
Семь CDC на одном интерфейсе: 5 U[S]ARTов, 1 CAN и 1 SSI Eddy_Em 18.02.2026 Постепенно допиливаю свою "многоинтерфейсную плату". Выглядит вот так: https:/ / www. cyberforum. ru/ blog_attachment. php?attachmentid=11617&stc=1&d=1771445347 Основана на STM32F303RBT6. На борту пять. . .	Камера Toupcam IUA500KMA Eddy_Em 12.02.2026 Т. к. у всяких "хикроботов" слишком уж мелкий пиксель, для подсмотра в ESPriF они вообще плохо годятся: уже 14 величину можно рассмотреть еле-еле лишь на экспозициях под 3 секунды (а то и больше),. . .	И ясному Солнцу zbw 12.02.2026 И ясному Солнцу, и светлой Луне. В мире покоя нет и люди не могут жить в тишине. А жить им немного лет.	«Знание-Сила» zbw 12.02.2026 «Знание-Сила» «Время-Деньги» «Деньги -Пуля»

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

	Сбалансированный класс 16.06.2023, 13:15. Показов 768. Ответов 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

Опции темы