Задача № Змей Горыныч

Вид материала

Задача

Содержание Напишите программу Примеры входных и выходных данных Green : 5 Районная (городская) олимпиада по информатике Московской области Green : 0 . Black : 1 Green : 2 Black : 1 Green : 20 Black : 4 Green : 410 Black : 7 0 Green : 195 Black : 194 Green : 32016 Black : 62 64 Green : 355911 Black : 70756 Районная (городская) олимпиада по информатике Московской области 2007-2008 уч. год Лист тестирования участника олимпиады

Подобный материал:

• Муравей Антц, 120.3kb.
• 14. 00 на площадке установлена сцена, работает диджей, звучит русская народная музыка, 14.94kb.
• «кем быть?» Или сказка про то, как выпускники волшебной школы выбирали себе лучшие, 324.05kb.
• В фокусе пересечения целого ряда идйных и жанрово-сти­­листических течений в литературе, 127.13kb.
• Сказка про Ивашку-школьника и гусей-лебедей, 85.56kb.
• Торговая тактика «Русские народные сказки» рнс, 41.24kb.
• Программа курса лекций «Математические методы и модели исследования операций», 27.98kb.
• Т. М. Боровська кандидат технічних наук, доцент І. С. Колесник, 118.17kb.
• Разновозрастная итоговая проектная задача 1-4 классы, 87.27kb.
• Программа дисциплины Алгоритмы на графах Семестр, 13.21kb.

Районная (городская) олимпиада по информатике Московской области

2007-2008 уч. год


Задача № 1. Змей Горыныч

Оценка: 25 баллов

Волшебник Мерлин изготавливает волшебные мечи принцам, желающим убить Змея Горыныча. Основная характеристика меча - число голов Змея Горыныча, которые он срубает за удар. Основная характеристика Змея Горыныча - число голов, которые он может отрастить за сеанс регенерации. Бои принцев со Змеями Горынычами всегда протекают одинаково - принц атакует, и прячется за щитом; Змей Горыныч атакует огненным дыханием и регенерирует; так продолжается до тех пор, пока после очередного удара у Змея Горыныча не останется голов. Ясно, впрочем, что не каждым мечом можно победить каждого Змея Горыныча. Заказ, поступающий Мерлину, всегда содержит число голов Змея Горыныча и скорость его регенерации.

^ Напишите программу, которая по известной атакующей силе меча определяет, сможет ли принц убить такого Змея Горыныча таким мечом и, если да, то сколько ударов потребуется.

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

С клавиатуры вводится три числа через пробел — N, М и К (1≤ N ,М, К ≤ 10⁹), где N - число голов, которые меч срубает одним-ударом, М-число голов Змея Горыныча, К - число голов, которые Змей Горыныч регенерирует за раз.

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

На экран вывести число ударов, которые необходимо нанести принцу, чтобы убить Змея Горыныча, если это возможно. Если таким мечом убить Змея Горыныча нельзя, то следует вывести «NO».

Примеры	входных и	выходных данных
	Ввод			Вывод
3 6 2	2			4
5 10	6			NO

Задача № 2. Таблица умножения

Оценка: 25 баллов

Таблицей умножения назовем таблицу размера N строк на М столбцов, в которой на пересечении i-ой строки и j-ого столбца стоит число i*j (строки и столбцы нумеруются с единицы).

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

Процесс покраски чисел можно условно разбить на четыре этапа. На первом этапе все числа красятся в черный цвет. На втором - все четные числа красятся в красный цвет, на третьем - все числа, делящиеся на 3, красятся в зеленый цвет, на четвертом - все числа, делящиеся на 5, красятся в синий цвет.

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

Напишите программу, решающую задачу подсчета соответствующих количеств.

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

С клавиатуры вводятся два натуральных числа N и М - размеры

таблицы умножения (1 ≤ N, M ≤ 1000).

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

В первой строке вывести на экран количество чисел, покрашенных в красный цвет, во второй - в зеленый, в третьей - в синий, в четвертой - в черный. Следуйте формату, приведенному в примерах.

^ Примеры входных и выходных данных
Ввод	Вывод
3 3	RED : 3 ^ GREEN : 5 BLUE : 0 BLACK : 1
5 2	RED : 5 GREEN : 2 BLUE : 2 BLACK : 1

^ Районная (городская) олимпиада по информатике Московской области

2007-2008 уч. год


Задача № 3. Гарри Поттер и волшебный портал

Оценка: 25 баллов

Гарри Поттер должен пройти по длинному коридору школы Хогвартс от своей спальни до кабинета профессора Снейпа, а затем вернуться обратно. Для упрощения задачи введем систему координат с единственной осью, направленной вдоль коридора. Пусть вначале Гарри находится в точке 0, а кабинет профессора Снейпа имеет координату X. Сам коридор настолько длинный, что можно считать его бесконечным (магия!). В трех точках коридора расположены три односторонних портала, то есть, войдя в один из таких порталов в точке с координатой а₁, а₂ или a3 Гарри может мгновенно переместиться в точку с координатой b₁, b₂ или b₃ соответственно. Гарри не обязательно заходить в портал, оказавшись в точке с координатой портала, он может просто пройти мимо него.

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

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

В первой строчке с клавиатуры вводится число X - координата кабинета профессора Снейпа. В следующих трех строках задаются по два числа - координаты входа ai- и выхода bi; порталов. Все числа целые от -10000 до 10000.

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

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

Примеры	входных	и выходных данных
	Ввод		Вывод
10 2 9 8 3 -100 100			8

Задача № 4. Двоичные числа

Оценка: 25 баллов

Найдите количество чисел Z, удовлетворяющих неравенству А ≤ Z ≤ В, таких, что в записи двоичного разложения Z используется ровно К единиц. Например, если A=10; B=20; К=2, то таких чисел 5 (это числа 10=1010₂; 12=1100₂; 17=10001₂; 18=10010₂; 20=10100₂).

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

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

С клавиатуры вводится три числа через пробел — А, В, К

(0≤А,В≤10⁹, 0≤К≤30)

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

Вывести на экран одно число - количество чисел Z.

Примеры входных и выходных данных

Ввод	Вывод
10 20 2	5

Внимание!

• Во всех задачах ограничение по времени - 2 секунды на тест.
  
• После олимпиады школьники и учителя могут получить тесты и
  подать апелляцию на сайте www. informatics.ru
  
• На Московскую областную олимпиаду по информатике будут приглашены победители районных туров, а также школьники, показавшие наилучшие результаты во II Всероссийской заочной олимпиаде по информатике. Подробности об отборе на областную олимпиаду с помощью заочного тура — на сайте
  www.olympiads.ru/zaoch
  
• Победители районных туров приглашаются на лекции по подготовке
  к областной олимпиаде. Следующая лекция состоится 27 ноября.
  Справки по тел. 334-03-67 и на сайте www.cnpt.ru
  

Районная (городская) олимпиада по информатике Московской области 2007-2008 уч. год Лист тестирования участника олимпиады

Фамилия, имя

Школа, класс


^ Районная (городская) олимпиада по информатике Московской области 2007-2008 уч. год Лист тестирования участника олимпиады

Задача №3. Гарри Поттер и волшебный портал

№	Тест	Ответ	Ответ участника	Баллы за тест	Баллы участника
1	15 20 -11 -10 100 16 17	30		3
2	15 20 -9 -10 100 16 17	28		3
3	15 -11 16 1 -10 17 -5	10		3
4	1000 993 -100 15 16 999 992	1101		3
5	1000 999 500 998 -1 10000 -10000	1003		3
6	-1700 -6 15 -1 -6 15-1699	1702		3
7	666 6 66 66 6 666 -333	939		3
8	-1001 90 -100 91 -200 92 -300	1794		4
итого				25

Задача №4. Двоичные числа

№	Тест	Ответ	Ответ участника	Баллы за тест	Баллы участника
1	0 60 0	1		3
2	0 2048 1	12		3
3	2378 29389 7	5756		3
4	10000 1000000 30	0		3
5	23 50078791 9	2 7 7 8 3 82		3
6	34567 218372873 22	157136		3
7	849987 89487231 3	1761		3
8	0 1000000000 15	146844581		4
итого				25

ИТОГО БАЛЛОВ:

Подпись тестирующего

Подпись участника

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