--->
43 задач
<---
Источники
На день рождения Егору подарили волшебный квадрат.
Волшебный квадрат — это таблица 3 × 3, в каждой из ячеек которой находятся числа от 0 до 9. Егор придумал следующую игру с волшебным квадратом: он загадывает число N и пытается так поставить числа в каждую ячейку квадрата, чтобы сумма чисел в каждой строке и каждом столбце была равна в точности N.
Пусть расстановка — это волшебный квадрат, заполненный числами. Тогда расстановки A и B считаются различными, если хотя бы для каких-то строки x и столбца y выполняется неравенство Ax, y ≠ Bx, y, где Ax, y и Bx, y — это числа, находящиеся в строке x и столбце y в расстановках A и B соответственно.
Егор задумался, сколько всего существует различных расстановок таких, что сумма в каждой строке и в каждом столбце была равна в точности N.
Напишите программу, которая поможет ответить на вопрос Егора.
Единственная строка входных данных содержит целое число N (0 ≤ N ≤ 109).
Требуется вывести одно число — искомое количество расстановок.
0
1
В примере из условия существует всего одна допустимая расстановка — это таблица 3 × 3, состоящая из нулей. Очевидно, что сумма элементов в любой строке или столбце в такой расстановке равна 0.
На отдыхе в Теплой Стране Вера познакомилась с симпатичным волейболистом- трактористом Петром. Турист Петр, кстати, собирается после отличного отдыха в Теплой Стране отправиться в путешествие по городам Европы. Как известно, Европа обладает развитой транспортной системой: в Европе есть \(V\) интересующих Петра городов и \(E\) маршрутов ночных поездов. Каждый маршрут соединяет два различных города, время в пути составляет одну ночь. Поезда по маршруту ходят в обоих направлениях.
Основной целью поездки Петра является осмотр местных достопримечательностей. По- скольку Петр — невероятно занятой человек, то он решил, что все путешествие должно занимать не более четырех дней. Петр уже многое повидал, поэтому на осмотр достопримечательностей в каждом городе Петр тратит ровно один день. Он хочет составить наиболее практичный тур: каждый день он будет тратить на осмотр города, а каждую ночь — на переезд ночным поездом между городами. Разумеется, Петр не имеет ни малейшего желания посещать один город несколько раз.
Но на этом прагматичность Петра не заканчивается: Петр, как настоящий турист, хочет посмотреть на самые красивые европейские достопримечательности. Он долго изучал справочники и для каждого города оценил свою ожидаемую радость от его посещения \(p_i\). Теперь он хочет найти маршрут, при котором его радость будет наибольшей. Помогите Петру найти такой маршрут.
В первой строке входных данных заданы два целых числа \(V\) и \(E\) (1 ≤ \(V\); \(E \le 3*10^5\)) — количество городов и маршрутов поездов, соответственно. В следующей строке заданы V целых чисел \(p_i\) (1 ≤ \(p_i\) ≤ \(10^8\)), где \(p_i\) обозначает ожидаемую радость от посещения го- рода с номером \(i\). В следующих \(E\) строках заданы описания маршрутов поездов. Каждое описание состоит из пары различных чисел \(a_i\) и \(b_i\) (1 ≤ \(a_i\); \(b_i\) ≤ V\( \)) — номеров городов, между которыми курсирует этот маршрут поезда. Гарантируется, что между каждой парой городов существует не более одного маршрута поезда.
В первой строке выходных данных выведите число K (1 ≤ K ≤ 4) — количество городов в оптимальном маршруте туриста Петра. В следующей строке выведите номера этих городов в порядке посещения. Города нумеруются начиная с единицы. Если оптимальных маршрутов несколько, выведите любой из них.
Тесты к этой задаче состоят из пяти групп. Баллы за каждую группу ставятся только при прохождении всех тестов группы и всех тестов предыдущих групп.
0. Тесты 1–2. Тесты из условия, оцениваются в ноль баллов.
1. Тесты 3–16. В тестах этой группы \(V\); \(E\) ≤ 100. Эта группа оценивается в 20 баллов
2. Тесты 17–32. В тестах этой группы \(V\); \(E\) ≤ 1 000. Эта группа оценивается в 20 баллов.
3. Тесты 33–53. В тестах этой группы \(V\) ≤ 3 000, \(E\) ≤ 60 000. Эта группа оценивается в 30 баллов.
4. В тестах этой группы дополнительные ограничения отсутствуют. Эта группа оценивается в 30 баллов. Решение будет тестироваться на тестах этой группы offline, т. е. после окончания тура.
5 4 4 2 3 1 5 1 2 2 3 3 4 4 5
4 2 3 4 5
4 3 1 2 3 4 1 2 1 3 1 4
3 4 1 3
Девочка Катя любит разные игры со словами. Недавно она придумала новую игру. Увидев где-либо написанное слово, она пытается придумать предложение, содержащее это слово в себе. Буквы увиденного слова должны идти в предложении по порядку, но не обязательно подряд. Например, увидев слово "LTIBE", она придумывает предложение "LET IT BE". Разумеется, Катя ищет кратчайшее предложение.
Ваша задача помочь Кате, автоматизировав игру.
В первой строке содержится увиденное Катей слово. Слово состоит из заглавных латинских букв. Его длина не менее 1 символа и не более 500. Во второй строке входного файла записано целое число N (1 ≤ N ≤ 500) — количество слов в словарном запасе Кати. Далее в N строках записаны слова. Слова состоят из заглавных латинских букв, содержат не менее 1 и не более 50 букв. Слова в наборе могут совпадать. В искомом предложении слово может использоваться любое количество раз, главное, чтобы оно содержалось в списке.
Выведите искомое предложение. Слова в предложении разделяйте пробелами. Длиной предложения называется количество символов (включая пробелы) использующихся при его записи. Переведите в нижний регистр те символы, которые образуют заданное слово. Если решений несколько, выведите любое. Если решения не существует, выведите в выходной файл символ "*".
LTIBE 5 IT THE LET BEE BE
lEt iT be