Задачи с сайта contest.samara.ru

Тортики – 1

Сегодня у Маши Петровой день рождения. Она пригласила в гости своих друзей и подруг - всего G человек. У нее есть K тортиков разного размера, которые она собирается разрезать так, чтобы все кусочки оказались (по размеру) одинаковыми. Маша уже придумала, как это можно сделать красиво. Осталось только выяснить, достанется ли хотя бы один кусочек какого-либо торта каждому из присутствующих.

Формат входного файла input.txt. Первая строка - два целых числа G и K через пробел (G - количество приглашенных гостей, 0<=G<=100, K - количество тортиков, 1<=K<=20).

Вторая строка - K целых чисел (1<=j1, j2, …, jK<=10) через пробел. Каждое из чисел jP обозначает, на какое количество кусочков Маша собирается разрезать тортик № P

Формат выходного файла output.txt. Первая строка: слово YES, если каждому из присутствующих достанется хотя бы один кусочек какого-либо торта, и слово NO, если это не так

Пример входного файла          Пример входного файла

10 2                                             5 1

4 7                                               4

Пример выходного файла       Пример выходного файла

YES                                             NO

Решение. Задача была предложена участникам окружной олимпиады школьников Самарской области по информатике в 2005 году. Задача очень простая и попытки сдать ее были предприняты на первых минутах соревнований. Но было много неудачных попыток, участники забыли, что присутствующие это не только приглашенные гости, но и сама Маша. Решайте и сдавайте самостоятельно. Помните, что за неудачные попытки, по правилам соревнований могут назначаться штрафные баллы. Найти эту задачу можно на сайте contest.samara.ru в пунктах «Соревнования» – «Окружная олимпиада 17.12.2005».

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

Успехов!

Высокие горы

Автор задачи: Рогачева Е.В.

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

Обозначим через E «запас сил» обоза. При подъеме в гору на единичную высоту обоз теряет 2*M «сил», а при спуске с такой же высоты - M «сил». Отдыхать обоз может только в «точках перевала» - либо после спуска перед подъемом, либо после подъема перед спуском. Обоз не может двигаться дальше, если до следующего перевала он должен потратить сил больше, чем имеется у него в запасе. За единицу времени он может восстановить V сил. Однако обоз не может набрать сил больше, чем Emax, сколько бы он ни отдыхал.

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

Формат входного файла input.txt.

Первая строка - целые числа N, E0, Emax, M, V через пробел.

N - количество точек «перевала» при движении обоза, 2 <= N <= 100. E0 - начальный запас сил обоза (0 <= E0 <= Emax), Emax - максимально возможный «запас сил» обоза (1 <= Emax <= 1000) M - количество сил, которое теряется при спуске с единичной высоты (0 <= M <= 1000), V - количество сил, которое восстанавливается за единицу времени при отдыхе (0 <= V <= 1000).

Вторая строка - целые числа h1, h2, …, hN через пробел - высоты, на которых расположены точки перевала (-1000 <= h1, h2, …, hN <= 1000).

Первое число соответствует точке, из которой обоз выезжает, последнее - месту назначения. Гарантируется, что во входном файле ни разу не встречаются два подряд одинаковых числа.

Формат выходного файла output.txt.

Первая строка - целое число T - минимальное время отдыха, которое потребуется обозу в пути или слово NO, если обоз не может проехать до места назначения с указанными ограничениями.

Пример входного файла            Пример выходного файла

3 13 15 3 2                                               1

Решение. Только 6 участников городского тура олимпиады 2006 Самары прошли все тесты и получили максимальное число баллов. Многие из тех, кто решил другие даже более сложные задачи, не сумел пройти все тесты для этой задачи.

Анализ показал, что в большинстве решений не учтено одно из условий задачи, а именно - V - количество сил, которое восстанавливается за единицу времени при отдыхе, может быть равно нулю(0 <= V <= 1000). Это означает, что если энергии для движения недостаточно, то при V=0 отдыхать бесполезно и нужно выдать в выходной файл 'NO'.

Второй особенностью является условие ограничение на Emax, даже при V>0 накопить энергию большую Emax нельзя. Учтите и это в своем решении. На сайте есть разбор задач и авторские решения. Но вы, зная особенности тестов, должны теперь самостоятельно решить и сдать решение.