Задания 2-го тура NetOI-2019
(решения принимаются до 0 часов 30 декабря 2019 г.)
Задача SnakeWay Винницкие зоологи исследуют поведение норных змей - очень экзотических для подольских местностей гадин. Они поместили одну особь в террариум с системой подземных ходов и с выходами на поверхность ровно в двух местах - углах террариума. Поверхность террариума разделена на равные квадраты по 1 дециметру, причем террариум имеет размеры 3хN дециметров.Ученые заметили, что змея выползает на поверхность ровно один раз в сутки. При этом змея обползает все клетки на поле, к тому же воспроизводит маршрут, который прошла ранее других (два маршрута считаются различными, если разная последовательность посещения клеток). Зоологи интересуются, сколько дней им надо, чтобы увидеть один и тот же маршрут дважды.
Технические условия Программа SnakeWay читает с устройства стандартного ввода две строки. В первом записано натуральное число N (N <106) - длина террариума по одной из сторон. В следующей строке записано единственную букву в зависимости от расположения выходов в террариуме. Буква D означает, что туннели расположено по диаметрально противоположных концах террариума, буква S означает, что между тоннелями ровно 3 клетки (включая клетки, где находятся тоннели), а буква L означает, что между тоннелями ровно N клеток (опять-таки, учитывая клетки , где находятся тоннели).
Программа выводит на экран единственное число - количество дней по модулю 1000000007, которые должны ожидать зоологи, прежде чем дважды увидеть один и тот же маршрут змеи. Дни первого и второго наблюдений следует учитывать в ответ. Если змея не может проползти, выполнив условие задачи, следует вывести -1 в качестве ответа.
Примеры
|
Ввод |
Вывод |
Комментарий |
|
3 D |
3 |
В змеи два возможных маршрута:
таким образом, змея сначала проползет одним путем, затем другим, а на третий день повторит свой первый путь |
|
1 L |
-1 |
Из условия задачи следует, что туннели находятся в одной и той же точке, а потому змея не может выползти оттуда, проползти все клетки ровно один раз и вернуться туда же |
|
1 S |
2 |
Змея имеет единственный возможный маршрут, а поэтому на второй день он повториться |
Задача SqStr . "Хорошее шифрования - залог выигрыша" - подумал Вася, играя со строкой из N символов. Для того, чтобы удобнее было шифровать строку, он превратил ее в последовательность натуральных чисел от 1 до 255. Очень быстро он придумал прекрасный алгоритм шифрования, который, безусловно, теперь представляет собой государственную тайну, а потому публиковать мы его здесь не будем. Зато попросим принять участие в исследовании свойств алгоритма. Вася заметил, что алгоритм "хорошо" работает на строках, где произведение кодов символов равно квадрату некоторого натурального числа. Такими строками, например, будут строки с кодами (1, 128, 128), (2, 5, 10), (7, 7, 49). В заданной строке из N чисел вам необходимо найти количество непустых подстрок, на которых алгоритм будет работать "хорошо" (то есть подстроки, на которых произведение кодов равно квадрату некоторого натурального числа).
Технические условия. Программа SqStr читает с устройства стандартного ввода в одной строке натуральное число N (N <= 300000) - длину строки, а дальше через пробелы следуют ровно N натуральных чисел, по значению не превышают 255 - коды символов. Программа должна вывести одно целое число - количество подстрок, на которых алгоритм будет работать "хорошо".
|
Ввод |
Вывод |
Комментарий |
|
3 1 128 128 |
3 |
«Хорошим» подстроками будут (128, 128) и (1, 128, 128), (1) |
|
3 7 7 49 |
3 |
"Хорошими" подстроками будут (7, 7), (49), (7, 7, 49) |
|
4 1 2 2 1 |
6 |
"Хорошими" подстроками будут (1) (1), (2, 2), (1, 2, 2), (2, 2, 1), (1, 2, 2, 1) |
Задача Vars2019. Миша имеет два массива одинаковой длины, состоящих из целых чисел и переменных. Миша хочет одного - заменами переменных на целые числа достичь, чтобы массивы были абсолютно одинаковы, то есть чтобы на соответствующих позициях стояли одинаковые числа. Помогите ему определить, возможно ли это вообще.
Технические условия. Программа читает с устройства стандартного ввода число T (1 ≤ T ≤ 10) - количество тестов. Далее следуют ровно T тестов, каждый из которых представлен тремя строками. Первая строка содержит ровно одно число N - длину массивов. В следующих двух строках содержатся по N (N<= 105) элементов массивов. Каждый элемент - или натуральное число, не превышает 1000, или же имя переменной, состоящий не более с 10 строчных латинских букв. Программа выводит на устройство стандартного вывода в единственной строке ровно T букв - ответы на каждый из тестовых примеров. Это или "Y" (YES), или "N" (NO), в зависимости от того, возможно ли приравнять массивы или нет.
|
Ввод |
Вывод |
Комментарий |
|
3 3 3 1 2 3 1 x 4 4 5 x p 1 x 3 x 5 x 3 x y 3 x y 2 z 3 |
YNY |
В первом примере положим х = 2, тогда получим равные массивы. Во втором примере достичь равенства не удастся. В третьем примере положим x = 2, y = 3, z = 3 и получим равные массивы. |
Задача Megacube. Андрей - настоящий фанат шоколада, жить без него не может. Недавно ему подарили огромную квадратную плитку молочного шоколада в прозрачной обертке, которую он решил оставить на самый лучший день своей жизни, а до тех пор только представлять вкус, глядя на него сквозь пленку. И однажды утром, проснувшись, он обнаружил, что за ночь мыши выгрызли некоторые части шоколадки, оставив на их месте полости. Немного расстроившись, Андрей решил сделать записи о состоянии шоколадки. Он внимательно посмотрел на каждый из четырех торцов шоколадки и для каждой строки записал, сколько квадратиков выгрызли мыши от края до первого уцелевшего квадратике (там, где мыши выгрызли шоколадку насквозь, Андрей записывал -1). Это занятие успокоило Андрея, и он смог пойти в школу без лишних мыслей. Однако по возвращению он обнаружил, что мыши не только полностью доели остатки его драгоценной шоколадки, а и частично испортили бумажку с записями. Теперь он хочет понять, выгрызли они что-то важное, или же данные уцелели и соответствуют какой-либо шоколадке. Помогите ему сделать это, пока он окончательно не потерял жажду к жизни!
Технические условия. Программа Megacube читает с устройства стандартного ввода число T (1 ≤ T ≤ 10) - количество тестов. Далее следуют ровно T тестов, каждый из которых представлен пятью строками:
- первая строка содержит N (1 ≤ N ≤ 10000) - размер шоколадки;
- второй строка содержит N чисел Li (-1 ≤ Li ≤ N) - записи, полученные при исследовании левого торца (в порядке от первого до N-й строки)
- третий строка содержит аналогичную информацию для правого торца, в том же порядке;
- четвертый строка содержит аналогичные данные (в порядке от первого до N-го столбика) относительно верхнего торца;
- пятую строчку содержит аналогичные записи, полученные при исследовании нижнего торца шоколадки.
Программа выводит на устройство стандартного вывода в единственной строке ровно T букв - ответы на каждый из тестовых примеров. Это или "Y" (YES), или "N" (NO).
|
Ввод |
Вывод |
Комментарий (для первой шоколадки) |
|||||||||
|
2 3 -1 2 0 -1 0 1 2 2 1 0 0 1 3 -1 0 1 -1 2 1 -1 2 -1 1 0 -1 |
YN |
|
Задача Bracket2019. Данная последовательность круглых скобок. За одну секунду можно поменять местами любые две скобки. За какой минимальный время вы сможете получить правильную последовательность скобок? Скобочный выражение считается правильным, если:
- оно пустое
- если A и B верны, то AB верное
- если A правильное выажение, то и (A) правильное
Технические условия. Программа Bracket2019 читает с устройства стандартного ввода последовательность скобок длиной не более 106 символов и выводит на устройство стандартного вывода искомый время. Если получить правильную последовательность скобок невозможно, программа должна вывести -1.
Примеры.
|
Ввод |
Вивод |
|
((())) )()( (( |
0 1 -1 |
--------------------------------------------------------------------------------------------------------------------------------------------
Задання подготовили Г.Непомнящий, Ю.Пасихов, М.Стречень,