Назовем N-значное число, не содержащее ведущих незначащих нулей, числом из Зазеркалья, если это число можно написать на бумаге, изображая цифры так, как их пишут на электронных табло (см. рисунок), а потом поднести к этому изображению зеркало и увидеть в нем то же самое число. При этом все цифры полностью мы должны увидеть именно в зеркале, в неискаженном виде, а число целиком прочитать, как обычно, слева направо. Единственное, что может выглядеть по-другому, — это расстояние между цифрами числа.
Вася выписал на бумаге некоторые цифры одного из N-значных чисел. Позиции этих цифр в числе он также зафиксировал. Помогите ему определить, сколько различных чисел из Зазеркалья он может записать, заполняя всеми допустимыми способами остальные позиции.
В первой строке входных данных записано одно натуральное число N (1 ≤ N ≤ 30). Во второй строке находятся ровно N символов, часть из которых цифры, а часть — символы ‘*’, обозначающие свободные места. Строка заканчивается символом перевода строки.
Выведите количество N-значных чисел из Зазеркалья, которые можно получить, заполняя свободные места цифрами.
Условие этой задачи нужно понять буквально.
А для того чтобы проверить ответ к первому примеру, можно перебрать все варианты на бумаге и подносить к ним зеркало, пока не станет понятно, какие 3 варианта являются подходящими.
Тесты к этой задаче состоят из четырех групп.
Баллы за каждую группу тестов ставятся только при прохождении всех тестов группы.
2 *0
3
4 1*7*
0
В столице одной небольшой страны очень сложная ситуация. Многокилометровые пробки буквально парализовали движение в городе, и власти на многих улицах ввели одностороннее движение, не анализируя, можно ли будет теперь проехать из любого места в городе в любое другое, не нарушая правила. Транспортная система столицы представляет собой N площадей, соединенных M полосами для движения, в том числе круговыми полосами, проходящими по площади. Каждая полоса предназначена для движения только в одну определенную сторону. При этом на магистралях есть полосы, направленные как в одну, так и в другую сторону. По круговой полосе можно двигаться только внутри площади и только против часовой стрелки.
Власти города на каждой полосе разместили видеокамеру, поэтому если Иннокентий едет по встречной полосе (при ее наличии) или, в случае одностороннего движения, в сторону противоположную предписанной знаками, то после поездки против правил по каждой из полос ему придется заплатить штраф в размере одной тысячи тугриков этой страны.
Иннокентий, который торопится купить кафельную плитку со скидкой, решился доехать до магазина в любом случае, даже если для этого придется нарушать правила. Но он хочет выбрать такой маршрут движения, суммарный штраф на котором минимален.
Иннокентий еще не решил, откуда именно и в какой магазин он собирается ехать, поэтому ему необходимо ответить на несколько вопросов вида «Какой минимальный штраф надо заплатить, чтобы добраться из пункта A в пункт B?». Отвечая на потребности жителей столицы, известная поисковая система Индекс разрабатывает соответствующий сервис.
Так как многие из вас рано или поздно будут проходить собеседование на работу в эту фирму, продемонстрируйте, что вы тоже умеете решать эту задачу.
В первой строке входных данных содержатся два числа N и M — количество площадей и полос движения в городе соответственно (1 ≤ N ≤ 5000, 1 ≤ M ≤ 10 000). Далее содержатся описания полос, по которым движение разрешено. Каждая полоса описывается номерами двух площадей, которые она соединяет. Движение разрешено в направлении от первой из указанных площадей ко второй.
В следующей строке содержится одно число K — количество вопросов у Иннокентия (1 ≤ K ≤ 10 000, N·K ≤ 2·107). В следующих строках описываются вопросы, каждый вопрос описывается номерами двух площадей, между которыми требуется найти самый дешевый путь. Путь необходимо проложить от первой из указанных площадей ко второй.
Для каждого вопроса выведите одно число — искомый минимальный размер штрафа в тысячах тугриков. В случае, если пути между выбранной парой площадей не существует, выведите - 1.
Тесты к этой задаче состоят из четырех групп.
Баллы за каждую группу тестов ставятся только при прохождении всех тестов группы.
5 5 2 1 2 4 3 2 4 3 5 4 3 5 1 1 5 2 3
0 2 0
Петя — большой фанат активного отдыха. Поэтому он решил активно отдохнуть от занятий в школе в течение N дней и посетить K праздничных мероприятий, проходящих в M разных городах. Петя начал свой отдых с того, что определил, за сколько дней он может добраться от каждого города до любого другого, а также распечатал и определил расписание всех мероприятий, которые он хотел бы посетить. В первый день Петя находится в первом городе, там же он должен находиться в день N, иначе его выгонят из школы.
Для каждого мероприятия известен день его начала, окончания, а также город, в котором оно проходит. Петя живёт полной жизнью, поэтому он посещает каждое мероприятие только целиком. Также Петя не может находиться на двух разных мероприятиях одновременно, даже если они проходят в одном городе. Однако, если два мероприятия проходят в одном городе, и первое заканчивается в тот же день, когда начинается второе, Петя может посетить оба. Также он может посетить мероприятие, начинающееся в день его приезда в город или заканчивающееся в день его отъезда из города.
Учитель информатики задал Вам задачку на дом: узнать, какое максимальное количество мероприятий может посетить Петя.
В первой строке даны три числа — количество дней активного отдыха N (1 ≤ N ≤ 106), количество городов M (1 ≤ M ≤ 250) и количество мероприятий K (1 ≤ K ≤ 5000).
В следующих M строках записаны по M чисел. j-ое число в i + 1-ой строчке "— целое положительное (за исключением диагональных элементов) количество дней Ai, j, необходимое, чтобы добраться от i-го города до j-го. Ai, j ≤ N. Диагональные элементы равны 0. Значение 1 в этой матрице означает, что Петя приедет в соответствующий город на следующий день после отъезда.
В следующих K строках записаны мероприятия. В каждой строке записаны три целых положительных числа Gi, Si, Fi "— номер города мероприятия, а также дни начала и окончания мероприятия соответственно. 1 ≤ Gi ≤ M, 1 ≤ Si ≤ Fi ≤ N.
Выведите единственное число — максимальное количество мероприятий, которые сможет посетить Петя.
Тесты к этой задаче состоят из четырех групп.
Баллы за каждую группу тестов ставятся только при прохождении всех тестов группы.
14 5 5 0 2 1 2 1 2 0 1 1 2 2 1 0 1 2 1 1 2 0 2 1 1 2 2 0 1 11 12 1 8 10 4 7 8 5 7 8 4 9 10
3
14 5 7 0 1 4 3 2 4 0 3 2 4 3 2 0 1 2 1 1 2 0 3 3 2 2 3 0 4 10 12 5 7 9 3 6 9 4 5 6 1 10 12 1 6 9 3 5 8
2
Недавно на уроке во время контрольной Мария Ивановна перехватила записку Саше от Оли. Мария Ивановна очень хочет знать, что в записке, но, к сожалению, записка зашифрована. Мария Ивановна знает, что её ученики для шифровки заменяют каждую букву исходного сообщения на какую-то другую. Замена происходит таким образом, что одинаковые буквы всегда заменяются одной и той же буквой, а разные — разными.
Мария Ивановна подозревает, что записка — это ответы к контрольному тесту (ведь её длина случайно оказалась равной длине строки с правильными ответами). Однако она знает, что ответы Оли не обязательно полностью правильны. На каждый вопрос возможен один из K вариантов ответа. Естественно, Мария Ивановна знает правильные ответы.
Мария Ивановна решила расшифровать записку таким способом, чтобы максимизировать количество правильных ответов Оли. Однако, она очень занята, поэтому попросила Вас помочь ей в этом пустяковом деле.
В первой строке задана длина каждой из строк N (1 ≤ N ≤ 2 000 000) и K — количество возможных ответов на каждый вопрос (1 ≤ K ≤ 52). Ответы нумеруются в порядке abcde...xyzABCDE...XYZ. То есть, при K = 6 возможные ответы выглядят как abcdef, а при K = 30 "— abcde...xyzABCD.
Во второй строке задана зашифрованная записка — строка, состоящая из строчных и заглавных латинских букв.
В третьей строке заданы правильные ответы — строка той же длины, что и первая, состоящая из строчных и заглавных латинских букв.
В первой строке выведите единственное число — максимально возможное количество правильных ответов у Оли.
Во второй строке выведите расшифровку — строчку длины K, где по порядку для каждой буквы из шифра учеников указано, какому ответу она соответствует.
Если несколько расшифровок дают правильный ответ, выведите любую.
Тесты к этой задаче состоят из четырех групп.
Баллы за каждую группу тестов ставятся только при прохождении всех тестов группы. Тестирование на очередной группе начинается только после полного прохождения предыдущей.
10 2 aaabbbaaab bbbbabbbbb
7 ba
10 2 aaaaaaabbb bbbbaaabbb
6 ab
9 4 dacbdacbd acbdacbda
9 cdba
Как вы помните, у Джонни приключился досадный инцидент со страусом Чаком. Поймав всех разбежавшихся страусов, фермер задумался о том, как бы не повторить подобного беспорядка в будущем.
Джонни принял решение построить новое жильё для птиц. Он поставил N наблюдательных вышек с часовыми и прожекторами и соединил их заборами с колючей проволкой под напряжением, огородив тем самым дворик в форме многогуольника из N вершин, на котором будут жить страусы. Для простоты наблюдения он хочет соединить некоторые пары несоседних вышек стенами с пулемётчиками, разбив тем самым двор на N - 2 треугольных части, образующих загоны для страусов. Естественно, стены должны лежать целиком внутри многоугольника, и каждый загон должен представлять собой невырожденный треугольник, т. е. его площадь должна быть ненулевой.
Сейчас фермеру предстоит выбрать, как именно он будет разбивать двор. Помогите ему проанализировать все возможные варианты проведения стен. Джонни интересуют два вопроса — как водится, попроще и посложнее. Во-первых, он хочет знать, для каких пар вышек существует план разбиения, включающий стену между ними. Во-вторых, его интересует, сколько вообще существует планов разбиения двора.
В первой строке входного файла идёт число N (3 ≤ N ≤ 300) — количество вышек.
В последующих N строках даны описания вышек по порядку их обхода. i-я строка содержит два целых числа xi, yi, по модулю не превосходящих 104 — координаты i-ой вышки.
Гарантируется, что двор представляет собой многоугольник ненулевой площади без самокасаний и самопересечений.
В первой строке выведите K — количество пар вышек, между которым потенциально может быть проведена стена.
Далее выведите K пар номеров вышек по одному в каждой строке. Числа в каждой паре должны быть упорядочены по возрастанию, пары должны идти сначала по возрастанию первых чисел, потом по возрастанию вторых чисел.
Последняя строка должна содержать единственное число — количество способов поделить двор на загоны. Так как оно может быть достаточно большим, выведите остаток от его деления на 230 = 1073741824.
Тесты к этой задаче состоят из четырех групп.
Баллы за каждую группу тестов ставятся только при прохождении всех тестов группы.
5 1 1 3 3 4 0 2 -2 1 0
5 1 3 1 4 2 4 2 5 3 5 5
6 2 2 1 4 0 2 2 0 4 2 3 4
5 1 3 1 4 1 5 2 4 4 6 4