6 тур - з 09.12 по 15.12.2013

точка входу для відправлення розв'язків http://93.171.173.139/cgi-bin/new-client?contest_id=24

скачати умови задач  шостого туру (*.doc)

1. Задача ROW (20 балів)

Ім’я вхідного файлу: ROW.dat

Ім’я вихідного файлу: ROW.ANs

Максимальний час роботи на одному тесті: 2 с.

Обмеження пам’яті: 64 мбайт

Системного адміністратора зацікавило питання, скількома способами можна перевести курсор всередині деякого текстового рядка з початкової в будь-яку іншу позицію, що знаходиться правіше.

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

· Праворуч. Курсор переміщається на один символ вправо.

· На одне слово вправо. Курсор переміщається на початок наступного слова. Якщо поточне слово останнє в рядку, то курсор переміщається на останній символ рядка.

Вхідний файл

Перший рядок вхідного файлу містить цілі числа S T – номери початкової та кінцевої позицій курсору всередині текстового рядка відповідно. Наступний рядок містить сам текст.

Вихідний файл

Вихідний файл повинен містити єдине число N – кількість різних способів переведення курсору.

Обмеження

Рядок містить не більш ніж 256 символів, 1<=S<=256, 1<=T<=256, S<=T.

Приклад.

ROW.dat

1 7

aaa bbbb

ROW.ANs

5

2. Задача EDITOR (100 балів)

Ім’я вхідного файлу: EDITOR.dat

Ім’я вихідного файлу: EDITOR.ANs

Максимальний час роботи на одному тесті: 5 с.

Обмеження пам’яті: 64 мбайт

Системний адміністратор завжди мінімізує свої зусилля. Зараз його цікавить питання, яка максимальна кількість натискань клавіш йому знадобиться, щоб перевести курсор з початкової в будь-яку іншу позицію всередині деякого тексту.

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

· Вліво. Курсор переміщається на один символ вліво. Якщо курсор стоїть на початку рядка, то він не зрушується.

· Праворуч. Курсор переміщається на один символ вправо. Якщо курсор стоїть в кінці рядка, то він не зрушується.

· Вгору. Курсор переміщається на один рядок вгору. Якщо поточний рядок перший, то курсор не зрушується. Якщо після переміщення курсор виходить за межі рядка, то він встановлюється на його останній символ.

· Вниз. Курсор переміщається на один рядок вниз. Якщо поточний рядок останній, то курсор не зрушується. Якщо після переміщення курсор виходить за межі рядка, то він встановлюється на його останній символ.

· На початок рядка. Переміщення на перший символ поточного рядка.

· В кінець рядка. Переміщення на останній символ поточного рядка.

· На одне слово вліво. Якщо курсор знаходиться всередині слова, то він переміщається на його перший символ. Якщо ж курсор знаходиться на символі пробілу або на першому символі слова, то він переміщається на початок попереднього слова. Якщо поточне слово - перше, то курсор опиниться на першому символі рядка.

· На одне слово вправо. Курсор переміщається на початок наступного слова. Якщо поточне слово останнє в рядку, то курсор переміщається на останній символ рядка.

Будь-яка операція, крім двох останніх, вимагає одного натискання на клавішу. Переміщення на слово вліво і на слово вправо вимагає двох натискань (Ctrl + left, Ctrl + right).

Вхідний файл

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

Вихідний файл

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

Обмеження

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

Кожен рядок містить не більш ніж 256 символів, 1<=R<=1000, 1<=С<=256.

Приклад.

EDITOR.dat

3 10

aaaaaaa aaaa

bbbbb

cc ccc ccccc

EDITOR.ANs

5