Управление образования г. Якутска

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

Условие

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

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

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

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

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

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

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

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

Ограничения

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

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

3 10
ababaca baca
abcde
ab abc abcde

5

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

8

Решения и тесты

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

Условие

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

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

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

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

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

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

Ограничения

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

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

no selection

no selection

testsimple

test

Решения и тесты

Задача C. КПК

Условие

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

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

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

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

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

Выходной файл содержит сначала число K₁ -- количество проводов, которые нужно оставить в схеме, затем K₁ пар чисел a_i a_j -- описание проводов. После этого следует число K₂ -- число проводов, которые нужно добавить в схему, затем K₂ пар чисел a_i a_j -- описание проводов. Если решений несколько, выведите любое из них.

Ограничения

1 ≤ N ≤ 1000, 0 ≤ M ≤ 10⁶

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

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₄). Ученые хотят сократить зону поиска и просят вас написать программу, определяющую, на каких участках этого прямоугольника может находиться марсоход.

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

В первой строке входного файла содержатся целые числа x₁ y₁ x₂ y₂ x₃ y₃ x₄ y₄, во второй строке содержится программа марсохода.

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

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

Ограничения

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

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

1 1 2 2 3 3 4 4
ne

..
x.

Решения и тесты

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

Условие

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

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

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

Во входном файле находятся два целых числа: N K, где

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

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

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

Ограничения

0 ≤ N ≤ 1000, 0 ≤ K ≤ 8

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

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.

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

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

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

В выходном файле должно содержаться число 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). Расположение защищающихся армий в первом году может быть произвольным, а расположение в каждом следующем году должно учитывать ограничения на перемещение армий.

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

Ограничения

1 ≤ N ≤ 10, 1 ≤ T ≤ 1000, 0 ≤ A_{i, j} ≤ 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).

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

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

Во входном файле находится целое число N, за которым следует N чисел A₁… A_N -- размеры звеньев.

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

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

Ограничения

1 ≤ N ≤ 100, 1 ≤ A_i ≤ 100

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

1 1

.#.
#.#
.#.

2 3 2

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

3 1 1 2

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

Решения и тесты