--->
232 задач
<---
Источники
Дан двумерный массив целых чисел n × m, все элементы которого — нули или единицы. Найти в нём наибольший по площади квадрат, состоящий только из единиц. Гарантируется, что в нём есть хотя бы одна единица.
Вводятся два целых числа n и m (1 ≤ n, m ≤ 1000), а потом n строк по m чисел 0 или 1 — элементы массива.
Вывести три числа — длину стороны квадрата и координаты его левого верхнего угла.
1 1 1
1 1 1
3 5 1 1 0 0 0 1 1 1 1 1 0 0 0 1 1
2 1 1
Каждый день к Грегори Хаусу приходит много больных, и у каждого измеряется уровень гемоглобина в крови. Данные по всем пациентам заносятся в базу данных.
Но волчанка попадается один раз на миллион, а работать с остальными неинтересно. Чтобы Хаус не выгонял больных, Кадди иногда запрашивает статистику по k последним больным: ей хочется знать сумму их уровня гемоглобина.
Также Хаус — мизантроп: он смотрит уровень гемоглобина больного, который поступил к нему позже всех, и, видя, что это точно не волчанка, выписывает его из больницы и удаляет информацию о нем из базы.
Автоматизацию процесса Хаус поручил Чейзу. Но Чейз почему-то не справился с этой задачей и попросил вас ему помочь.
Первой строкой входного файла задано число n ( 1 ≤ n ≤ 100000 ) — число обращений к базе данных. Запросы к базе выглядят следующим образом: + x ( 1 ≤ x ≤ 10 9 ) — добавить пациента с уровнем гемоглобина x в базу, - — удалить последнего пациента из базы, ? k ( 1 ≤ k ≤ 100000 ) — вывести суммарный гемоглобин последних k пациентов. Гарантируется, что k не превосходит число элементов в базе. Также гарантируется, что запросов на удаление к пустой базе не поступает. Перед началом работы база данных пуста.
Для каждого запроса " - " вывести уровень гемоглобина в крови пациента, а для каждого запроса " ? k " — суммарный гемоглобин у последних k поступивших пациентов. Ответы выводите в порядке поступления запросов.
7 +1 +2 +3 ?2 - - ?1
5 3 2 1
Имеется 10 колб с водой и известен объем воды в каждой из них. За одно “касание” можно взять одну колбу и часть воды (или всю воду) из этой колбы разлить по одной или нескольким другим колбам в любом количестве. За какое наименьшее количество “касаний” можно уравнять объемы воды во всех колбах? Каждая колба может вместить любой объем воды.
Программа получает на вход 10 целых чисел \(a_i\), каждое записанное в отдельной строке \(--\) объем воды в каждой из колб. Все числа — целые, от 0 до 100.
Выведите одно целое число — минимальное количество “касаний”, за которое можно уравнять объемы воды во всех колбах.
30 26 2 3 4 5 6 7 8 9
2
Имеется 4-мерный массив X, каждый индекс которого может принимать значения от 1 до N. Вы должны построить новый 4-мерный массив Y , элементы которого должны принимать следующие значения: \(Y\) [\(i_1\), \(i_2\), \(i_3\), \(i_4\)] = min(\(X\)[\(j_1\), \(j_2\), \(j_3\), \(j_4\)]), где 1 \(\le\) \(i_k\) \(\le\) \(N\) − \(M\) + 1, \(i_k\) \(\le\) \(j_k\) \(\le\) \(i_k\) + \(M\) − 1, а \(M\) - заданное число.
В первой строке входного файла задаются \(N\) и \(M\) (\(1\) \(\le\) \(M\) \(\le\) \(N\)). Остальные строки файла содержат элементы массива \(X\). Количество элементов не будет превышать 1500000 и сами они будут целыми числами, не превышающими по абсолютному значению \(10^9\). Они расположены в таком порядке, что считать их можно с помощью псевдокода:
for i = 1 to N:Выведите искомый массив \(Y\) в том же формате, в котором был дан массив \(X\).
1 1 1
1
3 2 3 1 4 -4 0 4 0 0 -3 0 -2 -5 5 3 5 -4 4 -3 -5 -4 -4 5 -1 0 -3 -2 -1 2 -5 -5 -1 1 1 -4 3 5 3 -3 -3 3 0 1 4 -1 -2 3 -2 5 4 -1 -5 3 -4 0 -3 -1 3 -1 4 4 -1 -5 -3 4 -4 5 1 5 -4 3 2 2 -2 -2 4 2 -4 -3 1 3 1
-5 -5 -4 -3 -5 -5 -4 -5 -5 -5 -5 -5 -4 -5 -4 -5
У бизнесмена есть телефон, который он использует для связи с партнерами по бизнесу. Сегодня у предпринимателя запланировано n разговоров, про каждый из которых известно число Pi — сколько рублей прибыли получит бизнесмен, если i-й разговор состоится (Pi может быть равно 0 — в этом случае никакой выгоды от i-го разговора нет).
Телефон у бизнесмена сделан по новейшим технологиям, но иногда барахлит. Сегодня, например, телефон внезапно разрядился, поэтому он позволит бизнесмену провести только первые A0 разговоров, а затем выключится до конца дня. Однако телефон можно зарядить, пропустив несколько первых запланированных разговоров. Более формально, если предприниматель будет заряжать телефон вместо первых j разговоров (то есть разговоров с номерами от 1 до j), то он потом сможет провести ровно Aj разговоров (с номерами от j + 1 до min(n, j + Aj)), после чего телефон опять же перестанет работать до конца дня.
Напишите программу, которая вычислит, сколько разговоров надо пропустить бизнесмену, чтобы заработать как можно больше. Если существует несколько ответов, то выведите тот, который требует большего времени зарядки, так как бизнесмену хочется отдохнуть подольше перед звонками.
На вход программе дается целое число n — количество запланированных звонков (1 ≤ n ≤ 2·105). На следующей строке вводятся через пробел \(n\) целых чисел Pi, обозначающие прибыли от звонков (0 ≤ Pi ≤ 1 000). Затем вводятся \(n+1\) целых чисел Aj, обозначающие, сколько звонков можно будет провести после подзарядки (0 ≤ Aj ≤ 106).
Выведите два числа, первое — это максимальная выгода, которую может получить бизнесмен, второе — количество пропущенных первых звонков, при котором она получается (0, если выгоднее всего не заряжать телефон вовсе).
5
1 2 0 4 1
2 0 8 3 5 6
5 3
Рассмотрим пример из условия: n = 5, P1 = 1, P2 = 2, P3 = 0, P4 = 4, P5 = 1, A0 = 2, A1 = 0, A2 = 8, A3 = 3, A4 = 5, A5 = 6.
Если бизнесмен не будет заряжать телефон, то результат будет равен P1 + P2 = 1 + 2 = 3 рубля. Если предприниматель будет заряжать телефон вместо первого звонка, то он не сможет позвонить ни разу, так как A1 = 0. Если вместо первых двух звонков, то результат составит P3 + P4 + P5 = 0 + 4 + 1 = 5 рублей. Если вместо первых трех, то P4 + P5 = 4 + 1 = 5. Если вместо четырёх звонков, то P5 = 1 рубль. Наконец, если бизнесмен будет заряжать телефон вместо всех n = 5 звонков, то он заведомо ничего не получит. Таким образом, два лучших варианта — это заряжать либо вместо 2 первых звонков, либо вместо 3, в обоих случаях получаем 5 рублей прибыли. По условию, из них мы выбираем выбираем вариант с 3 пропущенными звонками.
Тесты к этой задаче состоят из трех групп.