на первую страницу

Теория графов

Задача 4.1. Бумага с кляксами
Составитель В. Кузнецов
Входной файл: INPUT.TXT
Выходной файл: OUTPUT.TXT
Задание:
На прямоугольном листе бумаги в клетку поставлено несколько чернильных клякс, также прямоугольной формы. Определить минимальное расстояние, которое должен проползти муравей из левого нижнего в правый верхний угол листа бумаги, двигаясь только по неиспачканным вертикальным и горизонтальным линиям, если размеры листа MxN, а размеры клетки 1x1. Примечания:
1. Муравей не может выползать за край листа или двигаться по краю кляксы.
2. 1 Ј M, N Ј 100
Первая строка исходной информации - число клякс, вторая - координаты левого нижнего и правого верхнего углов листа бумаги, последующие, по количеству клякс, координаты левого нижнего и правого верхнего углов клякс. Результат работы программы - целое число, минимальное количество единичных отрезков, которые предстоит проползти муравью. Вывести -1, если муравей не сможет добраться до правого верхнего угла. Пример исходной информации:
2
0 0 6 6
0 2 5
4 1 5 6
Ответ для данного примера:
24

Задача 4.2. Прямоугольники
Составитель Д. Подкопаев
Входной файл: INPUT.TXT
Выходной файл: OUTPUT.TXT
Задание:
На клетчатом листе бумаги размера NxM (N, M Ј 100), нарисованы различные прямоугольники. Каждый прямоугольник состоит из целых клеток, разные прямоугольники не соприкасаются по сторонам или углам и не накладываются друг на друга. Необходимо найти число прямоугольников. Исходная информация - размеры листа бумаги N и M, в первой строке и далее матрица размером NxM, состоящая из 0 и 1 (0 - если клетка пустая и 1 - если она принадлежит какому-то прямоугольнику). Результат работы программы - число прямоугольников на листе. Пример исходной информации:
10 10
1 0 0 0 0 0 0 0 0 0
0 0 0 1 1 1 1 0 0 0
1 0 0 1 1 1 1 0 0 0
1 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 1 1 0 0 0 0 1 0 0
0 1 1 0 0 0 0 1 0 0
0 0 0 0 0 0 0 1 0 0
0 0 0 0 0 0 0 1 0 0
0 0 0 0 0 0 0 0 0 0
Ответ для данного примера:
5

Задача 4.3. Морской бой
Составитель Д. Подкопаев
Входной файл: INPUT.TXT
Выходной файл: OUTPUT.TXT
Задание:
На клетчатом листе бумаги размера MxN нарисованы корабли. Каждый корабль представляет собой вертикальный или горизонтальный набор подряд идущих закрашенных клеток. Разные корабли не соприкасаются по сторонам или углам и не накладываются друг на друга. В отличие от обычного "Морского боя" могут быть корабли более, чем из четырех клеток. Необходимо найти число кораблей. Пример: лист - 12x12, кораблей - 7.
Формат входных данных:
Входной файл INPUT.TXT содержит в первой строке два целых числа, разделенные пробелом, - размеры листа бумаги M и N, 2 Ј M, N Ј 100. Далее идет таблица из M строк по N целых чисел, разделенных пробелами, состоящая из 0 или 1 (0 - если клетка пустая, 1 - если она входит в состав какого-то корабля), одна строка таблицы располагается в одной строке файла. Пример:
12 12
0 0 0 0 0 0 0 0 0 0 0 1
0 1 1 1 1 1 0 0 0 0 0 1
0 0 0 0 0 0 0 1 0 0 0 1
0 1 0 0 0 0 0 0 0 0 0 0
0 1 0 0 0 0 0 0 0 0 0 0
0 1 0 1 1 1 1 1 1 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 1 0 0 0 0
0 0 0 0 0 0 0 1 0 0 0 0
0 0 0 0 0 0 0 1 0 0 0 0
0 0 0 0 0 0 0 1 0 0 0 0
0 1 1 0 0 0 0 0 0 0 0 0
Формат выходных данных:
Выходной файл OUTPUT.TXT должен содержать число (целое) кораблей на листе. Пример:
7

Задача 4.4. Заочное знакомство
Составитель В. Тарасов
Входной файл: INPUT.TXT
Выходной файл: OUTPUT.TXT
Задание:
Предположим, что n студенческих групп состоят из g1, g2,…, gn человек соответственно. В научной студенческой конференции принимали участие студенты из 1-ой и 2-ой групп. Несколько студентов из 2-ой группы заинтересовались докладами некоторых студентов из 1-ой группы и узнали их E-mail. В результате можно составить матрицу [m1ij], i = 1, ..., g1; j = 1, ..., g2 так, что m1ij = 1, если j-ый студент второй группы знает e-mail i-го студента первой группы, и m1ij = 0 в противном случае. В следующей научной студенческой конференции принимали участие студенты из 2-ой и 3-ей групп. Несколько студентов из 3-ей группы заинтересовались докладами некоторых студентов из 2-ой группы и узнали их e-mail. В результате можно составить матрицу [m2ij] i = 1, ..., g2; j = 1, ..., g3 так, что m2ij = 1, если j-ый студент третьей группы знает e-mail i-го студента второй группы, и m2ij = 0 в противном случае. И т.д. В последней научной студенче-ской конференции принимали участие студенты из n-1-ой и n-ой групп. Несколько студентов из n-ой груп-пы заинтересовались докладами некоторых студентов из n-1-ой группы и узнали их e-mail. В результате можно составить матрицу [mn-1ij] i = 1, ..., gn-1; j = 1, ..., gn так, что mn-1ij = 1, если j-ый студент n-ой груп-пы знает e-mail i-го студента n-1-ой группы, и mn-1ij = 0 в противном случае.
Если в процессе подготовки к новой конференции студенты n-ой группы захотят собрать как можно больше информации об аналогичных работах, то для этого они смогут послать сообщения известным им студентам n-1-ой группы с просьбой прислать копии работ и адреса известных им студентов, изучающих схожие про-блемы. Те в, свою очередь, смогут послать сообщения студентам n-2-ой группы и т. д. В результате этого можно будет составить матрицу [mij] i = 1, ..., g1; j = 1, ..., gn заочного знакомства так, что mij = 1, если j-ый студент n-ой группы знает e-mail h-го студента n-1-ой группы, а тот в свою очередь знает e-mail k-го студента n-2-ой группы, …, а тот в свою очередь знает e-mail l-го студента второй группы, а тот в свою очередь знает e-mail i-го студента первой группы, и mij = 0 в противном случае. Необходимо получить матрицу [mij] i = 1, ..., g1; j = 1, ..., gn заочного знакомства.
Формат входных данных:
Входной файл INPUT.TXT содержит в первой строке число студенческих групп n (целое), 3 * n * 9, во второй строке числа g1, g2,…, gn (число студентов в соответствующих группах), разделенные пробелами, 2 * gi * 20. Далее идет матрица [m1ij] i = 1, ..., g1; j = 1, ..., g2, одна строка матрицы располагается в одной строке файла. Сразу после нее идет матрица [m2ij] i = 1, ..., g2; j = 1, ..., g3, одна строка матрицы располагается в одной строке файла и т.д.. Последней идет матрица [mn-1ij] i = 1, ..., gn-1; j = 1, ..., gn, одна строка матрицы располагается в одной строке файла. Пример:
4
3 2 4 2
1 0
0 1
1 1
1 0 1 1
0 1 1 0
1 1
0 1
0 0
1 0
Формат выходных данных:
Выходной файл OUTPUT.TXT должен содержать матрицу [mij] i = 1, ..., g1; j = 1, ..., gn заочного знакомства, одна строка матрицы должна располагается в одной строке файла. Пример:
1 1
0 1
1 1

Задача 4.5. Замкнутый путь
Составитель А. Бедорев
Входной файл: INPUT.TXT
Выходной файл: OUTPUT.TXT
Задание:
Графом называется совокупность точек (вершин), некоторые из которых соединены между собой линиями. Графу, содержащему N вершин, можно сопоставить матрицу соединений размера N * N. Элемент Ai,j матрицы соединений равен 1, если i-я вершина соединена с j-й. Так, графу, изображенному на рисунке,

                   1


                  2           3

                  4           5


              6       7    8      9
сопоставляется матрица соединений:
0 1 1 0 0 0 0 0 0
1 0 0 1 0 0 0 0 0
1 0 0 0 1 0 0 0 0
0 1 0 0 0 1 1 0 0
0 0 1 0 0 0 0 1 1
0 0 0 1 0 0 1 0 0
0 0 0 1 0 1 0 1 0
0 0 0 0 1 0 1 0 1
0 0 0 0 1 0 0 1 0
Дана матрица соединений графа, содержащего N вершин. Требуется выяснить, существует ли такой замкнутый путь, проходящий по линиям графа, который проходит через все вершины по одному разу. Число вершин N находится в диапазоне 3 * N < 50. Формат входных данных:
Входной файл INPUT.TXT содержит в первой строке число - размерность матрицы соединений. Каждая последующая строка файла содержит очередную строку матрицы соединений, элементы которой отделены одним пробелом. Матрица соединений симметрична относительно главной диагонали. Пример:
4
0 1 1 0
1 0 0 1
1 0 0 1
0 1 1 0
Формат выходных данных:
Выходной файл OUTPUT.TXT должен содержать 0 в том случае, если замкнутого пути, проходящего через каждую из вершин графа по одному разу не существует. В случае, если такой путь существует, то первая строка выходного файла должна содержать 1. Пример:
1

Элементарная алгебра

Задача 5.1. Детерминант матрицы
Составитель А. Веретин
Задание:
Задана квадратная матрица АNxN, элементами которой являются целые числа от -1000 до 1000. Найти ее детерминант. Формат входных данных:
В первой строке входного файла DETERM.IN задана размерность матрицы N. Далее в N строках заданы коэффициенты матрицы, разделенные пробелом (в одной строке файла одна строка матрицы). Пример:
3
0 6 4
5 0 7
0 3 1
Формат выходных данных:
В выходном файле DETERM.OUT выведено одно число, являющееся значением детерминанта матрицы. Пример:
30

Задача 5.2. Обратная матрица
Составитель А. Веретин
Задание:
Задана квадратная матрица АNxN, элементами которой являются целые числа от -1000 до 1000. Найти ее обратную матрицу, если она существует. Формат входных данных:
В первой строке входного файла REVERS.IN задана размерность матрицы N. Далее в N строках заданы коэффициенты матрицы, разделенные пробелом (в одной строке файла одна строка матрицы). Пример:
3
0 6 4
5 0 7
0 3 1
Формат выходных данных:
Первая строка выходного файла REVERS.OUT содержит 1 - если обратная матрица существует, или 0 - если ее нет. Далее (если матрица существует) следует обратная матрица (в одной строке файла одна строка матрицы). Числа округлять до второго знака после запятой. Пример:
1
0 0.2 1.4
0.17 0 0.67
0 0 -1

Задача 5.3. Единицы
Составитель С. Русаков
Задание:
Задано десятичное представление целого числа n в диапазоне от -32768 до 32767. Найти количество единиц m в двоичном представлении числа n. Формат входных данных:
Во входном файле BINARY.IN содержится десятичное представление числа n. Пример:
134
Формат выходных данных:
В выходном файле BINARY.OUT содержится число m - количество единиц в двоичном представлении числа n. Пример:
3

Задача 5.4. Период дроби
Составитель Д. Подкопаев
Входной файл: INPUT.TXT
Выходной файл: OUTPUT.TXT
Задание:
Даны натуральные числа M и N (M, N Ј 1000) . Определить период десятичной дроби M/N. Если дробь конечная, то ее период состоит из одной цифры 0.
Исходная информация - два числа: M и N
Результат работы программы - длина периода в первой строке и цифры периода в последующих строках не более 100 в строке, в строках с цифрами периода не должно быть символов отличных от '0', '1', '2', '3', '4', '5', '6', '7', '8', '9'.
Пример исходной информации:
1 7
Ответ для данного примера:
6
42857

Задача 5.5. Полином
Составитель ???
Входной файл: INPUT.TXT
Выходной файл: OUTPUT.TXT
Задание:
Представить полином
e Pn(x) = a0 * ( x - a1) * ( x - a2) * ... * ( x - an)
в виде
b0 · xn + b1 · xn-1 + b2 · xn-2 + ... + bn.
Исходная информация - Первая строка исходной информации - степень полинома n, вторая - целые числа, коэффициенты a0, a1, a2, ... an, разделенные пробелами. (N Ј 50, -215+1 Ј a0, a1, a2, ... an Ј 215-1) Результат работы программы - целые числа b0, b1, b2, ... bn, по одному в строке. Пример исходной информации
2
1 2 3
Ответ для данного примера:
1
-5
6

Задача 5.6. Коэффициенты полинома
Составитель С. Русаков ???
Составитель В. Кузнецов ???
Входной файл: INPUT.TXT
Выходной файл: OUTPUT.TXT
Задание:
Известны корни полинома P(x) = a0 + a1 * x + ... + an-1 * x(n-1) + xn, an = 1. Рассчитать коэффициенты a0, ..., an-1.
1 * n * 10, корни xi - целые числа. x1 * ... * xn * 100.000.000 Формат входных данных:
Входной файл INPUT.TXT:
первая строка - степень полинома n;
вторая строка - первый корень;
...
n + 1 -я строка - n -ый корень;
Пример:
2
1
0
Формат выходных данных:
Выходной файл OUTPUT.TXT:
строка содержит коэффициенты a0, ..., an, разделенные пробелом. Пример:
0 -1 1

Логика и синтаксический анализ

Задача 6.1. Вычисление значений арифметических выражений
Составитель В. Тарасов
Задание:
Вычислить значение арифметического выражения, содержащего знаки бинарных арифметических операций, натуральные числа, отличные от нуля, и, возможно, скобки. Арифметические операции: +, -, *, ^, где ^ обозначает возведение в степень. Показатель степени всегда является натуральным числом, показатель и основание степени не могут быть равны нулю одновременно. Результаты всех промежуточных вычислений и значение самого выражения находятся в пределах: [-2147483648, 2147483647]. Формат входных данных Входной файл EXPR_VAL.IN содержит несколько выражений, каждое в отдельной строке. Максимальная длина выражения - 150 символов. Признаком конца файла является строка, состоящая из нуля. Пример:
21+3*(9-11)
4^2*8
0
Формат выходных данных:
Выходной файл EXPR_VAL.OUT должен содержать номер выражения в следующем формате: "Expression #n", где n - порядковый номер выражения во входном файле, на следующей строке - значение выражения, и, далее, пустую строку. Хвостовые пробельные символы в конце строк не допускаются. За значением последнего выражения сразу идет символ конца файла. Пример:
Expression #1
15
Expression #2
128

Задача 6.2. Вхождения логических формул
Составитель В. Тарасов
Задание:
Определить сколько вхождений формулы B содержит формула A. Формула определяется следующим образом:
(a) все пропозициональные буквы (заглавные буквы латинского алфавита A,B,...,Z) суть формулы; (b) если A и B - формулы, то (!A), (A&B), (A|B) тоже формулы (где ! - отрицание, & - конъюнкция, | - дизъюнкция); (c) выражение является формулой только в том случае, если это следует из правил (a) и (b). Подформулами данной формулы называются те формулы, которые строятся в процессе построения данной формулы в соответствии с правилами (a) - (c), включая и саму данную формулу. Формула A содержит вхождение формулы B, если существует подформула C формулы A, такая что C и B совпадают. С целью сокращения записи формул в дальнейшем будут опускаться внешние скобки, а также часть внутренних скобок, которые могут быть восстановлены на основе приписывания логическим связкам возрастающего приоритета следующим образом: |, &, !, причем ! является правоассоциируемой, остальные - лево-ассоциируемые. В соответствии с этими соглашениями, например, !E|F&G означает ((!E)|(F&G)). Формат входных данных:
Входной файл FORMOCCU.IN содержит в первой строке число пар формул A и B. Далее следует пустая строка. Затем идут пары формул A и B следующим образом. Сначала идет формула A, которую надо проверить на наличие вхождений, следующая строка содержит формулу B, вхождения которой надо искать. Максимальная длина формулы - 185 символов. Пары формул разделяются пустой строкой. Пример:
2
A&D&B|!D
D
B|E|A|(C|A)
C|A
Формат выходных данных:
Выходной файл FORMOCCU.OUT должен содержать номер пары формул в следующем формате: "Pair #n", где n - порядковый номер пары формул во входном файле, на следующей строке - число вхождений, и, далее, пустую строку. Хвостовые пробельные символы в конце строк не допускаются. За последним числом вхождений сразу идет символ конца файла. Пример:
Pair #1
2
Pair #2
1

Задача 6.3. Унификация термов
Составитель В. Тарасов
Задание:
Найти наиболее общий унификатор для двух заданных термов. Терм определяется следующим образом:
(a) всякая предметная переменная (обозначается буквами латинского алфавита u,x,y,z) или предметная константа (обозначается буквами латинского алфавита a,b,c,d) есть терм; (b) если f функциональная буква (обозначается буквами латинского алфавита f,g,h,j) и t1, t2 -термы, то f(t1,t2) есть терм; (c) выражение является термом только в том случае, если это следует из правил (a) и (b). Подстановка - это конечное множество вида {v1/t1,...,vn/tn}, где каждая vi- переменная,.каждый ti- терм, отличный от vi, все vi различны. Подстановка, которая не содержит элементов, называется пустой и обозначается {}. Пусть W={v1/t1,...,vn/tn} - подстановка и T- терм. Тогда TW -терм, полученный из T заменой одновременно всех вхождений переменной vi (i=1,...,n) в T на терм ti. Пусть W={x1/t1,...,xn/tn} и V={y1/u1,...,yn/un} - две подстановки. Тогда композиция W и V есть, подстановка (обзначается W°V), которая получается из множества {x1/t1V,...,xn/tnV,y1/u1,...,yn/un} вычеркиванием всех элементов xi/tiV, для которых xi=tiV и всех элементов yi/ui таких, что yiО{x1,...,xn}. Подстановка W называется унификатором для термов T1 и T2 тогда и только тогда, когда T1W=T2W. Унификатор W для множества термов будет наиболее общим унификатором тогда и только тогда, когда для каждого унификатора S для этого множества существует такая подстановка V, что S=W°V. Формат входных данных:
Входной файл TERMUNIF.IN содержит в первой строке число пар термов. Далее следует пустая строка. Затем идут пары термов, для которых нужно найти наиболее общий унификатор. Пары термов содержат не более одного вхождения каждой из предметных переменных и разделяются пустой строкой. Максимальная длина терма - 291 символ. Пример:
2
f(g(a,u),y)
f(x,z)
h(f(c,z),g(b,d))
h(f(d,a),x)
Формат выходных данных:
Выходной файл TERMUNIF.OUT должен содержать номер пары термов в следующем формате: "Pair #n", где n - порядковый номер пары термов во входном файле, на следующей строке - наиболее общий унификатор, если он существует, или строку "Not unified", если унификатор не существует. Далее - пустую строку. Если в элементе подстановки vi/ti и vi и ti являются переменными, то первой указывается переменная, относящаяся к первому терму. Хвостовые пробельные символы в конце строк не допускаются. За последним унификатором сразу идет символ конца файла. Пример:
Pair #1
{x/g(a,u);y/z}
Pair #2
Not unified

Задача 6.4. Преобразование простого арифметического выражения
Составитель В. Тарасов
Входной файл: INPUT.TXT
Выходной файл: OUTPUT.TXT
Задание:
Простое арифметическое выражение определяется следующим образом:
(a) буква есть простое арифметическое выражение; (b) если P и Q - простые арифметические выражения, то (P), P+Q, P-Q, P*Q или P/Q - простое арифметическое выражение; (c) выражение является простым арифметическим только в том случае, если это следует из правил (a) и (b); где буква это "a", или "b", или "c", … , или "z" (строчные буквы латинского алфавита). Арифметические операции упорядочены по возрастанию приоритета обычным образом: (1) "+", "-"; (2) "*", "/". Постфиксная форма записи простого арифметического выражения определяется следующим образом: (i) если простое арифметическое выражение есть буква, то постфиксная форма есть эта буква; (ii) если простое арифметическое выражение имеет вид (P), то постфиксная форма есть P; (iii) если простое арифметическое выражение имеет вид P знак_операции Q, то постфиксная форма есть P Q знак_операции; где P и Q - простые арифметические выражения. Например, для выражения (a+b)*c постфиксной формой будет ab+c* . Преобразовать заданное простое арифметическое выражение в постфиксную форму. Формат входных данных Входной файл INPUT.TXT содержит в первой строке натуральное число n, 1 * n * 100, - длину простого арифметического выражения (количество символов) и во второй строке - само простое арифметическое выражение, за которым следует перевод строки. Пример:
5
r+t*s
Формат выходных данных:
Выходной файл OUTPUT.TXT должен содержать постфиксную форму записи простого арифметического выражения. Постфиксная форма не должна содержать символов пробела, табуляции, перевода строки и должна быть расположена в первой строке файла. Пример:
rts*+

Председатель жюри:
Дьяконов Максим Валерьевич
e-mail: mdia{at}cs.karelia.ru