Шаблоном называется строка, состоящая из английских букв (a, ..., z, A, ..., Z) и символов ? и *. Каждый из символов ? разрешается заменить на одну произвольную букву, а каждый из символов * – на произвольную (возможно пустую) последовательность букв. Про любую строку из букв, которую можно получить из шаблона такими заменами, будем говорить, что она удовлетворяет этому шаблону.

Имеются два шаблона. Требуется найти строку минимальной длины, которая удовлетворяет обоим шаблона, либо выдать сообщение, что такой строки не существует.

Входные данные
Заданные шаблоны записаны в первых двух строках входного файла. Длина каждого шаблона не превосходит 80 символов.

Выходные данные
В выходной файл следует вывести строку минимальной длины, удовлетворяющую обоим шаблонам, либо сообщение «Строки не
существует!»

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

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

   Решение

Страница: << 1 2 3 4 [Всего задач: 20]      

Имя входного файла:	net.in
Имя выходного файла:	net.out
Максимальное время работы на одном тесте:	1 секунда
Максимальный объем используемой памяти:	64 мегабайта
Максимальная оценка за задачу:	100 баллов

Петя и Вася нашли на чердаке остатки рыболовной сети своего деда. Часть веревок давно сгнила, и сеть распалась на большое число кусков, каждый из которых состоит не более чем из 50 веревочек единичной длины.

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

Решение

Жюри составило отчет об учебно-тренировочных сборах по информатике и собирается распечатать его на стандартном листе бумаги. Весь отчет набран одним моноширинным шрифтом, т.е. все символы (включая пробелы) имеют одинаковую ширину. Длина строки при печати этим шрифтом на листе бумаги равна S.

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

Для достижения требуемого расположения текста на бумаге разрешается заменять произвольную пробельную последовательность (т.е. непустую последовательность подряд идущих пробелов и/или символов перевода строки) любой другой пробельной последовательностью.

Входные данные
Первая строка входного файла содержит целое число S (1 ≤ S ≤ 80). В последующих строках записан отчет, содержащий не более 500 слов. Длина каждой строки отчета не превосходит 250 символов, а длина каждого слова не превосходит S.

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

Пример входного файла
30
Победители летних учебно-тренировочных сборов по
информатике 1997 г.:
Владимир Мартьянов,
Анатолий Пономарев,
Николай Дуров, Андрей Лопатин.

Пример выходного файла
325
    Победители     летних
учебно-тренировочных сборов по
 информатике 1997 г.: Владимир
Мартьянов, Анатолий Пономарев,
Николай Дуров, Андрей Лопатин.

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

Решение

Имеется таблица M × N, в каждой ячейке которой записано либо целое число, либо арифметическая формула. В формулах могут присутствовать целые числа, знаки *, /, +, -, (, ), пробелы и ссылки на значения из других ячеек таблицы, записываемые в виде {НомерCтроки, НомерCтолбца} (например, {1,10}). Требуется вычислить значения во всех ячейках заданной таблицы.

Входные данные:
В первой строке входного файла записаны целые числа M и N (1 ≤ M, N ≤ 20). В каждой из последующих M строк содержится описание очередной строки таблицы. Описание состоит из целых чисел и арифметических формул, разделенных символами | (ASCII-код 124). Все числа принадлежат диапазону [-32768, 32767], а длина каждой формулы не превышает 100 символов.

Выходные данные:
Выведите в выходной файл значения всех ячеек таблицы. Значения ячеек каждой строки таблицы должны быть записаны через пробел в отдельной строке выходного файла. Все значения следует выводить с точностью до двух знаков после десятичной точки. Если значение ячейки вычислить невозможно, вместо него следует вывести символ - (ASCII-код 45).

Пример входного файла
2  3
  1      |    {1, 1   }*10        +3 |     -{1,2}/{2,2}
{2,3} |             0                     |           {2,1}

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

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

Решение

Шаблоном называется строка, состоящая из английских букв (a, ..., z, A, ..., Z) и символов ? и *. Каждый из символов ? разрешается заменить на одну произвольную букву, а каждый из символов * – на произвольную (возможно пустую) последовательность букв. Про любую строку из букв, которую можно получить из шаблона такими заменами, будем говорить, что она удовлетворяет этому шаблону.

Имеются два шаблона. Требуется найти строку минимальной длины, которая удовлетворяет обоим шаблона, либо выдать сообщение, что такой строки не существует.

Входные данные
Заданные шаблоны записаны в первых двух строках входного файла. Длина каждого шаблона не превосходит 80 символов.

Выходные данные
В выходной файл следует вывести строку минимальной длины, удовлетворяющую обоим шаблонам, либо сообщение «Строки не
существует!»

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

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

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

Решение

Уважаемые господа! Сегодня вам предлагается для каждого из следующих типов комбинаторных объектов:
    1) перестановки N-элементного множества (лексикографический порядок);
    2) K-элементные подмножества N-элементного множества (лексикографический порядок);
    3) разбиения N-элементного множества на K непустых подмножеств (лексикографический, т.е. алфавитный, порядок);
    4) разбиения числа N на слагаемые;
    5) правильные скобочные последовательности из 2N скобок;
    6) двоичные деревья с N вершинами;
    7) цепочки из нулей и единиц длины N без двух единиц подряд;
    8) перестановки N-элементного множества (порядок, в котором соседние перестановки отличаются транспозицией соседних элементов);
    9) K-элементные подмножества N-элементного множества (порядок, в котором соседние подмножества отличаются двумя элементами);
    10) все подмножества N-элементного множества (порядок, в котором соседние подмножества отличаются добавлением или удалением одного элемента);
    11) подвешенные деревья с N вершинами;
решить следующие две подзадачи:
    найти общее количество объектов и породить M объектов, начиная с L-го;
    по заданным объектам получить их номера.
В качестве N-элементного множества везде подразумевается множество {1, ..., N}. Там, где порядок порождения комбинаторных объектов не указан, Вы можете выбрать его по своему усмотрению. Нумерация объектов начинается с нуля.

Таким образом, Вам предстоит написать 11 программ. Задача засчитывается, если Ваша программа прошла все тесты, в противном случае
Вам начисляются штрафные баллы за неверный подход (20% от стоимости задачи), и Вы имеете возможность исправить решение.
В зависимости от того, какую из подзадач требуется решить, входной и выходной файлы имеют один из следующих двух форматов (тем самым, Ваша программа должна сама определять номер решаемой подзадачи).

Входные данные для подзадачи 1
N K L M

Выходные данные для подзадачи 1
<Число объектов>
<Объект номер L>
...
<Объект номер L+M-1>
Каждый объект должен выводиться с новой строки. Формат вывода объектов
остается на Ваше усмотрение с условием, что он должен быть читабельным.

Входные данные для подзадачи 2
N K
<Объект 1>
...
<Объект M>
Формат записи объектов будет соответствовать выходному формату, используемому Вашей программой при решении подзадачи 1.

Выходные данные для подзадачи 2
<Номер объекта 1>
...
<Номер объекта M>
Каждый номер должен быть выведен с новой строки.

Технические ограничения
Если в данной задаче число K не используется, то вместо него будет указан нуль. Числа N и K во всех задачах не превосходят 100, число L не превышает 2·10⁹ , число M – 10 000. Номера объектов в подзадаче 2 не будут превышать 2.1·10⁹. Все входные данные корректны.

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

Решение

Страница: << 1 2 3 4 [Всего задач: 20]