Олимпиады по информатике



Олимпиадные задания по информатике 9 класс


1). На координатной плоскости своими действительными координатами (x1, y1), (x2, y2), (x3, y3), (x4, y4) задан выпуклый четырехугольник. Если он является параллелограммом, найти площадь той его части, которая расположена во второй координатной четверти.

Пример работы правильной программы
Введите координаты вершин четырехугольника
–2 3 2 3 2 –3 –3 –4
Четырехугольник не является параллелограммом
Введите координаты вершин четырехугольника
–5 –2 1 4 5 4 –1 –2
Четырехугольник является параллелограммом
Искомая площадь 4.5

2).

Последовательность из латинских букв строится следующим образом. На первом шаге она пуста. На каждом последующем шаге последовательность удваивается, после чего к ней слева дописывается очередная буква латинского алфавита (а, b, с, ...). Ниже приведены первые шаги построения последовательности:
Шаг 1. пустая последовательность
Шаг 2. а
Шаг 3. baa
Шаг 4. cbaabaa
Шаг 5. dcbaabaacbaabaa
...

Задача состоит в том, чтобы по заданному числу N (1 <= N < 226) определить символ, который стоит на N-ом месте в последовательности, получившейся после 27-го шага (символы отсчитываются слева направо).

В качестве ответа укажите символ, стоящий в позиции N получившейся последовательности.

Пример работы правильной программы
Введите число N 4
Искомый символ w

3).

Имеются три пробирки. Вместимость каждой из них — 100 миллилитров. На двух пробирках из трех нанесены одинаковые риски (метки). Третья пробирка — без рисок. Возле каждой риски надписано целое число миллилитров, которое вмещается в пробирку от дна до этой риски.

Изначально одна из пробирок с рисками наполнена 100 миллилитрами кваса, а остальные две — пустые. Требуется написать программу, которая выясняет, можно ли поместить в пробирку без рисок один миллилитр кваса, и если да, то находит минимально необходимое для этого число переливаний. Квас можно переливать из одной пробирки в другую до тех пор, пока либо первая из них не станет пустой, либо одна из пробирок не окажется заполненной до какой-либо риски.

Технические требования:
1. Число рисок не более 10.
2. Риски считаются упорядоченными по возрастанию: V1 < V2 < ...  < Vn. Последняя риска считается сделанной на верхнем крае пробирки (Vn = 100).

Исходные данные корректны и их проверка не требуется.

Пример работы правильной программы
Введите число рисок 4
Введите 1-ую риску 13
Введите 2-ую риску 19
Введите 3-ую риску 27
4-я риска принимает значение 100.
Для получения 1 миллилитра необходимо 4 переливания.
Введите число рисок 2
Введите 1-ую риску 10
2-я риска принимает значение 100.
1 миллилитр получить невозможно.

4).

Военный укрепленный район представляет собой простую квадратную решетку размером N * N с расстоянием между узлами, равным 1. В некоторых узлах этой решетки находятся доты. Будем называть кластером ранга K группу из K дотов, такую, что расстояния между любыми дотами внутри этой группы меньше, чем расстояния между любым дотом, входящим в данную группу, и каждым дотом вне ее. Будем называть кластер ортогональным, если он не входит в состав кластера более высокого ранга. Максимальный ранг кластера ограничим числом 3.

Написать программу, которая для заданных N, числа дотов M и их координат (X, Y) проводит классификацию дотов по ортогональным кластерам, выводит число ортогональных кластеров 3-го и 2-го рангов. В программе предусмотреть корректность ввода исходных данных.

Пример работы правильно работающей программы
Размер решетки N=?
100
Число дотов М=?
6
Координаты 1-го дота?
0 0
Координаты 2-го дота?
2 1
Координаты 3-го дота?
4 0
Координаты 4-го дота?
2 99
Координаты 5-го дота?
5 90
Координаты 6-го дота?
50 50
Число ортогональных кластеров 3-го ранга равно 1
Число ортогональных кластеров 2-го ранга равно 1

5).

Группа Н-ских революционеров похитила с М-ской военной базы прототип экспериментальной нейтронной гранаты. Для активации взрывного механизма необходимо ввести код (последовательность из десятичных цифр). После подключения к гранате Н-ский эвристический анализатор частично расшифровал код, выдав строку-маску из N символов, каждый из которых имеет следующий смысл:
? — в этой позиции может находиться любая цифра;
заглавная латинская буква — в этой позиции может находиться любая цифра, но разным буквам соответствуют разные цифры, а одинаковым буквам — одинаковые цифры;
цифра — в этой позиции может находиться только эта цифра.

Требуется написать программу, которая определит число вариантов кода, удовлетворяющих строке-маске.

Примечания:
число вариантов не превосходит 2 млрд;
Н-ский эвристический анализатор абсолютно надежен и не допускает ошибок.

Технические требования

Имя входного файла: INPUT.TXT

Имя выходного файла: OUTPUT.TXT

Формат входных данных:
строка-маска, полученная на выходе Н-ского эвристического анализатора.

Формат выходных данных:
строка, содержащая число вариантов, удовлетворяющих строке-маске.

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

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

Олимпиадные задания по информатике 10 класс


1).

На одном из секретных заводов осуществляется обработка радиоактивных материалов, в результате которой образуются радиоактивные отходы двух типов: типа A — особо опасные и типа B — неопасные. Все отходы упаковываются в специальные прямоугольные контейнеры одинаковых размеров, после чего эти контейнеры укладываются в стопку (один над другим) для захоронения. Стопка является взрывоопасной, если в ней подряд идут более чем два контейнера с отходами типа A.

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

Технические требования:

Имя входного файла: INPUT.TXT

Имя выходного файла: OUTPUT.TXT

Формат входных данных:
единственная строка входного файла содержит целое число N — количество контейнеров в стопке (1 <= N <= 31).

Формат выходных данных:
в единственной строке выходного файла должно содержаться искомое количество вариантов взрывоопасных стопок.

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

Пример файла выходных данных (для приведенного выше входного файла):
3

2).

Колония клеток представляет собой квадратную матрицу порядка N (N < 500). В колонию проникает M (M < 11) вирусов, которые поражают клетки с координатами (X1, Y1), … (Xm, Ym). За одну единицу времени вирус проникает в клетки, соседние с зараженными (соседними считаются клетки, имеющие общую сторону).

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

Технические требования

Имя входного файла: INPUT.TXT

Имя выходного файла: OUTPUT.TXT

Формат входных данных:
1 строка — N
2 строка — M
3 строка — X1 Y1
4 строка — X2 Y2

M+2 строка — Xm Ym.

Формат выходных данных:
строка, содержащая одно число — время заражения.

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

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

3).

Рассматриваются логические выражения, записанные по следующим правилам:
а) логические значения "истина" и "ложь" записываются как TRUE и FALSE;
б) логические переменные обозначаются одной латинской буквой, первая — “A”, вторая — “B” и далее по алфавиту;
в) логические операции (в порядке убывания приоритета) имеют вид NOT, AND и OR; количество операций в выражении не превышает 8;
г) выражения, заключенные в скобки, выполняются в первую очередь согласно принятым в математике правилам; скобки могут быть вложенными (не более 4 одновременно открытых);
д) любое служебное слово отделяется от переменной как минимум одним пробелом; выделять пробелами скобки не обязательно;
е) ЗАГЛАВНЫЕ и строчные буквы не различаются. Например: A and (b OR c), то же самое, что и a and (b or c).

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

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

Технические требования

Имя входного файла: INPUT.TXT

Имя выходного файла: OUTPUT.TXT

Формат входных данных:
Одна строка, содержащая логическое выражение.

Формат выходных данных:
Одна строка, содержащая число вариантов получения TRUE.

Пример файла входных данных:
(a and b) or not((b and c) or true)

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

 

4).

Написать программу, рисующую координатные оси с началом координат в центре экрана и строящую параболу y=x2. В правом нижнем углу экрана выводится формула, описывающая график функции в виде: y = a(x + b)2 + c.

Далее программа ожидает нажатия следующих клавиш и выполняет соответствующую работу. Клавиши R (вправо), L (влево), D (вниз), U (вверх) вызывают смещение вершины параболы на единицу в указанном направлении и изменение формулы. По оси Ox перемещение от –30 до +30. По оси Oy перемещение от –20 до +20.

Клавиша “+” вызывает изменение коэффициента a на +0.1.

Клавиша “–” вызывает изменение коэффициента a на –0.1.

Коэффициент a изменяется от –1 до +1.

При перемещении параболы или изменении коэффициента a формула также изменяется.

Нажатие клавиши “ESC” (код 27) завершает работу программы.

5).

Заданы выражения вида a @ b (количество которых меньше или равно 30), связывающие величины a и b, где a и b — любые строчные буквы латинского алфавита (возможно совпадающие), а @ — одно из шести отношений <, <=, =, <> (не равно), >=, >. В различных выражениях одни и те же буквы могут повторяться. Если введенные выражения противоречивы, то нужно сообщить об этом, иначе по двум заданным буквам написать наиболее точное выражение, связывающее их, или указать, что отношения, связывающие эти величины, неизвестны.

Технические требования
Каждое выражение вводится в отдельной строке.

Пример 1
Выражения: a < b, y >= x, a <= b, b = x, x = b, z <= z.
Первая заданная буква: y, вторая заданная буква: a.
Ответ: y > a.
Пример 2
Выражения: a < b, b < c, a = c.
Ответ: Противоречивые данные.

Олимпиадные задания по информатике 11 класс


1).

Элементами массива a[1..n] являются неубывающие массивы [1..m] целых чисел (a: array [1..n] of array [1..m] of integer; a[1][1] <= ... <= a[1][m], ..., a[n][1] <= ... <= a[n][m]). Известно, что существует число, входящее во все массивы a[i] (существует такое х, что для всякого i из [1..n] найдётся j из [1..m], для которого a[i][j]=x). Найти одно из таких чисел х.

2).

Задан набор неповторяющихся пар (Ai,Aj), Ai, Aj принадлежат множеству А={A1, A2, ..., An}. Необходимо составить цепочку максимальной длины по правилу (Ai,Aj)+(Aj,Ak)=(Ai,Aj,Ak).

При образовании этой цепочки любая пара может быть использована не более одного раза.

3).

Элементами массива a[1..n] являются неубывающие массивы [1..m] целых чисел (a: array [1..n] of array [1..m] of integer; a[1][1] <= ... <= a[1][m], ..., a[n][1] <= ... <= a[n][m]). Известно, что существует число, входящее во все массивы a[i] (существует такое х, что для всякого i из [1..n] найдётся j из [1..m], для которого a[i][j]=x). Найти одно из таких чисел х.

4). Перечислить все разбиения N на целые положительные слагаемые

Пример: N=4, разбиения: 1+1+1+1, 2+1+1, 2+2, 3+1, 4.

First = (1,1,...,1) - N единиц Last = (N)

Чтобы разбиения не повторялись, договоримся перечислять слагаемые в невозрастающем порядке. Сказать, сколько их будет всего, не так-то просто (см.следующий пункт). Для составления алгоритма Next зададимся тем же вопросом: в каком случае i-ый член разбиения можно увеличить, не меняя предыдущих?



5).

Найти максимальную по длине последовательность z,
полученную вычеркиванием элементов как из x, так и из y.

Пусть x=x1,x2, ... ,xm, y=y1,y2, ... ,yn.

Заведем матрицу A[0..m,0..n]. Элемент A[i,j] будет длиной

максимальной общей подпоследовательности y x1, ... ,xi и y y1, ..., yj. Сначала A[i,0]=A[0,j]=0, i=0, ... ,m, j=0, ... ,n. Пусть xi=yj, тогда требуется увеличить длину максимальной общей подпоследовательности x1

^