XI городская олимпиада школьников
Санкт-Петербурга по информатике

1996 год

Теоретический тур

Задачи

Задача A. Миллион чисел

Имеется миллион различных натуральных чисел, не превосходящих 1.000.000.000 (одного миллиарда). Программа может их получить, выполнив сначала процедуру RESET, а затем миллион раз повторяя процедуру GETNEXT, которая вырабатывает следующее число. Напишите программу, которая находит наименьшее натуральное число, не включенное в этот набор чисел. Процедуру RESET нельзя вызвать больше четырех раз и нельзя запоминать в памяти компьютера более 200 чисел.

Задача B. Электронная таблица

Вы знаете, что клетки шахматной доски обозначаются латинскими буквами от A до H по вертикали и цифрами от 1 до 8 по горизонтали (от A1 в левом нижнем углу до H8 в правом верхнем). В каждой клетке содержится строка одного из трех типов: пустая строка, десятичная запись положительного числа или сумма названий двух или более клеток. На рисунке приведен пример заполнения доски (остальные клетки пустые).

Вычисление таблицы заключается в решении системы уравнений, в которой переменными являются значения клеток. Для приведенного примера решение такой системы следующее: A7=32, B1=16, C2=48, F4=64, E6=80.

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

Задача C. Банковский счет

Номер банковского счета состоит из девяти цифр, представленных 7-сегментным кодом. На рисунке приводится изображение 7-сегментного кода для цифры 6. При автоматическом считывании номера счета могут возникать ошибки, т.е. некоторые сегменты могут исчезать, а некоторые - появляться. Требуется восстановить прочитанный номер банковского счета, если известно, что

1. В номере счета содержится не более одного ошибочного сегмента;
2. Правильный номер {d9, d8, ..., d1} удовлетворяет условию (d1 + d2*2 + d3*3 + ... + d9*9) mod 11 = 0, где mod - операция взятия остатка от деления. Напишите программу, которая восстанавливает номер банковского счета, либо сообщает, что восстановление невозможно или неоднозначно. Каждая цифра вводится в программу в виде матрицы 3×3, состоящей из символов " " (пробел), "_" (подчеркивание) и "!"(вертикальная черта).

Например, для номера счета

программа должна вывести 123456789. А для номера счета

вывести сообщение "восстановление невозможно".

Задача D. Программа

Ниже приведен фрагмент программы на языке БАСТИНДА. Тип данных Длинное определяет неотрицательное 100-значное десятичное число. Процедура Сложить складывает два числа А и Б типа Длинное и записывает результат в В. Вставьте в текст процедуры Сложить два символа и замените один так, чтобы вместо сложения она выполняла вычитание, если известно, что A>Б. При вставке часть строки сдвигается вправо, а на освободившееся место записывается вставляемый символ. Обоснуйте свое решение.