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

Практический тур, 7 марта 1999 года

Задачи

Задача A. Прямая

Имя входного файла: input.txt
Имя выходного файла: output.txt
Максимальное время работы на каждом тесте: 10 секунд
Максимальная оценка: 20 баллов

Координатная плоскость разбита на единичные квадраты с целочисленными координатами. Требуется перечислить координаты левых нижних углов всех квадратов, которые пересекаются с прямой, проходящей через точки (x1, y1) и (x2, y2). Порядок перечисления квадратов может быть произвольным.

Формат входных данных

Во входном файле заданы целые числа x1 y1 x2 y2. Все числа по абсолютной величине не превосходят 10000. Указанные точки различны, то есть либо x1x1, либо y2y2.

Формат выходных данных

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

Пример

input.txtoutput.txt
-1 -1 1 2
-2 -2   -2 -1
-1 -2   -1 -1   -1 0
 0  0    0  1    0 2
 1  1    1  2

Задача B. Шары и коробки

Имя входного файла: input.txt
Имя выходного файла: output.txt
Максимальное время работы на каждом тесте: 10 секунд
Максимальная оценка: 20 баллов

Имеется N коробок, каждая выкрашена в свой отдельный цвет. В эти коробки положено M шаров, тех же N цветов. Расположение шаров по коробкам известно. Требуется разложить шары по коробкам так, чтобы в каждой коробке оказались только шары ее цвета и для перекладывания потребовалось минимальное число действий. Одним действием считается обмен двух шаров местами или перекладывание одного шара из коробки в коробку.

Формат входных данных

Во входном файле записаны числа N и M (2 ≤ N ≤ 10, 1 ≤ M ≤ 100). Далее следуют M пар чисел, задающих цвет очереднего шара и номер коробки, в которой он находится.

Формат выходных данных

В первую строку выходного файла выведите число действий K, требуемуемых для перекладывания шаров. Далее выведите К строк с тремя или четырьмя числами, описывающими действия в том порядке, в котором их следует производить. Если это перекладывание, то первое число означает номер коробки, откуда вынимается шар, второе число задает цвет шара, а третье число . номер коробки, в которую шар кладется. Если это действие обмен, то первые два числа означают номер коробки и цвет первого шара, а вторые два числа задают номер коробки и цвет второго шара.

Пример

input.txtoutput.txt
4 8
1 3
2 4
3 2
4 1
2 4
1 1
2 4
3 4
6
1 4 4 3
1 3 3 1
2 3 3
4 2 2
4 2 2
4 2 2

Задача C. Чаша Грааля

Имя входного файла: input.txt
Имя выходного файла: output.txt
Максимальное время работы на каждом тесте: 10 секунд
Максимальная оценка: 20 баллов

В конце полного приключений и опасностей путешествия Индиана Джонс добрался до входа в подземный замок крестоносцев, где хранится чаша Грааля. В руках у него находится план замка, состоящего из M этажей размера N×N. Хотя путь до чаши тернист и извилист, у профессора археологии есть все, что беспрепятственно передвигаться по замку – кнут, лестницы и динамит. Узкие коридоры и тупики-ловушки не могут остановить Джонса, единственной проблемой остаются преграды, которые необходимо взрывать, рискуя быть похороненным под обломками древнего замка. Напишите программу, определяющую наименьшее количество стен, которые необходимо уничтожить, чтобы можно было добраться до чаши Грааля.

Формат входных данных

В первой строке входного файла записаны числа M и N (1 ≤ M, N ≤ 20). Далее приведены планы M этажей, каждый из которых задан таблицей N×N символов, где символ "." (точка) означает свободное пространство, а "#" соответствует монолитной стене. Местоположение Индианы указано буквой "I", а чаши Грааля – буквой "G". Планы этажей разделяются пустыми строками.

Формат выходных данных

Выведите в выходной файл наименьшее количество стенок, которые требуется уничтожить, чтобы по образовавшимся полостям можно было добраться до чаши Грааля. Далее выведите в выходной файл план замка с разрушенными стенками в том же формате, что и в файле входных данных. Разрушенную стенку обозначайте на плане знаком "-". Пример входных данных выходных данных

Пример

input.txtoutput.txt
3 4
####
...#
####
###I

.###
##..
###.
####

G###
###.
###.
###.
2
-###
...#
####
###I

.###
##..
###.
###-

G###
###.
###.
###.

Задача D. Длинное число N

Имя входного файла: input.txt
Имя выходного файла: output.txt
Максимальное время работы на каждом тесте: 10 секунд
Максимальная оценка: 40 баллов

Во входном файле заданы числа N и M (0 ≤ M, N < 10100). Определите, сколько есть чисел, не превосходящих N, в десятичной записи которых встречается число M. Все числа рассматриваются без ведущих нулей.

Формат входных данных

В первой строке входного файла записано число N, а во второй – число M.

Формат выходных данных

Выведите в выходной файл искомое количество чисел. Сами числа выводить не надо.

Пример

input.txtoutput.txt
99
1
19