Тёмные силы под руководством Саурона заполонили Средиземье, и только Арагорн, сын Араторна, наследник Исилдура и истинный правитель Гондора, может найти силы противостоять Тёмному владыке Мордора. Впрочем, ему мы поможем в другой раз, сейчас же давайте оценим, как далеко может зайти Тёмный Властелин.
Карта Средиземья представляет собой клетчатый прямоугольник из N строк по M клеток, каждая из которых может либо полностью принадлежать Саурону, либо полностью не принадлежать. Если в любом квадрате размером 2 × 2 три клетки уже захвачены тёмными силами, то они могут завоевать четвёртую клетку этого квадрата.
Изначально полчищам Саурона подвластно некоторое множество клеток карты Средиземья. Оцените максимальное количество клеток, которое они могут подвести под его контроль.
В первой строке содержатся два целых числа N и M ( 1 ≤ N , M ≤ 1 000 ) "— количество строк и столбцов на карте Средиземья.
Следующие N строк по M символов описывают клетки карты. Символ ‘ . ’ соответствует клетке карты, свободной от власти Саурона, а ‘ # ’ "— клетке, захваченной Сауроном. Строки нумеруются от 1 до N , столбцы "— от 1 до M .
Выведите единственное число "— максимальное количество клеток, которые могут контролировать тёмные силы после всех завоеваний.
2 2 ## #.
4
3 4 #... #... ###.
9
3 5 ...## #.... #.#..
5
Сообщник Миши оставил ему послание со словом, состоящим из первых \(K\) строчных букв латинского алфавита. По опыту предыдущих квестов Миша догадался, что код — это слово минимальной длины, которое не является подстрокой переданного сообщником слова и состоит только из первых \(K\) строчных букв латинского алфавита.
Также Миша решил, что перебирать все такие слова будет слишком долго, поэтому в качестве кода от сейфа он хочет попробовать лексикографически минимальное среди всех подходящих слов. Помогите Мише определить, какое слово ему нужно ввести.
В первой строке содержатся два целых числа: \(N\) — длина переданного сообщником слова (\(1 \leq N \leq 10^6\)) и \(K\) (\(1 \leq K \leq 26\)).
Во второй строке содержится переданное сообщником слово.
Выведите строку, которую Миша хочет попробовать в качестве кода от сейфа
3 2 aab
ba
6 3 aaabbc
ac
Мальчик Вартáн настолько любит языки программирования, что выучил уже целых девять и обзавёлся самоучителем по ещё одному языку! Впрочем, просто учить языки ему уже немного надоело, и он решил придумать свой. Название для языка было придумано всего за пару минут — PJ (аббревиатура от любимых команд Вартана), казалось бы, полдела сделано.
После пяти лет упорной работы Вартан реализовал две команды, работающие с целыми неотрицательными числами:
Изначально исполнитель находится на первой строке, работа программы начинается с выполнения записанной в ней команды. Выполнение программы заканчивается после того, как исполнитель попытается перейти дальше последней строки. Нетрудно догадаться, что на данном языке невозможно написать программу, не завершающуюся за конечное число итераций.
По имеющейся программе на языке PJ определите сумму всех чисел, которые будут выведены в результате её исполнения.
На ввод подаётся корректная программа на языке PJ, состоящая как минимум из одной, но не более чем из 10 5 команд. Количество строк в файле совпадает с количеством команд, каждая команда занимает отдельную строку. Команда, записанная в строке с номером i (при нумерации от единицы), удовлетворяет одному из двух форматов:
Выведите сумму всех чисел, которые будут выведены в процессе выполнения данной программы.
print 1 print 2 jump 2 2
7
print 3 jump 1 1 print 1 print 1 jump 1 2
18
1. Заменить в текущем выражении любой знак ‘+’ на ‘-’
2. Добавить в выражение пару из открывающейся и закрывающейся скобок. Открывающаяся скобка обязательно ставится сразу после знака ‘+’ или ‘-’, а закрывающаяся обязательно ставится сразу после переменной (и, разумеется, после соответствующей ей открывающейся).
Требуется получить выражение, эквивалентное \(⋄_1\) \(x_1\) \(⋄_2\) \(x_2\) \(⋄_3\) ... \(⋄_n\) \(x_n\);
где каждое \(⋄_i\) — это знак ‘+’ или ‘-’.
Выражения f(\(x_1\); \(x_2\); ... ; \(x_n\)) и g(\(x_1\); \(x_2\); ... ; \(x_n\)) называются эквивалентными, если f(\(x_1\); \(x_2\); ... ; \(x_n\)) = g(\(x_1\); \(x_2\); ... ; \(x_n\)) для любых(\(x_1\); \(x_2\); ... ; \(x_n\)), то есть они равны для любых возможных значений используемых переменных. С точки зрения предлагаемой задачи данное определение означает, что после раскрытия всех скобок каждая переменная встречается в обоих выражениях с одним и тем же знаком.
Эмма использует \(A\) единиц магии на выполнение каждой операции первого типа и \(B\) единиц магии на выполнение каждой операции второго типа. Помогите Эмме определить, какое минимальное количество единиц магии ей придётся использовать, чтобы преобразовать исходное выражение в эквивалентное требуемому.
В первой строке входных данных записано единственное целое число \(N\) (1 <= N <= \(10^6\)) — количество переменных в выражениях. Во второй строке записана строка длины \(N\), состоящая только из символов ‘+’ и ‘-’, \(i\)-й символ строки соответствует знаку \(⋄_i\). В третьей строке записаны два целых числа \(A\) и \(B\) (0 <= \(A\); \(B\) <= \(10^9\)), задающие стоимости операций
Выведите одно число — искомое минимальное количество единиц магии, необходимое для получения эквивалентного выражения из исходного
В первом примере Эмме выгодно сначала заменить первый ‘+’ на ‘-’, затратив одну единицу магии, а потом бесплатно поставить скобки. В результате у нее получится
-(\(x_1\) + \(x_2\) + \(x_3\)) = -\(x_1\) -\(x_2\) -\(x_3\)3 --- 1 0
1
7 --+++-- 2 1
6
После получения разноцветного диплома об окончании факультета Высокой Магии и Колдовства Марсианского Галактического Университета, Пафнутий готовится поступать в аспирантуру. На лето он устроился системным администратором в контору по заготовке чистых стёкол и прямых досок, рассчитывая, что работа почти не будет отвлекать его от подготовки к вступительным экзаменам. Но вместо ожидаемого погружения в мир прикладной магии (и сапёра) Пафнутию каждый день приходится сталкиваться со сложными задачами!
В компании работает N сотрудников, каждый из которых использует ровно один персональный компьютер. Машины объединены в сеть с помощью N - 1 соединений, разрешающих парам компьютеров обмениваться данными в любом направлении. Сеть спроектирована таким образом, что между любой парой компьютеров существует ровно один кратчайший (по числу соединений) путь.
К сожалению, сетевые технологии не только помогают в работе и учёбе, но и предоставляют неограниченные возможности для бесцельной траты времени, поэтому сеть бóльшую часть времени находится в выключенном состоянии. Активация происходит лишь на две секунды раз в пять часов, чтобы переслать между сотрудниками накопившиеся сообщения.
Сообщения передаются при помощи интерфейса, который ещё помнит, как весело жужжала старушка БЭСМ-6. Его работа происходит строго по следующим правилам:
Гарантируется, что каждый компьютер в сети является получателем не более чем одного сообщения, причем никогда не является и отправителем, и получателем одновременно. Как этого добивается администрация "— остается загадкой.
Пафнутию нравится решать в уме задачу выбора правильной последовательности пересылок, но правильного ответа может и не существовать. Он просит вас написать программу, которая по описанию конфигурации сети и готовых к отправке сообщений определит, существует ли последовательность пересылок, приводящая к успешному завершению работы интерфейса передачи сообщений. Сама последовательность системного администратора при этом не интересует.
В первой строке входного файла находится единственное целое число N — количество компьютеров. Следующие N - 1 строк содержат пары чисел v i и u i , каждая из которых означает наличие соединения между парой компьютеров с данными номерами. 1 ≤ N ≤ 4 000 , 1 ≤ v i , u i ≤ N , v i ≠ u i . Гарантируется, что между любой парой вершин существует путь, состоящий из данных соединений.
Следующая строка содержит единственное целое число S — количество отправляемых сообщений. Следующие S строк содержат по два целых числа s i и sid i — номер машины, отправляющей сообщение, и уникальный идентификатор сообщения. 1 ≤ S ≤ N , 1 ≤ s i , sid i ≤ N . Гарантируется, что все s i и sid i уникальны.
Далее следует строка, содержащая единственное целое число K — количество компьютеров, принимающих сообщения. Следующие K строк содержат по два целых числа t i и tid i — номер компьютера и идентификатор принимаемого сообщения. 1 ≤ S + K ≤ N , 1 ≤ t i , tid i ≤ N . Гарантируется, что все t i уникальны и что t i ≠ s j для любых i и j . Гарантируется, что для любого i найдётся j такое, что tid i = sid j .
В выходной файл выведите « YES », если решение для данного случая существует, и « NO » в противном случае.
В первом примере требуется передать сообщение от компьютера 3 к компьютеру 1, а также от компьютера 4 к компьютерам 2 и 5. Передача сообщения от 4 к 2 затрёт сообщение, находящееся в ячейке памяти машины 3, поэтому необходимо сначала выполнить передачу от 3 к 1, а затем от 4 к 2. Передачу сообщения от компьютера 4 к компьютеру 5 можно выполнить когда угодно.
Во втором примере передача сообщения от компьютера 4 к компьютеру 1 затрёт содержимое ячеек памяти машин 2 и 3, поэтому успешная пересылка невозможна. Компьютер 5 не может быть использован ни в одной передаче сообщения.
5 1 2 2 3 3 4 4 5 2 3 1 4 2 3 5 2 1 1 2 2
YES
5 1 2 2 3 3 4 2 5 2 2 1 4 2 2 1 2 3 1
NO