13. Задачи олимпиад

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

В будущем Вам придется изучить комбинаторику, теорию графов, динамическое программирование, численные методы. А пока решайте задачи на сайтах ACM.TIMUS.RU, ACM.SGU.RU и CONTEST.SAMARA.RU.

Внимательно читайте условия задачи, сторого соблюдайте форматы входных и выходных данных. Помните, что даже лишний пробел в выходных данных может стать причиной ошибки. Обязательно тестируйте свою программу не только на тестах, приведенных в условиях задачи, но и на собственных тестах, как можно более «вредных». При тестировании используйте текстовые файлы, даже если тестирующая программа не требует явного использования файлов. Так, например, сайты ACM.TIMUS.RU и ACM.SGU.RU не требуют явного использования файлов, а сайт CONTEST.SAMARA.RU пока требует. Но при автоматическом тестировании на сайте файлы, конечно, использоваться будут.

1. Задачи с сайта contest.Samara.Ru

   1. Тортики – 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».

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

Успехов!