РАЙОННАЯ ОЛИМПИАДА ШКОЛЬНИКОВ ПО ИНФОРМАТИКЕ
1998-99 учебный год

1. k-периодичное число (15 баллов). Назовем натуральное число (количество цифр в его записи не превышает 255) k-периодичным, если модуль разности между любыми его двумя соседними цифрами равен k. Определить, является ли k-периодичным заданное число n.

2. Гроза фальшивомонетчиков (25 баллов). Дано 12 монет, одна из которых, возможно, фальшивая. Известно, что она отличается по массе от настоящих, но не известно, легче она или тяжелее. Имеются чашечные весы без гирь. Весы достаточно чувствительны, то есть они способны уловить разность масс, равную разности масс настоящей и фальшивой монеты. За одно взвешивание на каждую чашку весов кладется несколько (от одной до шести) монет и фиксируются показания.

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

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

• Каждой монете присвоен номер от 1 до 12.


• Результат каждого взвешивания вводится в компьютер в следующей последовательности:

• После каждого ввода данных программа формирует сообщение в текстовой форме:

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


• Передавать программе любую информацию, кроме трех результатов взвешивания, запрещено.

3. Web-адреса (35 баллов). Дано N Web-адресов страниц Internet (N <= 20). На каждой странице расположено несколько ссылок на другие адреса (в частности, таких ссылок может не быть вообще). Требуется определить минимальное число переходов, чтобы попасть с одной страницы на другую.

Замечания:

• Ссылки однонаправлены, то есть если с A есть ссылка на B, то это не значит, что с B есть ссылка на A.


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

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

• Все адреса считаются занумерованными от 1 до N.


• Для каждого адреса ссылки вводятся как номера соответствующих адресов.


• Программа должна позволять выполнить несколько тестов при одном и том же наборе Web-адресов (без их повторного ввода).

Пример работы правильной программы

4. Календари (30 баллов). В “солнечном” календаре год состоит из 12 месяцев с количеством дней соответственно:

Написать программу, переводящую даты из “лунного” календаря в “солнечный” и обратно в пределах 1000-2000 г.г. “солнечного” календаря.

Пример правильно работающей программы

Замечание. При решении задачи предполагается возможность использования целого типа длиной 4 байта (longint).

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

• каждая шашка может входить не более чем в один кластер;


• если две шашки расположены в соседних клетках (имеющих общую вершину или сторону), то они входят в состав одного кластера.

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

Пример правильно работающей программы

6. Счастливый билет (50 баллов). Даны: А — номер автобусного билета (шестизначное натуральное число) и N — целое неотрицательное число. Между некоторыми парами соседних цифр номера билета А разрешается поместить знаки арифметических операций (+ , – , *) так, чтобы результат полученного арифметического выражения стал равен N.

Требуется

• определить количество различных решений для заданных А и N;


• вывести все решения на экран.

Замечания

• Разрешается предполагать, что число различных решений не превосходит числа строк на экране.


• Значение выражения вычисляется с учетом стандартного приоритета арифметических операций.

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

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

Пример работы правильной программы

---

---