Осень 2243-го года. Государства в прошлом, главным территориальным образованием является автономия. В результате терраформирования территория бывшей Евразии теперь представляет собой прямоугольник, он разбит на \(w \times h\) квадратных автономий, которые организованы в виде сетки из \(w\) автономий по ширине и \(h\) по высоте. Некоторые автономии входят в содружество Крипто, они представляют собой криптоанархистские технократические общества и не признают бюрократии. Остальные автономии входят в конфедерацию Бюрро, бюрократия в них доведена до высшего совершенства.
Для перемещения между автономиями необходим загранпаспорт. При въезде в автономию содружества Крипто предъявлять документы не нужно, но при въезде в автономию конфедерации Бюрро пограничная служба проверяет документ, заполняет специальные формы и проставляет в загранпаспорт путешественника штамп своей автономии. Один штамп занимает одну страницу паспорта, разные штампы ставятся на разные страницы.
Опытный путешественник по имени Вениамин хочет получить загранпаспорт нового образца. Чтобы это сделать досрочно, ему нужно заполнить все страницы своего старого паспорта штампами пограничных служб. На данный момент у него осталось \(n\) пустых страниц, соответственно ему нужно ровно \(n\) раз въехать в автономию Бюрро. Он хочет сделать это как можно быстрее.
Вениамин путешествует таким образом, что за один день он переезжает из автономии, в которой он находится, в автономию, имеющую с ней общую сторону. Помогите Вениамину спланировать свое путешествие так, чтобы заполнить все оставшиеся страницы загранпаспорта и при этом сделать как можно меньше переездов между автономиями. Вениамин начинает свое путешествие в родной автономии, которая принадлежит содружеству Крипто, а закончить путешествие может в любой автономии.
В первой строке входного файла содержатся три целых числа: \(w\), \(h\) и \(n\) (\(1 \le w, h \le 500\), \(1 \le n \le 1\,000\)).
В каждой из следующих \(h\) строк содержится по \(w\) символов, они задают карту Евразии. Символ «Arlaquo обозначает автономию содружества Крипто, а «T» - автономию конфедерации Бюрро. Автономия, в которой Вениамин начинает свое путешествие, обозначена символом «V».
Карта дана с севера на юг по строкам и с запада на восток по столбцам, таким образом, первый символ второй строки входного файла описывает самую северо-западную автономию.
Гарантируется, что в Евразии есть хотя бы одна автономия Бюрро.
В выходной файл выведите одну строку из символов «N», «E», «S», «W» - план путешествия Вениамина. Эти символы означают, что Вениамину следует поехать на север, восток, юг или запад, соответственно. Число перемещений в плане необходимо минимизировать, в процессе путешествия Вениамин должен ровно \(n\) раз въехать в автономию Бюрро. Если возможных оптимальных планов путешествия несколько, можно вывести любой.
5 3 6 AAATA VAATA AAAAT
EEENSNSN
3 1 2 TVT
WEW
В лаборатории биоинформатики ученые проводят эксперименты по распространению искусственно созданных вирусов. Для эксперимента используется специальная лабораторная установка, представляющая собой таблицу из \(n \times m\) ячеек. В каждую ячейку помещается живая клетка. Ученые заражают вирусом некоторые клетки, всего исходно заражается не более 8 клеток.
Каждую секунду среди незараженных клеток, имеющих зараженную клетку в соседней по стороне ячейке, ровно одна клетка заражается вирусом.
Ученые заинтересовались, какие конфигурации зараженных клеток могут получиться через \(t\) секунд. Для начала они хотят посчитать число таких конфигураций. Помогите им это сделать.
В первой строке входного файла находятся целые числа \(n\), \(m\) и \(t\) (\(1 \le n, m \le 100\), \(1 \le t \le 6\)) - размеры таблицы и количество секунд.
Каждая из следующих \(n\) строк содержит \(m\) символов. Символ <<.>> означает, что в изначальной конфигурации клетка не заражена, а символ <<*>> - что заражена. Количество <<*>> в таблице не превышает 8.
Гарантируется, что незараженных клеток в исходной конфигурации не меньше \(t\).
Выведите количество различных возможных конфигураций таблицы после \(t\) секунд.
2 2 1 *. ..
2
2 2 2 *. ..
3
2 2 3 *. ..
1
В секретной лаборатории профессора Хаоса проходит эксперимент по выращиванию особо опасных бактерий. В начале первого дня эксперимента у Хаоса имеется \(a\) особо опасных бактерий.
Каждый день эксперимента устроен следующим образом. Рано утром профессор достает из контейнера все свои бактерии и помещает их в инкубатор, где бактерии начинают делиться. Вместо каждой бактерии образуется \(b\) новых бактерий.
После извлечения бактерий из инкубатора \(c\) из них используются для проведения различных опытов и затем уничтожаются. Если после извлечения из инкубатора имеется менее c бактерий, для проведения опытов используются все имеющиеся бактерии, и эксперимент заканчивается.
Оставшиеся бактерии в конце дня необходимо поместить в контейнер и продолжить использовать в эксперименте. Однако в контейнер можно поместить не более \(d\) бактерий, поэтому если число оставшихся бактерий больше \(d\), то в контейнер помещаются \(d\) бактерий, а остальные уничтожаются.
Теперь профессор Хаос хочет выяснить, сколько особо опасных бактерий будет у него в контейнере после \(k\)-го дня эксперимента. Помогите ему найти ответ на этот вопрос.
В единственной строке входного файла содержится пять целых чисел \(a\), \(b\), \(c\), \(d\) и \(k\) (\(1 \le a, b \le 1000, 0 \le c \le 1000, 1 \le d \le 1000, a \le d, 1 \le k \le 10^{18}\)).
Выведите одно число — количество бактерий у Хаоса к концу \(k\)-го дня. Если эксперимент завершится в \(k\)-й день или ранее, выведите число 0.
1 3 1 5 2
5
1 2 0 4 3
4
1 2 3 5 2
0
Саша очень любит играть в игры на своем планшете. Недавно он скачал новую игру, которая называется «Золотые монеты».
Игра проходит на поле, имеющем вид сетки с тремя горизонтальными и четырьмя вертикальными рядами. Это поле представляет собой город: линии сетки являются дорогами, а узлы сетки — перекрестками. По дорогам можно перемещаться в обоих направлениях. В начале игры на каждой дороге расположено несколько золотых монет.
Пример игрового поля приведен на рисунке, перекрестки обозначены черными точками, дороги — отрезками, а число на дороге задает начальное количество золотых монет на ней.
Персонажем игры является бородатый электромонтер Томас. Сначала игрок может поместить Томаса на любой перекресток. Затем каждый ход игрок перемещает Томаса с перекрестка, на котором он находится, на соседний перекресток по одной из дорог, на которой еще лежит хотя бы одна монета.
Проходя по дороге, Томас забирает округленную вверх половину лежащих на ней монет. Таким образом, если на дороге лежит \(x\) монет, то, пройдя по этой дороге, Томас заберет [\(x/2\)] монет, а на дороге останется ⌊\(x/2\)⌋ монет. По дорогам, на которых монет уже нет, перемещать Томаса не разрешается.
Когда Томас оказывается в ситуации, что на всех соседних дорогах не осталось ни одной монеты, игра заканчивается. Очки игрока равны числу монет, которые собрал Томас. Помогите Саше понять, какое максимальное количество монет он сможет собрать.
Входной файл состоит из пяти строк. Первая, третья и пятая строки содержат по три целых числа и описывают соответствующие горизонтальные улицы. Вторая и четвертая строки содержат по четыре целых числа и описывают соответствующие вертикальные улицы. Все числа неотрицательные и не превосходят \(10^9\) .
В единственной строке выходного файла выведите число \(s\) — максимальное количество монет, которые удастся собрать.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
150
1 1 1 0 0 0 0 1 1 1 0 0 0 1 1 1 1
7
Петя работает в наукограде Заколково. Он занимается разработкой нового микропроцессора Чебур. Поскольку ведущий архитектор микропроцессора очень не любит числа с плавающей точкой, вещественные числа в микропроцессоре Чебур хранятся в формате с фиксированной точкой.
Внутренние регистры процессора хранят вещественные числа в виде двоичной дроби ровно с n двоичными знаками после точки. Число знаков до точки не ограничено. В таком формате представимы числа, равные \(p/2^n\) для некоторого целого \(p\). Число \(x\), полученное в результате выполнения арифметических операций над вещественными числами, при сохранении в регистр процессора заменяется на ближайшее представимое число, а если x находится ровно посередине между двумя представимыми числами, то на большее из них.
Для хранения чисел в памяти используется формат, при котором вещественное число
представляется в виде двоичной дроби ровно с \(k\) двоичными знаками после точки (\(k \le n\), число
знаков до точки, так же как и у регистров, не ограничено).
В таком формате представимы в точности
числа, равные
\(p/2^{k}\) для некоторого целого \(p\). При загрузке числа из памяти в регистр процессора
число дополняется нулями до n двоичных знаков после точки. При сохранении числа y в память из
регистра оно заменяется на ближайшее представимое число, а если y находится ровно посередине
между двумя представимыми числами, то на большее их них.
Например, пусть \(n = 10\), \(k = 5\). Число 1 хранится в памяти в виде \(1.00000_2\), число 3 хранится в памяти как \(11.00000_2\). При загрузке в регистры числа дополняются нулями до \(1.0000000000_2\) и \(11.0000000000_2\), соответственно. Пусть было выполнено деление 1 на 3. Если результат деления \(1/3\) записать в двоичной системе, получится \(0.(01)_2\) — здесь, как и в случае десятичных дробей, часть в скобках означает период бесконечной двоичной дроби. При сохранении в регистре процессора эта дробь будет приближена значением \(0.0101010101_2\). Умножим теперь это число на 3. Получится число \(0.1111111111_2\), в таком же виде оно хранится в регистре процессора. При сохранении в память оно приближается числом \(1.00000_2\), как ближайшей двоичной дробью с 5 знаками после точки.
Петя заметил, что если загрузить в регистры единицу и целое число \(v\), поделить 1 на v, затем умножить результат деления на v и сохранить результат умножения в память, то итоговое сохраненное значение не всегда равно 1. Например, если \(v = 40\), то после деления в регистре оказывается значение \(0.0000011010_2\), после умножения на \(v\) значение \(1.0000010000_2\), после сохранения в память оно преобразуется в \(1.00001_2\). Петя называет такие числа неудачными.
Петю заинтересовал вопрос, какие целые числа от 1 до \(r\) являются неудачными. Помогите ему выяснить это
Первая строка входного файла содержит три целых числа \(n\), \(k\) и \(r\) (\(1 ≤\le k \le n \le 100, 1 \le r \le 1000\)).
В первой строке выходного файла выведите число \(t\) — количество неудачных чисел, лежащих в диапазоне от 1 до \(r\). Во второй строке выходного файла через пробел выведите в возрастающем порядке все неудачные числа, лежащие в диапазоне от 1 до \(r\).
10 5 60
7 40 50 52 53 55 58 59