Версия для печати
Убрать все задачи
Города и дороги
В галактике "Milky Way" на планете "Neptune" есть N городов,
некоторые из которых соединены дорогами. Император "Maximus"
галактики "Milky Way" решил провести инвентаризацию дорог
на планете "Neptune". Но, как оказалось, он не силен в математике,
поэтому он просит вас сосчитать количество дорог.
Входные данные. В файле INPUT.TXT записано число N (0<=N<=100).
В следующих N строках записано по N чисел, каждое из которых
является единичкой или ноликом. Причем, если в позиции (i,j)
квадратной матрицы стоит единичка, то i-ый и j-ый города соединены дорогами,
а если нолик, то не соединены.
Выходные данные. В файл OUTPUT.TXT вывести одно число - количество дорог
на планете "Neptune".
Примечание. Все дороги двусторонние, то есть если есть дорога
из города i в город j, то есть и дорога из города j в город i,
и это та же самая дорога.
Пример файла INPUT.TXT
5
0 1 0 0 0
1 0 1 1 0
0 1 0 0 0
0 1 0 0 0
0 0 0 0 0
Пример файла OUTPUT.TXT
3
Решение
Булевой функцией называется функция, принимающая одно из логических
значений TRUE или FALSE и зависящая от некоторого (быть может, нулевого)
количества аргументов, каждый из которых также может принимать любое из
значений TRUE или FALSE.
Любая булева функция однозначно задается своей таблицей истинности, в
которой для каждого возможного набора значений аргументов указано значение
функции. Например, x AND y – булева функция от двух аргументов. Ее
таблица истинности выглядит так:
Если договориться, что наборы значений аргументов в таблице
располагаются в лексикографическом порядке, то функция AND однозначно
задается третьим столбцом таблицы – строкой 0001. Аналогично, каждой
булевой функции от k аргументов можно поставить в соответствие строку из
нулей и единиц длины 2k.
Задан набор из N+1 булевой функции (f, f1, f2, ..., fN). Напишите программу,
которая определяет, можно ли функцию f выразить через функции f1, f2, ..., fN, и
если такие представления возможны, то находит кратчайшее по числу символов
среди них.
Входные данные
В первой строке входного файла записано целое число N (1 ≤ N ≤ 9).
Последующие N+1 строк содержат описания функций
f, f1, f2, ..., fN соответственно. Каждая из функций описывается строкой символов так, как
указано выше. Число аргументов у функции f будет не более двух, а у остальных
функций – не более трех.
Выходные данные
Первая строка выходного файла должна содержать искомое символьное
представление, либо строку «Impossible», если такого представления не
существует. После функции с нулевым числом аргументов скобки не ставятся.
Если у функции f один аргумент, то он обозначается x, а если два, то они
обозначаются x и y.
Пример входного файла
2
1
1010
0
Пример выходного файла
f1(f2,f2)
Решение
n одинаковых монет лежат на столе, образуя замкнутую цепочку. Центры монет образуют выпуклый многоугольник. Сколько оборотов сделает монета такого же размера за время, пока она один раз прокатится по внешней стороне всей цепочки, как показано на рисунке?
Как изменится ответ, если радиус этой монеты в k раз больше радиуса каждой из монет цепочки?
Решение
Фильтр
