Задача A. Текстовый редактор ≡

Условие

Начинающий программист Билл написал свою первую программу — текстовый редактор. Теперь его интересует вопрос, сколько нажатий клавиш потребуется пользователю, чтобы перевести курсор в любую позицию внутри текста.

Текст, с которым работает редактор Билла, представляет собой набор строк. Строки состоят из печатных символов (с ASCII-кодами больше 32) и пробелов. Строка никогда не начинается пробелом и не заканчивается им. Слово — это часть строки, не содержащая пробелов и ограниченная слева и справа пробелами или концами строки. Пользователь может перемещать курсор с помощью восьми операций:

• Влево. Курсор перемещается на один символ влево. Если курсор стоит в начале строки, то он не сдвигается.
• Вправо. Курсор перемещается на один символ вправо. Если курсор стоит в конце строки, то он не сдвигается.
• Вверх. Курсор перемещается на одну строку вверх. Если текущая строка первая, то курсор не сдвигается. Если после перемещения курсор выходит за пределы строки, то он устанавливается на ее последний символ.
• Вниз. Курсор перемещается на одну строку вниз. Если текущая строка последняя, то курсор не сдвигается. Если после перемещения курсор выходит за пределы строки, то он устанавливается на ее последний символ.
• В начало строки. Перемещение на первый символ текущей строки.
• В конец строки. Перемещение на последний символ текущей строки.
• На одно слово влево. Если курсор находится внутри слова, то он перемещается на его первый символ. Если же курсор находится на символе пробела или на первом символе слова, то он перемещается на начало предыдущего слова. Если текущее слово — первое, то курсор окажется на первом символе строки.
• На одно слово вправо. Курсор перемещается на начало следующего слова. Если текущее слово последнее в строке, то курсор перемещается на последний символ строки.

Любая операция, кроме двух последних, требует одного нажатия на клавишу. Перемещение на слово влево и на слово вправо требует двух нажатий (Ctrl+left, Ctrl+right).

Формат входного файла

Формат выходного файла

Ограничения

Примеры тестов

3 10
ababaca baca
abcde
ab abc abcde

5

1 1
begin write(a+b); end.

8

Задача B. Важнейшая часть ≡

Условие

Компания X желает разработать программу для автоматического поиска интересной информации на веб-страницах. В частности, было замечено, что авторы веб-сайтов любят выделять важную информацию при помощи курсива, жирного шрифта, подчёркивания и т.д. Директор компании высказал предположение, что самая важная информация будет выделена сильнее всего. Поэтому вам поручено написать программу, которая в данном тексте найдёт участок с наибольшим количеством выделений.

Исходными данными для программы будет строка символов, содержащая пары тегов <i> ... </i>, <u> ... </u>, <b> ... </b>, ограничивающие выделенные различным образом подстроки. Теги могут повторяться и вкладываться друг в друга, например This <b>is <i>a <u>sample of <b>very</b></u> important</i> text</b>. Ваша программа должна найти подстроку, вложенную в наибольшее количество тегов. Если таких подстрок несколько, следует вывести самую левую из них. В приведённом примере ответом будет подстрока very.

Формат входного файла

Формат выходного файла

Ограничения

Примеры тестов

no selection

no selection

<b>test</b><b>simple</b>

test

Задача C. КПК ≡

Условие

Хакер Вася решил собрать карманный персональный компьютер (КПК). Согласно найденной им в Интернет инструкции компьютер собран правильно тогда, когда ток из каждой микросхемы может пройти в каждую и притом единственным путем.

Вася собрал компьютер, но сомневается в правильности сборки. Напишите программу, которая по данному Васей описанию схемы определит, какие провода нужно удалить, какие оставить и какие придется добавить, чтобы компьютер был собран правильно. Так как Васе не хочется выполнять много работы, он просит вас удалять и добавлять провода таким образом, чтобы суммарное число добавленных и удаленных проводов было минимально.

Формат входного файла

Формат выходного файла

Ограничения

Примеры тестов

3 1
2 3

1
2 3
1
1 2

Задача D. Марсоход ≡

Условие

В далеком будущем российские ученые собрали и отправили аппарат для исследования поверхности Марса — "Марсоход-1". Поверхность кратера, в который высадился марсоход, разбита на участки размером 1 x 1 метр каждый. Программа движения марсохода состоит из последовательности команд:

• w — передвинуться на 1 метр на запад,
• e — передвинуться на 1 метр на восток,
• s — передвинуться на 1 метр на юг,
• n — передвинуться на 1 метр на север.

Координаты юго-западного угла кратера — (0, 0). Оси координат направлены с запада на восток и с юга на север.

Известно, что марсоход высадился где-то в прямоугольнике с координатами (x₁, y₁) − (x₂, y₂). К сожалению связь с марсоходом была потеряна по неизвестным причинам, но он успел передать, что полностью выполнил программу движения. Удалось также определить, что последний сигнал был послан из прямоугольника с координатами (x₃, y₃) − (x₄, y₄). Ученые хотят сократить зону поиска и просят вас написать программу, определяющую, на каких участках этого прямоугольника может находиться марсоход.

Формат входного файла

Формат выходного файла

Ограничения

Примеры тестов

1 1 2 2 3 3 4 4
ne

..
x.

Задача E. Красивые степени ≡

Условие

Математик Николай Николаевич очень любит красивые числа. Причем красивым он считает такое число, запись которого начинается с единицы, далее следуют несколько нулей, и заканчивается опять единицей. Его коллега Юрий Александрович считает, что если такое красивое число возвести в некоторую степень, то оно станет еще лучше. Николай Николаевич сомневается, но хочет проверить это. Вдруг получившиеся числа понравятся ему больше!

Так как вручную возводить в степень тяжело, а в программировании он разбирается не так хорошо, как в математике, вам придется ему помочь.

Формат входного файла

• N — количество нулей в записи числа,
• K — степень, в которую нужно возводить число.

Формат выходного файла

Ограничения

Примеры тестов

1 1

101

1 0

1

0 8

214358881

Задача F. Круговая оборона ≡

Условие

У государства Централии есть четыре агрессивных соседа: Верхия, Низия, Правия и Левия. Правители соседних государств постоянно сосредотачивают на границе с Централией свои армии, ожидая удобного случая для вторжения. Удобным агрессоры считают случай, когда количество армий Централии, охраняющих границу с данным государством, будет меньше, чем количество армий, сосредоточенных на границе агрессором.

Поскольку содержание армий — дорогостоящее занятие, Централия может постоянно поддерживать только N армий. К счастью, по той же причине её соседи, чья экономика менее стабильна, чем в Централии, могут в i-й год подготовить для завоевания A_i,k армий, где k = 0… 3 — номер соседа.

В Централии проживает могущественный колдун-экономист, который сумел предсказать количество враждебных армий на T лет вперёд. Вам поручена роль главнокомандующего армиями Централии с задачей распределения армий по границам таким образом, чтобы удобный для вторжения случай предоставился как можно позже. Задача осложняется тем, что за один год любая армия Централии может переместиться с той границы, которую она занимала в прошлом году, только на соседнюю границу, т.е. с k-й границы либо на границу (k + 1)mod 4, либо на границу (k + 3)mod 4.

Формат входного файла

Формат выходного файла

В выходном файле должно содержаться число Q — максимальное количество лет, в течение которого можно избежать вторжения (0 ≤ Q ≤ T), за которым следуют Q четвёрок чисел B_i,0 B_i,1 B_i,2 B_i,3 — количество армий, которые следует в i-м году расположить на каждой из границ (B_i,0 + B_i,1 + B_i,2 + B_i,3 = N). Расположение защищающихся армий в первом году может быть произвольным, а расположение в каждом следующем году должно учитывать ограничения на перемещение армий.

Если существует несколько оптимальных решений, вывести любое из них.

Ограничения

Примеры тестов

4 2
0 4 0 0
2 1 1 0

2
0 4 0 0
2 1 1 0

4 2
0 4 0 0
2 0 1 1

1
0 4 0 0

Задача G. Гирлянда ≡

Условие

Ваша программа должна вывести в выходной файл изображение гирлянды. Гирлянда состоит из N звеньев, каждое из которых имеет вид ромба, состоящего из символов '#' (ASCII 35) для нечётных звеньев, либо '*' (ASCII 42) — для чётных звеньев. Размер i-го звена задаётся целым числом A_i. Каждая сторона ромба размером A_i состоит из A_i + 1 символа.

Гирлянда должна быть изображена на фоне прямоугольника, заполненного символами '.' (ASCII 46).

Каждое звено, начиная со второго, расположено вертикально под предыдущим и "сцеплено" с ним, как изображено в примере.

Формат входного файла

Формат выходного файла

Ограничения

Примеры тестов

1 1

.#.
#.#
.#.

2 3 2

...#...
..#.#..
.#...#.
#.....#
.#...#.
..#*#..
..*#*..
.*...*.
..*.*..
...*...

3 1 1 2

..#..
.#*#.
.*#*.
.#*#.
#...#
.#.#.
..#..