реализация


Плюсануть
Поделиться
Класснуть
Запинить


Условие задачи ПрогрессПопытки, все/успешные
ID 91201. Сундук с секретом
Темы: математика    *1000    реализация   

На борту «Нулевого указателя» обнаружили старинный сундук с n рычагами. Чтобы открыть его, рычаги нужно нажимать в правильном порядке — но Шкипер Баг этого порядка не знает.

Когда Шкипер Баг нажимает рычаг: если этот рычаг действительно следующий в правильной последовательности — он остаётся нажатым. Если рычаг неправильный — он сбрасывается вместе со всеми уже нажатыми рычагами, и придётся начинать заново с нужного места.

Когда все n рычагов окажутся нажаты одновременно — сундук откроется. Шкипер Баг действует оптимально. Найдите количество нажатий в худшем случае.

Формат входных данных

Единственная строка: целое число n (1 ≤ n ≤ 2000) — количество рычагов.


Формат выходных данных

Одно число — количество нажатий в худшем случае.

 

Примечание (n = 3). Пусть правильная последовательность — {2, 3, 1}.

Шкипер Баг ищет первый рычаг. Нажимает рычаг 1 — сброс (1 нажатие). Нажимает рычаг 3 — сброс (2 нажатия). Нажимает рычаг 2 — остаётся нажатым (3 нажатия).

Теперь ищет второй рычаг. Нажимает рычаг 1 — сброс, рычаг 2 тоже сбросился (4 нажатия). Повторно нажимает рычаг 2 (5 нажатий), затем рычаг 3 — остаётся нажатым (6 нажатий).

Ищет третий рычаг. Единственный оставшийся — рычаг 1, нажимает (7 нажатий). Сундук открыт!

Итого в худшем случае: 7 нажатий.

 19/ 3
ID 91199. Корабельный архив
Темы: математика    *1000    реализация   

В трюме «Нулевого указателя» хранится стопка из n секретных свитков с морскими картами, пронумерованных от 1 до n. Сверху лежит свиток a1, под ним a2, и так далее. Все номера различны.

Капитан Архипов, не отрываясь от чая, выкрикивает номера нужных свитков. На i-м шаге он требует свиток bi. Если свиток ещё в стопке — Шкипер Баг снимает его вместе со всеми свитками выше (вытащить из середины нельзя — свитки слиплись от сырости). Если нужного свитка в стопке уже нет — Шкипер Баг делает умное лицо и ждёт следующей команды.

Посчитайте, сколько свитков Шкипер Баг достанет на каждом шаге.

Формат входных данных
Первая строка: n (1 ≤ n ≤ 200 000).

Вторая строка: n чисел ai — начальный порядок стопки (все различны).

Третья строка: n чисел bi — порядок требований капитана (все различны).

Формат выходных данных
n чисел — количество свитков, снятых на каждом шаге.


Примечание: 
В тестовом примере капитан потребовал свиток №2 — Шкипер Баг снял №1 и №2 сверху (2 штуки). Затем потребовал №1 — но его уже нет, ничего не происходит. Затем №3 — снял один.

 20/ 3
ID 91198. Зелье от морской болезни
Темы: Бинарный поиск    реализация    дп    *1100   

Шкипер Баг ужасно страдает от морской болезни. Единственное спасение — зелье «Штиль», которое продаётся в лавках на островах архипелага. На n островах цены разные: в i-м порту бутылка стоит xi дублонов.

Каждый раз, когда «Нулевой указатель» заходит в порт, у Шкипера Бага с собой разная сумма — зависит от того, не украл ли корабельный кот монеты из кармана. Всего таких заходов будет q. Для каждого захода Шкипер Баг хочет заранее знать: в скольких портах архипелага он смог бы купить зелье, имея столько дублонов?

Формат входных данных
Первая строка: n (1≤n≤100 000) — количество портов.
Вторая строка: n чисел  xi​ (1≤xi≤100 000) — цены на зелье.
Третья строка: q (1≤q≤100 000) — количество заходов в порт.
Следующие q строк: число mi​ (1≤mi≤109) — дублоны Шкипера Бага при i-м заходе.

Формат выходных данных
q чисел — для каждого захода количество портов, где хватит денег.


Примечание: 
При 1 дублоне ни одна лавка недоступна. При 8 — можно купить в 4 лавках (цены 2, 3, 4, 7). При 3 — только одна лавка (цена 2). При 100 дублонах — все пять.

 36/ 3
ID 84272. Сигналы со спутника
Темы: Задача на реализацию    реализация    сортировки    матрицы   

Космическая станция «Орион» принимает сигналы от спутников-разведчиков. Приёмная матрица станции имеет размер 640 строк на 480 позиций. При получении каждого сигнала в журнал записываются координаты активированного элемента матрицы: номер строки и номер позиции в строке.

Элемент матрицы, который принял хотя бы один сигнал, считается активным. Элемент, который не принял ни одного сигнала, считается неактивным.

Для анализа качества связи нужно найти наибольшую непрерывную цепочку активных элементов в одной строке.

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


Формат входных данных

В первой строке записано целое число N — количество принятых сигналов (1 ≤ N ≤ 10000).

В каждой из следующих N строк записаны по два числа через пробел:
- номер строки (целое число от 1 до 640)
- номер позиции в строке (целое число от 1 до 480)

Один и тот же элемент матрицы может получить несколько сигналов (координаты могут повторяться).

Формат выходных данных

Два целых числа через пробел: наибольшая длина цепочки активных элементов и номер строки, в которой она находится.
 

 14/ 5
ID 84271. Серверные стойки
Темы: Задача на реализацию    ЕГЭ_информатика    реализация    матрицы   

В новом датацентре «Кибер-Облако» серверы размещаются в стойках, которые расположены рядами. Ряды пронумерованы натуральными числами. Слоты в каждом ряду также пронумерованы натуральными числами начиная с единицы.

По данным инвентаризации известно, в каких рядах и в каких слотах уже установлены серверы. Администратору нужно разместить новое оборудование: кластер из ровно 25 серверов, которые должны располагаться в соседних слотах одного ряда.

Для надёжной работы кластера требуется, чтобы непосредственно слева и справа от него в том же ряду уже были установлены работающие серверы (они будут выполнять роль шлюзов).

Найдите ряд с наибольшим номером, в котором есть ровно 25 свободных слотов подряд, ограниченных занятыми слотами с обеих сторон.

Гарантируется, что существует хотя бы один ряд, удовлетворяющий условию.

Формат входных данных
В первой строке находится число N — количество установленных серверов (натуральное число, не превышающее 20000).

Каждая из следующих N строк содержит два натуральных числа, не превышающих 10000:
- номер ряда
- номер слота в этом ряду

Формат выходных данных

Два целых числа через пробел: наибольший номер ряда и наименьший номер слота в выбранной последовательности из 25 свободных мест.

 

 4/ 3
ID 84267. Набор в космическую академию
Темы: Массивы    ЕГЭ - вычислительные задачи    Задача на реализацию    реализация   

Космическая Академия «Звёздный Путь» проводит ежегодный набор курсантов. Отбор кандидатов происходит по сумме баллов трёх вступительных испытаний (физическая подготовка, математика, астронавигация) и собеседования с приёмной комиссией.

На заранее известное количество мест отбираются кандидаты, набравшие наибольшую сумму баллов по результатам трёх испытаний. Все кандидаты, набравшие определённую сумму баллов или больше, зачисляются на имеющиеся места. Такой балл называется проходным.

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

Из числа кандидатов, набравших полупроходной балл, на имеющиеся места принимаются кандидаты, имеющие более высокий балл за собеседование. Если два кандидата с полупроходным баллом имеют одинаковый балл за собеседование, то проходит тот кандидат, значение ID которого выше.

Для данного множества кандидатов определите полупроходной балл, а также ID кандидата с полупроходным баллом, который будет зачислен последним (займёт последнее свободное место).

Формат входных данных

В первой строке находятся два числа:

- N — количество кандидатов (натуральное число, не превышающее 10000)

- S — количество имеющихся мест (натуральное число, S ≤ N)

Каждая из следующих N строк содержит пять чисел:

- ID кандидата (натуральное число, не превышающее 10 000 000)

- три оценки по испытаниям (целые неотрицательные числа, не превышающие 100)

- балл за собеседование (целое неотрицательное число, не превышающее 10)

Гарантируется, что в исходных данных существует полупроходной балл.

 

Формат выходных данных

Два целых числа через пробел: полупроходной балл и ID кандидата с полупроходным баллом, занявшего последнее место.
 

Примечание

В первом тестовом примере

- ID=1001: сумма экзаменов = 270, собеседование = 10 → проходит (проходной балл)

- ID=1002: сумма = 240, собеседование = 8 → полупроходной балл, проходит

- ID=1003: сумма = 240, собеседование = 5 → не проходит (собеседование меньше)

- ID=1004: сумма = 210, собеседование = 10

Мест: 2. Кандидат с ID=1001 проходит автоматически. Осталось 1 место, но с суммой 240 — два кандидата. Это полупроходной балл. Между ними выбираем по собеседованию: ID=1002 (собес 8) > ID=1003 (собес 5).

Во втором тестовом примере
Все кандидаты имеют одинаковую сумму баллов (240) и одинаковый балл за собеседование (5). Мест: 2. Выбираем по ID в порядке убывания: сначала 503, затем 502. Последний зачисленный — кандидат с ID=502.

 

 1/ 1
ID 82123. Подводная станция
Темы: Массивы    ЕГЭ - вычислительные задачи    Задача на реализацию    реализация   

На подводной исследовательской станции «Нептун-7» требуется установить новый научный модуль. Станция состоит из M уровней (пронумерованных от 1 до M сверху вниз, где уровень 1 ближе всего к поверхности) и K отсеков на каждом уровне.

Некоторые отсеки уже заняты оборудованием. По требованиям безопасности, новый модуль нужно разместить так, чтобы над ним (на уровнях с меньшими номерами) было как можно больше подряд идущих свободных отсеков с тем же номером — это обеспечивает путь аварийной эвакуации к поверхности.

Если несколько отсеков имеют одинаковое максимальное количество свободных отсеков над ними, выбирается отсек на уровне ближе к поверхности (с меньшим номером уровня).

Гарантируется, что хотя бы один свободный отсек на станции существует.


Формат входных данных

В первой строке находятся три числа:

  • N — количество занятых отсеков (1 ≤ N ≤ 10 000)
  • M — количество уровней (1 ≤ M ≤ 100 000)
  • K — количество отсеков на каждом уровне (1 ≤ K ≤ 100 000)

В следующих N строках находятся пары натуральных чисел: номер уровня и номер отсека занятого места соответственно.


Формат выходных данных

Два целых числа через пробел:

  1. Номер уровня выбранного отсека
  2. Количество свободных отсеков над ним (подряд, с тем же номером)

 /
ID 82122. Космический техосмотр
Темы: Массивы    ЕГЭ - вычислительные задачи    Задача на реализацию    реализация   

На орбитальной станции «Галактика-7» завершился ежегодный технический осмотр космических кораблей. По его результатам каждый корабль получил:

  • Оценки трёх бортовых систем: двигательной, навигационной и системы жизнеобеспечения (по шкале от 2 до 5, где 2 — критическая неисправность, 5 — отличное состояние)
  • Статус лицензии пилота: действующая или просроченная

Корабль допускается к полётам, если выполнены оба условия:

  1. Все три бортовые системы имеют оценку 3 или выше
  2. Лицензия пилота действующая

Корабль не допущен к полётам, если хотя бы одно из условий не выполнено.

Руководство станции решило предоставить возможность экстренного ремонта одной системы одному из кораблей. Корабль может претендовать на ремонт, если:

  1. Лицензия пилота действующая
  2. Ровно одна система имеет критическую неисправность (оценка 2), а две другие системы исправны (оценка 3 или выше)

Если таких кораблей несколько, выбирается тот, у которого наибольшая сумма оценок всех трёх систем (такой корабль ближе всего к допуску).

Гарантируется, что ровно один корабль удовлетворяет всем критериям отбора.
 

Формат входных данных

В первой строке находится число N — количество кораблей (1 ≤ N ≤ 1000).

Каждая из следующих N строк содержит пять целых чисел через пробел:

  • ID — бортовой номер корабля (натуральное число, не превышающее 108)
  • S1, S2, S3 — оценки трёх бортовых систем (каждая от 2 до 5)
  • L — статус лицензии пилота (1 — действующая, 0 — просроченная)
 

Формат выходных данных

Выведите два числа через пробел:

  1. Количество кораблей, не допущенных к полётам
  2. Бортовой номер корабля, который получит возможность экстренного ремонта

 17/ 7