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

Автор:И. Туфанов
Входной файл: input.txt   Ограничение времени:2 сек
Выходной файл: output.txt   Ограничение памяти:8 Мб

Условие

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

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

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

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

Первая строка входного файла содержит целые числа R C — номер текущей строки и номер символа в текущей строке соответственно. Все остальные строки содержат текст, загруженный в редактор.

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

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

Ограничения

Размер текста во входном файле не превосходит 2000 байт. Входной файл не содержит пустых строк.

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

Входной файл (input.txt) Выходной файл (output.txt)
1
3 10
ababaca baca
abcde
ab abc abcde
5
2
1 1
begin write(a+b); end.
8

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

Автор:А. Кленин
Входной файл: input.txt   Ограничение времени:2 сек
Выходной файл: output.txt   Ограничение памяти:64 Мб

Условие

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

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

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

Во входном файле находится исходная строка текста.

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

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

Ограничения

Длина исходной строки не превосходит 10000 символов. Открывающие и закрывающие теги образуют правильную скобочную последовательность (каждому открывающему тегу соответствует парный закрывающий, и наоборот). Например, последовательность <i>a<u>b</i></u> не может встретиться во входном файле. Между открывающим и закрывающим тегом есть по крайней мере один символ.

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

Входной файл (input.txt) Выходной файл (output.txt)
1
no selection
no selection
2
&amp;lt;b&gt;test&amp;lt;/b&gt;&amp;lt;b&gt;simple&amp;lt;/b&gt;
test

Задача C. КПК

Автор:И. Олейников, Т. Чистяков
Входной файл: input.txt   Ограничение времени:2 сек
Выходной файл: output.txt   Ограничение памяти:8 Мб

Условие

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

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

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

Входной файл содержит числа N и M — соответственно число микросхем и проводов в КПК, за которыми следуют M пар чисел ai aj, означающие, что i-ая и j-ая микросхемы соединены проводом. Ток по проводу может течь в любом направлении.

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

Выходной файл содержит сначала число K1 — количество проводов, которые нужно оставить в схеме, затем K1 пар чисел ai aj — описание проводов. После этого следует число K2 — число проводов, которые нужно добавить в схему, затем K2 пар чисел ai aj — описание проводов. Если решений несколько, выведите любое из них.

Ограничения

1 ≤ N ≤ 1000, 0 ≤ M ≤ 106

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

Входной файл (input.txt) Выходной файл (output.txt)
1
3 1
2 3
1
2 3
1
1 2

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

Автор:И. Олейников, А. Кленин
Входной файл: input.txt   Ограничение времени:2 сек
Выходной файл: output.txt   Ограничение памяти:3 Мб

Условие

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

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

Известно, что марсоход высадился где-то в прямоугольнике с координатами (x1, y1) − (x2, y2). К сожалению связь с марсоходом была потеряна по неизвестным причинам, но он успел передать, что полностью выполнил программу движения. Удалось также определить, что последний сигнал был послан из прямоугольника с координатами (x3, y3) − (x4, y4). Ученые хотят сократить зону поиска и просят вас написать программу, определяющую, на каких участках этого прямоугольника может находиться марсоход.

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

В первой строке входного файла содержатся целые числа x1 y1 x2 y2 x3 y3 x4 y4, во второй строке содержится программа марсохода.

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

Выходной файл должен содержать abs(y4 − y3) + 1 строк по abs(x4 − x3) + 1 символов в каждой — изображение зоны поиска, на котором участки, где может находиться марсоход, отмечены символом 'x' (ASCII 120), а остальные — символом '.' (ASCII 46).

Ограничения

0 ≤ xi, yi ≤ 1000, количество команд в программе не превышает 30000.

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

Входной файл (input.txt) Выходной файл (output.txt)
1
1 1 2 2 3 3 4 4
ne
..
x.

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

Автор:И. Лудов
Входной файл: input.txt   Ограничение времени:1 сек
Выходной файл: output.txt   Ограничение памяти:2 Мб

Условие

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

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

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

Во входном файле находятся два целых числа: N K, где Таким образом, если входной файл содержит 3 5, это значит, что нужно число 10001 возвести в пятую степень.

Обратите внимание, что если указано 0 нулей, подразумевается число 11, а не 1.

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

В выходном файле должно содержаться заданное число, возведенное в заданную степень.

Ограничения

0 ≤ N ≤ 1000, 0 ≤ K ≤ 8

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

Входной файл (input.txt) Выходной файл (output.txt)
1
1 1
101
2
1 0
1
3
0 8
214358881

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

Автор:А. Кленин, Т. Чистяков
Входной файл: input.txt   Ограничение времени:3 сек
Выходной файл: output.txt   Ограничение памяти:64 Мб

Условие

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

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

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

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

Во входном файле находятся числа N T, за которыми следует T четвёрок чисел Ai,0 Ai,1 Ai,2 Ai,3 — количество армий, которые будут выставлены в i-м году каждым из соседних государств.

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

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

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

Ограничения

1 ≤ N ≤ 10, 1 ≤ T ≤ 1000, 0 ≤ Ai, j ≤ N

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

Входной файл (input.txt) Выходной файл (output.txt)
1
4 2
0 4 0 0
2 1 1 0
2
0 4 0 0
2 1 1 0
2
4 2
0 4 0 0
2 0 1 1
1
0 4 0 0

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

Автор:А. Кленин
Входной файл: input.txt   Ограничение времени:1 сек
Выходной файл: output.txt   Ограничение памяти:256 Мб

Условие

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

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

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

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

Во входном файле находится целое число N, за которым следует N чисел A1 AN — размеры звеньев.

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

Выходной файл должен содержать изображение гирлянды.

Ограничения

1 ≤ N ≤ 100, 1 ≤ Ai ≤ 100

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

Входной файл (input.txt) Выходной файл (output.txt)
1
1 1
.#.
#.#
.#.
2
2 3 2
...#...
..#.#..
.#...#.
#.....#
.#...#.
..#*#..
..*#*..
.*...*.
..*.*..
...*...
3
3 1 1 2
..#..
.#*#.
.*#*.
.#*#.
#...#
.#.#.
..#..

0.096s 0.003s 19