Олимпиады по информатике и программированию среди школьников и студентов

This page uses frames, but your browser doesn't support them.


Районная олимпиада по информатике 98

Требования ко всем программам: если в течение 20 секунд задача не сообщает результат, то за тест участник получает 0 баллов.

Задача №1. Сравнение строк. (15 баллов)

Вводятся две строки символов в кодировке ASCII. Символы находятся в диапазоне [32..126]. Требуется определить, какие символы встречаются в обеих строчках, а какие только в одной, и вывести их в порядке возрастания номера. Проверка корректности входных данных не требуется.

Пример.
Входная информация: | Выходная информация:
Information; Revolution | в обеих: inot в одной: .;IRaeflmru

Задача №2. Поиск квадратов. (30 баллов)

На поле 10x10 клеток располагают до девяти квадратов один поверх другого. Ребра квадратов выражаются целым числом клеток. Квадраты не выходят за границы поля. Границы квадратов совпадают с краями клеток поля. Каждая клетка поля помечена цифрой 0. Каждая клетка квадрата помечается цифрой соответствующей номеру квадрата.

Во время исполнения алгоритма в программу вводится таблица цифр 10x10 в виде 10 строк:
0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0
0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0
0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0
0 | 0 | 0 | 1 | 1 | 1 | 1 | 0 | 0 | 0
0 | 0 | 0 | 1 | 1 | 1 | 1 | 3 | 3 | 0
0 | 0 | 0 | 1 | 1 | 1 | 1 | 3 | 3 | 0
0 | 2 | 2 | 2 | 1 | 1 | 1 | 3 | 3 | 0
0 | 2 | 2 | 2 | 0 | 3 | 3 | 3 | 3 | 0
0 | 2 | 2 | 2 | 0 | 0 | 0 | 0 | 0 | 0
0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0

По этим данным алгоритм должен определить размеры квадратов и выдать сообещение на монитор в виде последовательности, содержащей номера квадратов и их размеры:
1 - 4
2 - 3
3 - 4

Считается известным, что во входных данных содержится достаточная информация для однозначного определения размеров квадратов. Контроля корректности входных данных не требуется.

Задача №3. Римские цифры. (30 баллов)

Напишите программу, складывающую два числа, записанных римскими цифрами. Результат должен выводиться также в римской нумерации. Сумма двух чисел не превышает 3000. Контроль корректности входных данных требуется. Если запись входного числа ошибочна, должно выводиться сообщение: "Ошибка ввода".

Правила римской нумерации.

  1. I = 1; V = 5; X = 10; L = 50; C = 100; D = 500; M = 1000.
  2. Каждая цифра числа в десятичной системе счисления переводится в римскую запись отдельно.
  3. Если меньшая цифра стоит перед большей, то она вычитается.
  4. Одна и та же цифра ставится не более трех раз подряд.

Примеры: XIX (19), CCCXXXIII (333), CMXCIX (999), DCXC (690), XLIX (49), DCCCLXXXVIII (888), CCCXCVII (397).

Пример входных данных: CLXXIX, CCXLI
Результат: CDXX

Задача №4. Девятнашка. (40 баллов)

Игровое поле состоит из четырех карточек, помеченных цифрами от 1 до 4, и пяти карточек, помеченных цифрой 0. На рисунке внизу показано финальное расположение карточек.

1 | 0 | 2
0 | 0 | 0
3 | 0 | 4

Карточка под номером 4 ("пустое место") может меняться местами с карточками, имеющими с ней общую сторону. Задача программы состоит в том, чтобы найти комбинацию, которая за наименьшее число перестановок приведет карточки к финальному расположению. Входные данные вводятся в виде трех строк из трех цифр, пример:
013
004
020

Контроля корректности входных данных не требуется. Выходные данные: число перестановок (наименьшее).

Для этого примера результат: 19.

Задача №5. (3 балла)

Даны натуральные числа n, k (n, k <= 9999). Из чисел от n до k выбрать те, запись которых содержит ровно три одинаковые цифры. Например, числа 6766, 5444, 0006, 0060 содержат ровно три одинаковые цифры.

Задача №6. (3 балла)

Натуральное число из k цифр является числом Амстронга, если сумма его цифр, возведенных в k-ю степень, равна самому числу (например, 153 = 13 + 53 + 33). Получить все числа Амстронга, состоящие из трех и четырех цифр.

Задача №7. (4 балла)

Имеется n1 шоколадных конфет, n2 карамели и n3 леденцов. Сколько подарочных наборов к Новому году можно составить из этих конфет, если известно, что в каждом наборе должно быть k1 шоколадных, k2 карамели и k3 леденцов?