Задания школьной олимпиады по информатике 2009/2010 учебный год

Задания школьной олимпиады по информатике

2009/2010 учебный год

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

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

Задача № 1. Запасливая мышка (1 балл)

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

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

В единственной строке входного файла INPUT. TXT записано 3 числа — w и h (ширина и высота коврика), а так же d (диаметр запасного коврика). Все числа целые не больше 100.

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

В файл OUTPUT. TXT выведите ‘YES', если новый коврик можно спрятать под старым, и ‘NO’, если этого сделать нельзя.

Пример

№	INPUT. TXT	OUTPUT. TXT
1	4 7 4	YES
2	4 7 5	NO

Задача № 2. Два бандита (1 балл)

Бандиты Гарри и Ларри отдыхали на природе. Решив пострелять, они выставили на бревно несколько банок из-под Coca-Cola (не больше 10). Гарри начал простреливать банки по порядку, начиная с самой левой, Ларри — с самой правой. В какой-то момент получилось так, что они одновременно прострелили одну и ту же последнюю банку.

Гарри возмутился и сказал, что Ларри должен ему кучу денег за то, что тот лишил его удовольствия прострелить несколько банок. В ответ Ларри сказал, что Гарри должен ему еще больше денег по тем же причинам. Они стали спорить кто кому сколько должен, но никто из них не помнил сколько банок было в начале, а искать простреленные банки по всей округе было неохота. Каждый из них помнили только, сколько банок прострелил он сам.

Определите по этим данным, сколько банок не прострелил Гарри и сколько банок не прострелил Ларри.

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

В единственной строке входного файла INPUT. TXT записано 2 числа — количество банок, простреленных Гарри и Ларри соответственно.

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

В файл OUTPUT. TXT выведите 2 числа — количество банок, не простреленных Гарри и Ларри соответственно.

Пример

№	INPUT. TXT	OUTPUT. TXT
1	4 7	6 3

Задача № 3. Шахматные клетки (1 балл)

Даны координаты двух полей шахматной доски

(координаты клетки - это 2 числа от 1 до 8: номер столбца и номер строки)

Одно ли цвета эти клетки на шахматной доске? Вывести в выходной файл

сообщение YES, если они одного цвета, и NO иначе

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

В единственной строке входного файла INPUT. TXT записаны через пробел координаты первой клетки и координаты второй клетки.

№	INPUT. TXT	OUTPUT. TXT
1		YES
2		NO

Задача № 4. Зарплата (2 балла)

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

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

В единственной строке входного файла INPUT. TXT записаны размеры зарплат всех сотрудников через пробел. Каждая заработная плата – это натуральное число, не превышающее 105.

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

В выходной файл OUTPUT. TXT необходимо вывести одно целое число — разницу между максимальной и минимальной зарплатой.

Примеры

№	INPUT. TXT	OUTPUT. TXT
1		900
2	36 11 20	25

Задача № 5. Нули (5 баллов)

Требуется найти самую длинную непрерывную цепочку нулей в последовательности нулей и единиц.

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

В единственной строке входного файла INPUT. TXT записана последовательность нулей и единиц (без пробелов). Суммарное количество цифр не превышает 100.

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

В единственную строку выходного файла OUTPUT. TXT нужно вывести искомую длину цепочки нулей.

Пример

№	INPUT. TXT	OUTPUT. TXT
1		4

Задача № 6. Клавиатура (10 баллов)

Имя входного файла:	keyboard. in
Имя выходного файла:	keyboard. out
Максимальное время работы на одном тесте:	2 секунды
Максимальный объем используемой памяти:	64 мегабайта

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

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

Требуется написать программу, определяющую, какие клавиши сломаются в процессе заданного варианта эксплуатации клавиатуры.

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

Первая строка входного файла содержит целое число n (1 ≤ n ≤ 100) – количество клавиш на клавиатуре. Вторая строка содержит n целых чисел – с1, с2, … , сn, где сi (1 ≤ сi ≤ 100000) – количество нажатий, выдерживаемых i-ой клавишей. Третья строка содержит целое число k (1 ≤ k ≤ 100000) – общее количество нажатий клавиш, и последняя строка содержит k целых чисел pj (1 ≤ pj ≤ n) – последовательность нажатых клавиш.

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

В выходной файл необходимо вывести n строк, содержащих информацию об исправности клавиш. Если i-ая клавиша сломалась, то i-ая строка должна содержать слово “yes” (без кавычек), если же клавиша работоспособна – слово “no”.

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

keyboard. in	keyboard. out
5 1 16	yes no no no yes

Задача № 7. Газон (20 баллов)

Имя входного файла:	lawn. in
Имя выходного файла:	lawn. out
Максимальное время работы на одном тесте:	2 секунды
Максимальный объем используемой памяти:	64 мегабайта

Фермер Иван с юности следит за своим газоном. Газон можно считать плоскостью, на которой в каждой точке с целыми координатами растет один пучок травы.

В одно из воскресений Иван воспользовался газонокосилкой и постриг некоторый прямоугольный участок газона. Стороны этого участка параллельны осям координат, а две противоположные вершины расположены в точках (x1, y1) и (x2, y2). Следует отметить, что пучки травы, находящиеся на границе этого прямоугольника, также были пострижены.

Довольный результатом Иван купил и установил на газоне дождевальную установку. Она была размещена в точке с координатами (x3, y3) и имела радиус действия струи r. Таким образом, установка начала поливать все пучки, расстояние от которых до точки (x3, y3) не превышало r.

Все было хорошо, но Ивана заинтересовал следующий вопрос: сколько пучков травы оказалось и пострижено, и полито в это воскресенье?

Требуется написать программу, которая позволит дать ответ на вопрос Ивана.

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

В первой строке входного файла содержатся четыре целых числа x1, y1, x2, y2 (−100 000 ≤ x1 < x2 ≤ 100 000; −100 000 ≤ y1 < y2 ≤ 100 000).

Во второй строке входного файла содержатся три целых числа x3, y3, r (−100 000 ≤ x3, y3 ≤ 100 000; 1 ≤ r ≤ 100 000)

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

В выходной файл необходимо вывести одно целое число — число пучков травы, которые были и пострижены, и политы.

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

lawn. in	lawn. out
4 0 3	14

Иллюстрация к примеру

Составитель