situan4

21.04.2023 18:01 •  Информатика

ООЧЕНЬ НУЖЕН ПРОГРАММИСТ НА ПАСКАЛЕ ХОТЯ БЫ НА ОДНО ИЗ ЗАДАНИЙ Мишки Кеша и Тучка решили сделать на Лисичкин День рождения салют из n фейерверков. Они решили расставить фейерверки вдоль прямой с k различными лунками для фейерверков. В целях безопасности Кеша с Тучкой решили расставить фейерверки так, чтобы минимальное расстояние между ними было как можно больше. Однако для полной безопасности и этого недостаточно, так как если расстояние между двумя фейерверками меньше или равно 1, то они взрываются и могут поранить мишек. Вам нужно выяснить смогут ли Тучка с Кешей, соблюдая все правила безопасности, устроить салют из n фейерверков.
Входные данные
Первая строка содержит два целых числа k (2≤k≤104) и n (2≤n≤k) — число лунок для фейерверков и число фейерверков.
Вторая строка содержит k натуральных чисел xi, расположенных по возрастанию, — координаты позиций (xi≤109).
Выходные данные
Если мишки не смогут устроить салют, выведите «NO» (без кавычек). Иначе в первой строке выведите «YES» (без кавычек), а во второй строке выведите одно целое число — наибольшее минимальное возможное допустимое расстояние между двумя фейерверками.
Примеры
входные данные
4 4
1 3 5 7
выходные данные
YES
входные данные
2 2
3 4
выходные данные
NO

ЗАДАЧА 2
В Берляндском государственном университете есть студенческий буфет. Рассмотрим его работу в один из учебных дней.
Во всем университете n перемен, перед каждой из которых в буфет привозят ровно k булочек с маком (считаем, что в начале дня буфет пустой). Каждая булочка может храниться в буфете h перемен. В течение i-й перемены (1≤i≤n) в буфет приходят ровно ai студентов. Студенты приходят в буфет голодными, поэтому цель каждого из них — купить ровно одну булочку и стать сытым. Каждый студент может стоять в очереди за булочкой ровно один раз в день во время одной перемены. Сотрудник буфета работает с молниеносной скоростью, поэтому время продажи каждой булочки ничтожно мало и в условиях задачи роли не играет. Однако, если студенту не хватает булочки, он расстраивается и уходит голодным.
Определите минимальное количество студентов, которые останутся голодными.
Входные данные
Первая строка содержит три целых числа n, k, h (1≤n≤k≤105, 1≤h≤100) — количество перемен, количество булочек, привозимых в буфет перед каждой переменой, и срок хранения каждой булочки.
Вторая строка содержит n целых чисел ai (1≤ai≤105) — количество студентов, пришедших в буфет на i-й перемене.
Выходные данные
Выведите единственное целое число — минимальное количество студентов, которые останутся голодными.
Пример
входные данные
5 3 2
2 4 3 6 8
выходные данные
8

ЗАДАЧА 3
Сегодня Егор принимает участие в необычном турнире по шашкам.
В игре принимают участие два игрока, действия происходят на поле размером n×n клеток. Клетки поля окрашены в черный или белый цвет. Любые две соседние клетки, разделяющие сторону, имеют различный цвет. У каждого игрока в распоряжении имеется некоторое количество шашек определенного цвета (черного или белого). Начальная расстановка шашек произвольна (могут стоять на любых клетках). Пример размещения шашек на доске приведен на рисунке ниже.(рисунки приложенны)
Игроки ходят по очереди. Ход заключается в перемещении своей шашки на любую ближайшую клетку цвета, совпадающего с цветом клетки, на которой стоит рассматриваемая шашка (если эта клетка свободна).
Кроме того, в распоряжении игроков имеется операция взятия шашки противника. Егор может взять шашку соперника по следующим правилам:
Шашка соперника находится на одной из ближайших клеток цвета, совпадающего с цветом клетки, на которой стоит шашка Егора.
Шашка Егора может «перепрыгнуть» шашку соперника, если в клетке, в которую попадет при этом шашка Егора, не стоит никакая другая шашка.
За один ход может быть выполнено несколько последовательных взятий, если выполняются вышеуказанные условия. При этом, пока ход не окончен, через уже взятые шашки больше нельзя «прыгать».
Цель игры — взять как можно большее количество шашек соперника.
В первой же партии что-то пошло не по плану. После сложного начала у Егора осталась всего одна шашка, а на доске возникла непростая ситуация. Егор совсем не хочет проиграть в самом начале. Поэтому ему нужно понять, какое наименьшее и наибольшее количество шашек соперника он может взять за один ход, играя по вышеуказанным правилам?
примеры
входные данные
8
0##
#0###00#


##0#0###
1##
##0#0#0#

выходные данные
1 5
входные данные
8
#0
0##
##0
###0
1###

##0###0#

выходные данные
0 0