Программирование на С

Поход в гости

Условие

Мальчик Влад идет в гости к своему другу Васе, который живет в доме с N подъездами и M этажами. На каждом этаже каждого подъезда расположено одинаковое количество квартир. Влад помнит номер Васиной квартиры X (квартиры нумеруются с 1), но не помнит ни номер подъезда ни этаж.

Васин дом необычен тем, что домофоны в нем установлены не на входах в подъезды, а на каждом этаже. Поэтому Влад не может просто посмотреть, сколько квартир имеется на этаже. Вместо этого он может, поднявшись на какой-либо этаж в одном из подъездов, набрать номер Васиной квартиры на домофоне и по его сигналу определить, находится ли эта квартира на текущем этаже.

У Влада есть K предположений насчет того, какое количество квартир может быть на одном этаже одного подъезда. Влад собирается вычислить для каждого из K предположений номер подъезда и номер этажа, зайти в соответствующий подъезд, подняться на этаж и позвонить в домофон, чтобы проверить, живет ли здесь Вася. Перейти из одного подъезда в другой можно только через улицу (0 этаж). Влад может проверять свои предположения в любом порядке.

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

В примере 2 для 1-го и 2-го предположения Вася живет на 10 этаже 1 подъезда, в то время как для 3-го предположения Вася будет жить на 7 этаже 1 подъезда. Влад может сначала подняться на 7 этаж 1 подъезда для проверки 3-го предположения, а потом подняться на 10 этаж этого же подъезда для проверки предположений 1 и 2.

В примере 3 для 1-го предположения количество квартир в доме будет равно 40, а для 2-го предположения - 60. Ни в том, ни в другом случае в доме не найдется квартиры с номером 100.

Формат входного файла
Входной файл содержит целые числа N M X K - количество подъездов и этажей в доме Васи, номер его квартиры, количество предположений Влада. Далее следует K различных чисел a_i - предположения Влада о количество квартир на одном этаже одного подъезда дома Васи.

Формат выходного файла
Выходной файл должен содержать единственное целое число - минимальное количество этажей, на которые Владу необходимо будет подняться, чтобы точно определить, где живет Вася. Если ни одно предположение Влада не позволяет определить, где живет Вася, то выведите -1.

Ограничения
1 <= N, M <= 1e4, 1 <= X <= 1e6, 1 <= K <= 1e5, 1 <= a_i <= 1e5

Гармоничный забор

Условие

Марфа Геннадьевна попросила внука построить новый забор вдоль огорода. Внук выполнил просьбу бабушки и построил забор из N досок, в котором доска с номером i имела высоту a_i сантиметров.

Марфа Геннадьевна недавно прочитала книгу, в которой было написано, что гармоничным является забор, состоящий из чередующихся высоких и низких деревянных досок, то есть должно выполняться либо условие a_1 < a_2 > a_3 < a_4 >..., либо условие a_1 > a_2 < a_3 > a_4 < ...

Внук решил порадовать Марфу Геннадьевну и нарастить некоторые доски, чтобы сделать забор гармоничным. При этом ему хочется потратить поменьше древесины.

Напишите программу, которая по указанным длинам досок a_i определяет новый набор длин b_i, в котором:

a_i <= b_i;
либо b_1 < b_2 > b_3 < b_4 >..., либо b_1 > b_2 < b_3 > b_4 < ...;
сумма b_i минимальна.
Формат входного файла
Входной файл содержит целое число N за которым следует N чисел a_i - длины досок.

Формат выходного файла
Выходной файл должен содержать N целых чисел b_i - новые длины досок. Если существует несколько решений, выведите любое из них.

Ограничения
1 <= N <= 100, 1 <= a_i <= 100

Программист Вася и грибы

Условие

Юный программист Вася создал аркадную игру. В этой игре герой перемещается по горизонтальным платформам и может собирать грибы. Теперь Вася работает над редактором уровней для этой игры.

Уровень для игры кодируется прямоугольной таблицей символов из N строк и M столбцов. Свободные ячейки таблицы обозначаются символом '*' (ASCII 42).

Платформа - это набор последовательных ячеек из одной строки, который содержит лишь символы '#', и ограничен слева и справа границами уровня либо символами '.' или '*'.

Уровень всегда составлен таким образом, что над каждым символом '#' обязательно находится либо '.', либо '*'. Во втором случае будем говорить, что на этой платформе находится гриб. Под каждым символом '*' находится символ '#', т.е. грибы могут находиться только на платформах.

Васе предстоит реализовать аналитический модуль для редактора уровней. Одна из функций аналитического модуля - подсчет количества платформ, на которых находится хотя бы по одному грибу. Напишите программу, вычисляющую это количество.

В тестовом примере уровень содержит четыре платформы, на двух из которых есть грибы.

Формат входного файла
Первая строка входного файла содержит числа N M. Далее следует N строк по M символов в каждой - описание уровня.

Формат выходного файла
Выходной файл должен содержать единственное целое число - количество платформ, на которых находится хотя бы по одному грибу.

Ограничения
1 <= N, M <= 20