Требуется подсчитать количество последовательностей длины N, состоящих из 0 и 1, в которых никакие две единицы не стоят рядом.

Входные данные
Во входном файле записано целое число N (1 ≤ N ≤ 100).

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

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

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

   Решение

Заданы N-вершинный ориентированный граф с двумя выделенными вершинами v₁ и v₂ и целое число C. Требуется:
1) определить, существует ли в заданном графе путь из вершины v₁ в вершину v₂, состоящий из C ребер (путь может иметь самопересечения как по вершинам, так и по ребрам);
2) найти минимум функции | X - C |, где X – количество ребер в некотором пути из v₁ в v₂ .

Входные данные
Первая строка входного файла содержит целое число N – количество вершин в графе (1 ≤ N ≤ 10). В следующих N строках расположена матрица N × N из нулей и единиц, элемент (i, j) которой равен единице, если в графе есть ребро из вершины i в вершину j, и нулю, если такого ребра нет. (Граф может содержать петли, т.е. ребра, идущие из вершины в саму себя). Элементы матрицы во входном файле записаны без разделительных пробелов. 

Наконец, строка N+2 содержит номера вершин v₁ и v₂ , а строка N+3 – десятичную запись числа C (1 &le C < 10⁵⁰).

Выходные данные
В первую строку выходного файла выведите ответ на первый пункт задачи: «Yes», если путь длины C существует, и «No», если нет. Во вторую строку запишите ответ на второй пункт задачи. Если ни одного пути из v₁ в v₂ не существует, ваша программа должна вывести -1.

Пример входного файла
3
010
001
100
1 1
555555555555555555555555555555555

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

   Решение

Во входном файле записано равенство вида A = B, где A и B – это выражения, содержащие сколь угодно длинные целые числа и знаки операций +, - (бинарный и унарный) и *. Выражения не содержат скобок. Требуется проверить выполнение заданного равенства и вывести в выходной файл результат проверки в форме «Да, выполняется» или «Нет, не выполняется».
Длина входного файла данных не превосходит 60 килобайт. Числа и знаки операций в выражении могут разделяться пробелами и/или символами перевода строки.

Пример входного файла
2
                * 43 = 86

Пример выходного файла
Да, выполняется

   Решение

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

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

Входные данные
Исходное выражение длиной не более 250 символов записано в первой строке входного файла. Выражение содержит не более 50 чисел, каждое из которых лежит в диапазоне от 0 до 10⁶ . Пробелы внутри чисел не допускаются.

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

Пример входного файла
1+2 - 3.0*4

Пример выходного файла
0
((1+2)-3)*4

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

Решение

Уважаемые господа! Сегодня вам предлагается для каждого из следующих типов комбинаторных объектов:
    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 [Всего задач: 7]