См. также:

Результаты

  Санкт-Петербургские Олимпиады по Информатике

Задачи городской олимпиады СПб 1996 года

Районный теоретический тур (1-ый тур)

A. Задача о строке B. Пифагорово дерево
C. Закраска прямой D. Шарики
E. N в степени N F. Сообщение
G. "Ну, погоди!" на катке H. Раскраска шестеренок

Городской теоретический тур (2-ой тур)

Задача A (Миллион чисел) Задача B (Электронная таблица)
Задача C (Банковский счет) Задача D (Программа)

Городской практический тур (3-ый тур)

Задача A Задача B Задача C

Районный теоретический тур (1-ый тур)

A. Задача о строке

Во входном потоке расположена строка, cостоящая из нулей и единиц. Требуется найти длину наибольшей подстроки вида ABCD, где

A - непрерывная цепочка нулей (не менее 6 символов);
B - непрерывная цепочка единиц (непустая);
C - непрерывная цепочка нулей (непустая);
D - непрерывная цепочка единиц (не менее 7 символов).

На вход программе подается последовательность символов, составляющих строку. Признаком конца служит символ "." (точка). Длина строки заранее не определена. Строка может быть такой длинной, что не поместится в память вашего компьютера. Программа должна прочитать строку ровно 1 раз. Например, для строки "0100100000001001111111110." ответом будет 19.

B. Пифагорово дерево

Напишите программу, которая выводит на графический экран дерево, изображенное на рисунке. Угол между парой исходящих веток равен 90 градусов. Каждая ветка (исключая ствол) имеет длину, равную 0.56 от длины ветки, из которой она растет. Высота дерева составляет 10 веток (включая ствол). Считайте, что размеры графического экрана вашего компьютера 640 точек по горизонтали и 480 точек по вертикали. В левом верхнем углу экрана расположена точка с координатами (0,0). Считайте, что в вашем языке программирования есть оператор LINE (x1,y1,x2,y2), который изображает на экране отрезок, соединяющий точки с координатами (x1,y1) и (x2,y2).

C. Закраска прямой

Отрезок числовой оси от 0 до 1.000.000.000 выкрасили в белый цвет. Затем отдельные участки (между точками с целыми координатами) перекрашивали в белый и черный цвета. Всего было выполнено N (1< N < 100) перекрашиваний. Напишите программу, которая по заданной последовательности перекрашиваний находит границы самого длинного белого участка.

Например, для N=4 и последовательности: 1- 999999997 в черный, 40-300 в белый, 300-634 в белый, 43-47 в черный, ответом будет участок (47-634).

D. Шарики

Имеется клетчатое поле размером MxN клеток (0< M,N< =20). В разных клетках поля находятся два маленьких шарика, которые могут перемещаются по полю по диагонали. За один шаг каждый шарик перемещается на одну из 4-х соседних диагональных клеток. При соударении с границей поля шарик меняет свое направление, отражаясь как луч света. При попадании в угол шарик меняет направление своего движения на противоположное.

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

E. N в степени N

По заданному целому A (0< A< 1.000.000.000) найти минимальное N, при котором N**N (N в степени N) будет делиться на A без остатка. Напишите программу, которая будет работать эффективнее, чем простой перебор всех значений X. Например, для A=40 ответом будет N=10.

F. Сообщение

В сообщении, состоящем из одних русских букв и пробелов, каждую букву заменили ее порядковым номером в русском алфавите ('А' - 1, 'Б' - 2, ..., 'Я' - 33), а символ пробела заменили нулем. Напишите программу, которая вводит получившуюся последовательность цифр (не более 30) и находит количество исходных сообщений, из которых могла получиться заданная последовательность. Например, для последовательности "1025" количество возможных исходных сообщений - 4.

G. "Ну, погоди!" на катке

Заяц стоит в центре большого катка и поет свою любимую песню в игрушечный микрофон. От микрофона тянется достаточно длинный шнур, конец которого находится в руках у Волка. Пытаясь воспользоваться сложившейся ситуацией, Волк хочет незаметно замотать зайца этим шнуром. Для этого он катается вокруг зайца на коньках и постепенно его заматывает. Напишите программу, которая вводит путь Волка - ломаную, заданную последовательным перечислением координат вершин и определяет на сколько полных оборотов Волк замотает зайца. Учтите, что во Волк во время движения может не только заматывать зайца, но и разматывать. Координаты представляются вещественными числами. Заяц стоит в точке с координатами (0,0).

H. Раскраска шестеренок

Две одинаковые шестеренки с N (N<= 12) зубьями красятся в два цвета, белый и черный, каждый зубец в свой цвет. Напишите программу, которая для заданному N выводит все способы раскраски шестеренок, которые нельзя совместить вращением. Раскраски, которые получаются друг из друга вращением и обменом шестеренок считаются одинаковыми. На рисунке показаны три раскрашенных шестеренки с 11 зубьями. Раскраска 2 совмещается с раскраской 1, а раскраска 3 - нет. Например, для N=2 все способы раскраски следующие (Б - белый цвет, Ч - черный). 

ББ, БЧ
ББ, ЧЧ
БЧ, ЧЧ

Городской теоретический тур (2-ой тур)

Задача 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(B. При вставке часть строки сдвигается вправо, а на освободившееся место записывается вставляемый символ. Обоснуйте свое решение.

Городской практический тур (3-ий тур)

Усл. обозначения: ЗЛ - замкнутая ломаная без самопересечений и самокасаний, звенья которой параллельны осям координат. Ломаная задается перечислением координат вершин в порядке обхода по часовой стрелке, первая и последняя вершины совпадают. Координаты вершин - целые числа. Ломаная содержит не более 100 звеньев. Ломаная не содержит последовательных параллельных звеньев.

Задача A

Задана ЗЛ A и целое число K. Требуется найти ЗЛ B, имеющую минимально возможную площадь при одновременном выполнении следующих условий:

  1. Область, ограниченная ломаной B, содержит ломаную A;
  2. Расстояние между точками ломаных A и B не меньше K.

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

Результат работы вывести одновременно в файл OUTPUT.TXT и на графический экран. В выходном файле ломная задается также, как во входных данных. На графическом экране изобразите ломную A белым цветом, а ломную B - зеленым. Ваша программа должна выполнить подходящее масштабирование и центровку изображения.

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

10 0 10 20 30 20 30 10 40 10 40 0 10 0
13

Пример выходного файла OUTPUT.TXT для приведенного примера: 

-3 -13 -3 33 53 33 -3 -13

Задача B

Задана ЗЛ A и целое число K. Требуется найти ЗЛ B, имеющую максимально возможную площадь при одновременном выполнении следующих условий:

  1. Область, ограниченная ломаной A, содержит ломаную B;
  2. Расстояние между точками ломаных A и B не меньше K.

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

Результат работы вывести одновременно в файл OUTPUT.TXT и на графический экран. В выходном файле ломная задается также, как во входных данных. На графическом экране изобразите ломную A белым цветом, а ломную B - зеленым. Ваша программа должна выполнить подходящее масштабирование и центровку изображения.

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

10 0 10 20 30 20 30 10 40 10 40 0 10 0
5

Пример выходного файла OUTPUT.TXT для приведенного примера: 

15 5 15 15 25 15 25 5 15 05

Задача C

Задана ЗЛ A и точка с целочисленными координатами (x,y), не лежащая на ломаной A. В точке находится источник света, который освещает непосредственно видимые из него участки ломаной A. Требуется найти освещенные и неосещенные участки ломаной A. Результат работы вывести одновременно в файл OUTPUT.TXT и на графический экран. В файл OUTPUT.TXT вывести только суммарную длину всех освещенных участков. На графическом экране изобразите ломаную A и точку (x,y). Освещенные участки ломаной рисуются белым цветом, а неосвещенные - серым. Ваша программа должна выполнить подходящее масштабирование и центровку изображения.

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

10 0 10 20 30 20 30 10 40 10 40 0 10 0
35 5

Пример выходного файла OUTPUT.TXT для приведенного примера: 

9

Система оценок

Задача A 25 баллов
Задача B 35 баллов
Задача C 25 баллов
Графическое оформление15 баллов
Максимальная оценка на практическом туре 100 баллов
Используются технологии uCoz