ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам |
К задаче N

Проект МЦНМО
при участии
школы 57
Фильтр
Сложность с по   Класс с по  
Выбрана 1 задача
Версия для печати
Убрать все задачи

Булевой функцией называется функция, принимающая одно из логических значений 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)

   Решение

Задачи

Страница: 1 2 >> [Всего задач: 6]      



Задача 102930

 [Жизнь бактерий ]
Тема:   [ Задачи на полный перебор ]
Сложность: 3

Игра «Жизнь» является упрощенной моделью развития колонии бактерий. Игровое поле для этой игры представляет собой прямоугольник M × N клеток. В начальный момент времени в некоторых клетках находятся бактерии. За один шаг игры некоторые бактерии могут погибнуть, а некоторые родиться на свободных клетках в соответствии со следующими правилами: 
    1) бактерия, у которой есть не более одной соседки, погибает «от скуки»; 
    2) бактерия, у которой есть более трех соседок, погибает «от тесноты»; 
    3) на свободной клетке, у которой есть ровно три соседние бактерии, рождается новая бактерия.
Все эти правила применяются одновременно ко всем клеткам игрового поля. Клетки считаются соседними, если у них есть хотя бы одна общая точка. Напишите программу, которая: 
    по заданной колонии находит ее предка, то есть колонию, чьим следующим поколением она является, либо сообщает, что это невозможно;
    находит колонию, у которой нет предка, и которая погибает не ранее, чем через L шагов, либо сообщает, что такой колонии не существует.

Входные данные

Если во входном файле записана матрица M × N (2 ≤ M, N ≤ 15), то программа должна решать пункт 1 задачи для колонии бактерий, задаваемой этой матрицей. Бактерии обозначаются символом *, а пустые клетки – символом . (точка). Если во входном файле заданы три числа M, N и L (2 ≤ M, N ≤ 10, 0 ≤  L ≤ 10), то программа должна решать пункт 2 для этих параметров.

Выходные данные

Если искомая колония существует, то ее следует вывести в выходной файл в формате, приведенном в описании входных данных к пункту 1. В противном случае ваша программа должна записать в выходной файл сообщение «NOT POSSIBLE».

Пример входного файла для пункта 1

...
***
...


Пример выходного файла для пункта 1

.*.
.*.
.*.


Пример входного файла для пункта 2

2 2 10

Пример выходного файла для пункта 2

*.
**

Прислать комментарий     Решение

Задача 102927

 [Кроссворд ]
Тема:   [ Задачи на полный перебор ]
Сложность: 3+

Задан набор из N слов, из которых требуется составить связный кроссворд. Слова в кроссворде должны располагаться либо вертикально, либо горизонтально, причем каждое слово, записанное по вертикали, должно пересекаться с каждым словом, записанным по горизонтали. Слова, записанные в одном направлении, отделяются друг от друга как минимум одним пустым рядом. Каждое слово в кроссворде должно встречаться в точности столько раз, сколько раз оно присутствует в наборе.

Входные данные

Первая строка входного файла содержит целое число N – количество слов в наборе (1 ≤ N ≤ 9). В каждой из N последующих строк содержится по одному слову (некоторые из них могут повторяться). Слово представляет собой последовательность не более чем из 20 русских и/или английских букв.

Выходные данные

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

Пример входного файла

СБОРЫ
СОН
ПОТОП
АНТОН

Пример выходного файла

П
СБОРЫ
О Т
АНТОН
П
Прислать комментарий     Решение


Задача 102923

 [Круги ]
Тема:   [ Задачи на полный перебор ]
Сложность: 3+

Задан круг, разделенный на N секторов, и два целых числа M и K. В каждый из секторов круга помещается одно целое число, не меньшее K. Когда секторы заполнены числами, из них можно получать новые числа по следующим правилам:
    взять число из одного сектора;
    взять число, равное сумме двух или более чисел в смежных секторах.
Из новых чисел составляется наибольшая последовательность подряд идущих чисел, начинающаяся с числа M: (M, M+1, M+2, ..., I).

Пример на рисунке показывает, как получить все новые числа от 2 до 21 для приведенных на нем чисел в секторах. Серым цветом выделены суммируемые числа.


Напишите программу, которая определяет способ расстановки чисел в секторах, максимизирующий длину указанной последовательности.

Входные данные

Входной файл содержит три целых числа N, M и K (N ≤ 6, M ≤ 20, 0 ≤ K ≤ 20).

Выходные данные

Выведите в первую строку выходного файла наибольшее число I для неразрывной последовательности новых чисел от M до I, которая может быть получена из чисел в секторах. Далее выведите все наборы чисел в секторах, из которых можно получить такую последовательность. Каждый набор записывается в отдельную строку выходного файла в виде списка чисел, начинающегося с наименьшего из них (оно может быть не единственным). Числа в списке должны идти в том же порядке, в котором они записаны в секторах круга. Если наименьшее число встречается несколько раз, следует вывести все возможные комбинации. Например, (1 1 2 3), (1 2 3 1), (1 3 2 1) и (1 1 3 2).

Пример входного файла

5
2
1

Пример выходного файла

21
1 3 10 2 5
1 5 2 10 3
2 4 9 3 5
2 5 3 9 4
Прислать комментарий     Решение


Задача 102950

 [Булевы функции ]
Тема:   [ Задачи на полный перебор ]
Сложность: 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)
Прислать комментарий     Решение


Задача 102929

 [Максимальный M-угольник ]
Тема:   [ Задачи на полный перебор ]
Сложность: 4-

Заданы N различных точек плоскости и натуральное число M. Требуется найти максимальный по площади невырожденный M-угольник без самопересечений и самокасаний, вершинами которого являются некоторые из этих N точек.

Входные данные

В первой строке входного файла через пробел записаны два целых числа M и N (3 ≤ M ≤ N ≤ 10). Во второй строке перечислены N точек, каждая из которых задана парой своих координат. Координаты являются вещественными числами и разделяются пробелом.

Выходные данные

В первую строку выходного файла нужно вывести площадь искомого M-угольника, а во вторую – номера точек, являющихся вершинами этого M-угольника (в порядке обхода по или против часовой стрелки). Номера точек разделяются пробелом. Если вариантов решений несколько, то достаточно выдать любой из них. Если же ни один M-угольник с указанными свойствами построить невозможно, то выходной файл должен содержать единственное число 0.

Пример входного файла

3 4
0 0 0 1 1 0 1 1

Пример выходного файла

0.5
1 2 3
Прислать комментарий     Решение


Страница: 1 2 >> [Всего задач: 6]      



© 2004-... МЦНМО (о копирайте)
Пишите нам

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .