Республиканская олимпиада

XII Республиканская олимпиада

имени

ИНФОРМАТИКА

8-9 классы

Заочный тур

1. «Ворота» (100 баллов)

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

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

Во входном файле input. txt записана ширина одной створки ворот – действительное число .

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

В выходном файле output. txt записана площадь образованного участка (с точностью ).

Пример:

input. txt	output. txt
4	6.867

2. «Площадь пересечения» (100 баллов)

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

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

Во входном файле input. txt в первых трех строках записаны по два числа – координаты вершин треугольника, четвертая строка содержит три числа – координаты верхнего левого угла и длина его стороны .

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

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

Пример:

input. txt	output. txt
0 0 1 0 0 1 0 1 1	0.50

3. «Слияние чисел» (100 баллов)

Даны два натуральных числа. Мегамозг решил составить из их цифр максимальное возможное число, сохранив первоначальную последовательность цифр.

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

Во входном файле input. txt в двух строках заданы два числа и .

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

В выходном файле output. txt содержится полученное число.

Пример:

input. txt	output. txt
20 4181	421810

4. «Сложение массивов» (100 баллов)

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

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

Во входном файле input. txt в первой строке заданы размеры массивов (0<=n, m<=10). В следующих строках задаются элементы двух массивов, разделенные пустой строкой. Элементы массива имеют длину не более 10.

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

В выходном файле output. txt записывается полученный массив.

Пример:

input. txt	output. txt
5 6 ab bc cd de ef fg bc cd de ef fg gh gh ef de cd bc ab abcd a a a a a b с d e f g a a a a a a ab bc cd de ef fg a b с d e f ab abcd abcde defgh efgh gh aceh bdf aceh bdf aceh bdf	b bca cda dea efa fga ca db ec fd ge hf gha efb dec c bce abf cd bcd bcde adefgh aefgh agh baceh cbdf daceh ebdf faceh gbdf

5. «Испорченный прямоугольник» (100 баллов)

Копаясь в своих записях Мегамозг нашел рисунок прямоугольника. От небрежного хранения на прямоугольнике остались линии, которые разделяют его на отдельные участки. Напишите программу, которая подсчитает количество треугольников из образовавшихся участков прямоугольника.

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

Во входном файле input. txt в первой строке заданы координаты правого верхнего угла прямоугольника на плоскости. Координаты нижнего левого угла заранее известны: , стороны прямоугольника параллельны осям координат.

Во второй строке записано целое число k – количество линий .

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

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

В выходном файле output. txt записывается целое число – количество треугольников из образовавшихся участков прямоугольника.

Пример:

input. txt	output. txt
5 3 1 1 1	3

6. «Мегамозг на заработке» (100 баллов)

Мегамозг устроился на работу. Ему пообещали, что его заработная плата будет увеличиваться каждый час. Каждый месяц заработная плата будет составлять количество рублей, равное третьей степени номера месяца (заработная плата в 1 месяц – 1 рубль, во 2 месяц – 8 рублей, в третий месяц – 27 рублей и так далее). Заработная плата Мегамозга облагается налогом, который ежемесячно вычисляется следующим образом: к записи заработной платы за 1 месяц справа записывается заработок за 2 месяц и так далее до тех пор, пока общее количество цифр в числе не будет больше . Процентом налога от заработной платы и является - я цифра образованного числа. Помогите Мегамозгу написать программу, автоматически определяющую процент налога от его заработной платы.

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

Во входном файле input. txt в первой строке задается число .

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

В выходном файле output. txt записывается процент налога – целое число .

Пример:

input. txt	output. txt
3	2

7. «Марки» (100 баллов)

Мегамозг собирает почтовые марки. У него имеются для этого альбомов, вмещающих марок. Мегамозг хочет, чтобы при потере одного какого-либо альбома каждая марка оставалась у него хотя бы в одном экземпляре. Поэтому каждую марку он покупает в двух экземплярах и наклеивает в два разных альбома. Нужно определить какое максимальное количество марок в его коллекции может образоваться.

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

Во входном файле input. txt в первой строке записано целое число – количество альбомов .

В следующей строке записаны k чисел , определяющие вместимости альбомов (, суммарная вместимость всех альбомов не более 100000 марок).

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

В выходном файле output. txt в первой строке записывается целое число – максимальное количество марок в коллекции Мегамозга. В следующих r строках – пары чисел, задающие номера двух альбомов, где будет располагаться очередная марка.

Пример:

input. txt	output. txt
4	2 1 2 2 4

8. «Телевышка» (100 баллов)

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

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

Во входном файле input. txt в первой строке записаны два целых числа и – количество микрорайонов по оси (с запада на восток) и по оси (с юга на север) соответственно .

В следующей строке записаны число – количество микрорайонов, занимаемых небоскребами .

В следующих строках задаются пары чисел – координаты небоскребов (координаты отсчитываются от 1). Гарантируется, что существует один дом, который не является небоскребом.

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

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

Пример:

input. txt	output. txt
3 3 4 1 2 3 2 2 1 2 3	1 2 2

ФОРМА

оформления решений заданий заочного тура

(Интернет-олимпиады)

по информатике

Решения задач по информатике высылаются на почтовый ящик *****@***ru

На данный ящик в архиве (WinRar, WinZip, WinArj) необходимо прислать решенные задачи (программы). Название каждой задачи является ее номер! Решения задач можно отправлять несколько раз, баллы будут присваиваться за последнее отправленное решение соответствующей задачи. На Ваше письмо будет отправлен ответ о получении решений, если ответ не придет в течение недели, то свяжитесь с Оргкомитетом олимпиады по телефону 8(8362)218417.

В письме ДОЛЖЕН быть текстовый документ, содержащий следующие данные:

1.  Фамилия, имя, отчество

2.  Язык программирования, использованный при решении задач

3.  Класс

4.  Полное название образовательного учреждения

5.  Вид школы (обычная, лицей, гимназия, с углубленным изучением предмета)

6.  Полный домашний адрес (с указанием индекса и телефона), e-mail (обязательно)

7.  Адрес школы и телефон

8.  Фамилия, имя, отчество учителя (наставника)

9.  Каким образом вы узнали о проведении олимпиады им.