Задание школьного этапа Всероссийской олимпиады школьников 9-11

ВСЕРОССИЙСКАЯ ОЛИМПИАДА ШКОЛЬНИКОВ

ПО ИНФОРМАТИКЕ 2019-2020 учебный год

ШКОЛЬНЫЙ ЭТАП

ЗАДАНИЯ 9-11 КЛАССЫ

Задача 1 (15 баллов)

Дорожка замощена плитками в один ряд, плитки пронумерованы числами от 1 до 1000. На плитках с номерами A, B и C (A

1. На одной плитке может находиться только один кузнечик.

2. За один ход один из двух крайних кузнечиков (то есть с плитки A или с плитки C) может перепрыгнуть через среднего кузнечика (плитка B) и встать на плитку, которая находится ровно посередине между двумя оставшимися кузнечиками (то есть между B и C или A и B соответственно).

Если между двумя оставшимися кузнечиками находится чётное число плиток, то он может выбрать любую из двух центральных плиток.

Например, если кузнечики первоначально сидели на плитках номер 1, 5, 10, то первым ходом кузнечик с плитки номер 10 может перепрыгнуть на плитку номер 3 (она находится посередине между 1 и 5), или кузнечик с плитки номер 1 может перепрыгнуть на плитку номер 7 или 8 (эти две плитки находятся посередине между плитками 5 и 10).

Даны три числа: A, B, C. Определите, какое наибольшее число ходов может продолжаться игра.

Формат входных данных

Программа получает на вход три целых числа A, B и C (1 6 A

Формат выходных данных

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

Примеры

Примечание

В примере сначала кузнечик с плитки №6 прыгает на плитку №3. Затем кузнечик с плитки №4 прыгает на плитку №2.

Задача 2 (15 баллов)

Даны две сцепленные шестеренки. У одной шестеренки N зубцов, у другой – K. Требуется найти, какое минимальное число поворотов на один зубчик требуется сделать, чтобы шестеренки вернулись в исходное состояние.

Формат ввода

В единственной строке даны два натуральных числа N и K, каждое из которых не превосходящих 10 миллионов.

Формат вывода

Выведите искомое количество зубчиков. Гарантируется, что оно не более миллиарда.

Примеры

Задача 3 (15 баллов)

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

Входные данные:

первая строка входного файла содержит целые числа t1 , v1 — для первого электромобиля, t2 и v2 — для второго, разделенные пробелами (1 ≤ ti , vi ≤ 1000). Вторая строка содержит одно целое число x — длину трассы (1 ≤ x ≤ 1000 000).

Выходные данные:

если первый автомобиль финиширует первым, выведите «First». Если второй автомобиль окажется на финише раньше, выведите «Second». Если же обе машины преодолеют трассу за одинаковое время, выведите «Draw».

Пример:

Задача 4 (10 баллов)

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

Входные данные:

содержится единственное целое число n (2 ≤ n ≤ 100) — размер делегации.

Выходные данные:

выведите два целых числа a2 и a3 , разделенных пробелом — число двухместных и трехместных номеров, которые необходимо выделить телекомпании, соответственно. Пример:

Задача 5 (20 баллов)

Любимое дело призрака Феди в теплые летние ночи — прыгать вдоль дороги по макушкам деревьев. Больше всего радости ему доставляет, когда он прыгает не просто так, а только вверх, от невысокого дерева к дереву повыше (причём одинаковая высота дерева Федю не устраивает, так как он стремится ввысь). При этом Федя суммировал высоту деревьев, которые он посещал, при условии, если ему это доставляло радость и чем больше была эта сумма, тем больше радовался Федя. Эту сумму будем называть «Показателем радости Феди» (Prf). Если Федя неожиданно встречал дерево ниже, либо точно такое же по высоте, как и предыдущее, то его показатель радости тут же падал до высоты текущего дерева.

Требуется: написать программу, определяющую максимальный Prf, при условии, что прыгать он начал c Prf=0.

Входные данные: Первая строка — количество деревьев N

Выходные данные: одно число — Prf.

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

Задача 6 (25 баллов)

Наступил июнь и фермеру Джону настала пора обрабатывать картофельное поле с посадками картофеля и всходами свежих сорняков. Поле можно представить в виде плоскости, и кусты картофеля посажаны идеально в точках с целыми координатами. В солнечный понедельник Джон вышел в поле для прополки. Работал он очень хорошо, так как опыт имел не малый, да и здоровьем был не обижен. В течение дня он прополол некоторый прямоугольный участок поля. Стороны этого участка параллельны осям координат, а две противоположные вершины расположены в точках (x1, y1) и (x2, y2). Следует отметить, что кусты картофеля, находящиеся на границе этого прямоугольника, также были прополоты. В момент прополки фермер заметил, что на некоторых кустах появились колорадские жуки, это очень огорчило фермера, и он решил опрыскать поле химикатами, защищающими посевы. Фермер установил в поле специальную оросительную установку. Она была размещена в точке с координатами (x3, y3) и имела радиус действия струи R. Таким образом, установка начала обрабатывать все картофельные кусты, расстояние от которых до точки (x3, y3) не превышало R. Все было хорошо, но фермера мучил следующий вопрос: сколько кустов оказалось и прополото и опрыскано?

Входные данные: Первая строка содержит четыре целых числа x1, y1, x2, y2 (−100 000 ≤ x1

Выходные данные: вывести целое число – количество кустов картофеля, которые были и прополоты и опрысканы.

Пример: