Тексты задач для тренировочных интернет-туров по информатике для размещения на сайте school-collection. edu. ru (стр. 6 )

Примеры

Примечание

Векторы а1, а2, ..., ап называются линейно независимыми, если из того, что λ1а1 + λ2а2 + ...  + λnап = 0, следует, что λ1 = λ2 = ...  = λn = 0.

Задача D. Кактусы

Имя входного файла: cacti. in

Имя выходного файла: cacti. out

Ограничение по времени: 2 секунды

Ограничение по памяти: 256 мебибайт

Связный граф называется кактусом, если каждое его ребро лежит не более чем на одном цикле. На рисунках ниже приведены примеры кактусов и не кактусов.

По заданному п нужно найти количество помеченных кактусов с п вершинами.

Требуется написать программу, которая выводит это количество по модулю 109 + 7.

Формат входных данных

Входной файл содержит число п (1 ≤ п ≤ 500).

Формат выходных данных

Выходной файл должен содержать одно число – количество кактусов с п вершинами по модулю 109 + 7.

Примеры

Задача E. Разбиения на пары

Имя входного файла: pairings. in

Имя выходного файла: pairings. out

Ограничение по времени: 2 секунды

Ограничение по памяти: 64 мебибайта

Разбиением на пары множества чисел {1, 2, ..., 2n} назовём набор из n пар чисел, в котором каждое число от 1 до 2n, включительно, встречается ровно один раз. Записывается разбиение на пары так: сначала числа внутри каждой пары сортируются по возрастанию, затем сами пары сортируются по возрастанию первых чисел, и наконец, пары выписываются в строчку по порядку. Разбиения считаются одинаковыми, если они имеют одинаковую запись.

Так, например, для n = 2 существует всего три различных разбиения множества чисел {1, 2, 3, 4} на пары. Они записываются так:

Вася и Петя поспорили, кто из них быстрее выпишет все разбиения на пары множества чисел {1, 2, ..., 2п}. Оба одновременно берут по листку бумаги и начинают выписывать все разбиения на пары в лексикографическом порядке. Одно разбиение идёт в этом порядке раньше другого, если для некоторого к от 0 до (2п – 1), включительно, первые к чисел в их записи совпадают, а (к + 1)-е число первого разбиения меньше, чем (к + 1)-е число второго разбиения.

Оказалось, что Вася выписывает одно разбиение ровно две секунды, а Петя — ровно одну секунду. Вася хочет знать, какое разбиение В выписывал Петя в ту секунду, когда сам Вася заканчивал выписывать некоторое разбиение А.

Требуется написать программу, которая выяснит это для Васи, чтобы не отвлекать его от процесса выписывания разбиений.

Формат входных данных

В первой строке входного файла задано целое число п (1 ≤ п ≤ 17).

Во второй строке записаны 2п целых чисел через пробел – разбиение А, выписанное Васей. Скобки в записи разбиения опущены для удобства чтения.

Формат выходных данных

Если Петя уже выписал все разбиения до той секунды, в которую Вася закончил выписывать разбиение А, необходимо вывести в первой строке выходного файла фразу «Already finished!» без кавычек. В противном случае, необходимо вывести в первой строке выходного файла 2п целых чисел через пробел – запись разбиения В, выписанного Петей, также без скобок.

Программы, всегда выводящие «Already finished!», будут оценены в 0 баллов.

Примеры

6.  Описание заданий для шестого интернет-тура

На шестом туре было предложено 4 задачи: задача A «Связность», задача B «Драйверы», задача C «Наследство» и задача D «Тетрис». Тексты задач представлены ниже.

Задача A. Связность

Имя входного файла: стандартный ввод

Имя выходного файла: стандартный вывод

Ограничение по времени: 2 секунды

Ограничение по памяти: 256 мегабайт

Задан ориентированный граф из п вершин и т1 рёбер. Известно, что в графе есть вершины s и t такие, что все вершины достижимы из s, и из всех вершин достижима t. Также на том же множестве вершин задано другое множество рёбер, состоящее из т2 элементов. Рёбрам из этого множества приписаны некоторые целые веса.

Необходимо добавить к графу некоторые рёбра из второго множества так, чтобы выполнялись следующие требования:

•  граф с добавленными рёбрами должен быть сильно связным (каждая вершина должна быть достижима из каждой),

•  суммарный вес добавленных рёбер должен быть минимальным.

Формат входных данных

В первой строке находится целое число п (1 ≤ п ≤ 100 000). Во второй строке находится целое неотрицательное число т1. Далее в т1 строках находятся описания ребер исходного графа. Каждое ребро задается номерами начала и конца. В следующей строке находится целое неотрицательное число т2. Далее в т2 строках находятся описания ребер, которые можно добавить. Каждое ребро задаётся номерами начала и конца и своим весом — целым числом от –109 до 109, включительно. Известно, что 0 ≤ т1 + т2 ≤ 500 000.

Формат выходных данных

В первую строку выведите «YES» или «N0» в зависимости от того, существует ли решение задачи. Если решение существует, выведите следующие три строки. В первой из них должен быть суммарный вес добавленных рёбер. Во второй – количество добавленных рёбер. В третьей через пробел должны содержаться номера добавленных рёбер. Рёбра нумеруются с единицы в том порядке, в котором они перечислены во входном файле. Каждое добавленное ребро нужно выводить ровно один раз.

Примеры

Задача B. Драйверы

Имя входного файла: входной файл

Имя выходного файла: выходной файл

Ограничение по времени: 10 секунд

Ограничение по памяти: 256 мебибайт

В операционной системе есть N драйверов. Известно, что какая-то пара драйверов (i, j) конфликтует (i≠j). Существует ровно одна такая пара. То, что драйверы конфликтуют, выражается в том, что, если их включить одновременно, система не будет работать. В любом другом случае система работает.

Изначально все драйверы выключены. Нужно определить пару конфликтующих драйверов (т. е. числа i и j). Для этого разрешается провести серию экспериментов. Один эксперимент заключается в том, что мы выбираем любое множество S из N драйверов. И включаем их. Смотрим, будет ли работать система или нет. А потом выключаем всё обратно. Стоимость одного эксперимента равна размеру множества S.

Ваш бюджет равен 105. Т. е. суммарная стоимость всех экспериментов не должна превышать 105.

Решение должно содержаться в функции Solution(N, i, j, data). N — число драйверов, а значения переменных i и j должны содержать ответ (драйверы нумеруются целыми числами от 0 до N — 1).

Для проведения эксперимента можно использовать функцию Check() (эта функция возвращает 1, если система работает, и 0, если не работает). Функция Check() не включает драйверы, помеченные data[i] = 0, и включает драйверы, помеченные data[i] = 0. Соответственно, i лежит в пределах от 0 до N — 1. 2 ≤ N ≤ 105.

Подзадача 1

Дополнительные условия: N ≤ 100 (Решение оценивается в 20 баллов).

Подзадача 2

Дополнительные условия: N ≤ 1 000 (Решение оценивается в 20 баллов)

Подзадача 3

Дополнительные условия: N ≤ 5 000 (Решение оценивается в 20 баллов).

Подзадача 4

Дополнительные условия: N ≤ 20 000 (Решение оценивается в 20 баллов)

Подзадача 5

Дополнительные условия: отсутствуют. (Решение оценивается из 30 баллов)

Тесты даны в порядке возрастания N. Если решение прошло успешно все тесты для N ≤ X, тогда оно получитбаллов.

Задача C. Наследство

Имя входного файла: стандартный ввод

Имя выходного файла: стандартный вывод

Ограничение по времени: 2 секунды

Ограничение по памяти: 256 Мебибайт

В королевстве имеются п городов, соединённых (п— 1) дорогами. При этом по дорогам можно добраться из любого города до любого другого города.

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

Для того чтобы раздел считался справедливым, было решено следующее:

•  принцы получат города, отличающиеся количеством не более, чем в два раза.

•  из любого города одного принца останется возможность добраться до любого другого города того же принца по дорогам, соединяющим города этого принца.

Придворный шут заметил, что такое деление не всегда возможно. Голову ему отрубили, но потом задумались... и постановили: один город можно оставить в совместном управлении и считать его принадлежащим как первому, так и второму принцу.

Формат входных данных

В первой строке записано целое число п — количество городов (2 ≤ п ≤ 100 000). Каждая из следующих (п—1) строк содержит по два целых числа — номера городов, соединённых этой дорогой. Города нумеруются, начиная с единицы.