close

Вход

Забыли?

вход по аккаунту

?

1. Префиксная архивация 2. Числа-палиндромы

код для вставкиСкачать
Эстонская олимпиада по информатике
?адания
Региональный тур ??????????
?руппа преуспевших
?? Префиксная архивация
? секунда
?? очков
Префиксная архивация ? это двухшаговый алгоритм для архивации совокупности слов?
?? Сортируем слова в алфавитном порядке?
a1 a2 . . . ana ? b1 b2 . . . bnb нахо?
ai = bi ? ?сли k > 0? преобразуем
?? ? отсортированном списке? для каждой пары идущих подряд слов
k ? что для всех 1
kbk+1 bk+2 . . . bnb ?
дим наибольший такой
второе слово к виду
i
k
выполняется
?ругими словами? в каждом слове? если у него есть префикс? равный префиксу предыдущего
слова? заменяем этот префикс на его длину ?в десятичной системе счисления?? При разархи?
вации мы можем это слово легко восстановить? так как у нас есть предыдущее слово и длина
префикса? который нужно из него взять?
?аписать программу? которая заархивирует с помощью описанного алгоритма заданую совокуп?
ность слов?
?ходные данные? ? первой строке текстового файла
10 000?? и в каждой из следующих N
длиной 1 . . . 30 символов?
?r???s?s дано количество слов N ?1
N
строк дано одно состоящее из маленьких латинских букв слово
?ыходные данные? ? текстовой файл
?r?????? вывести ровно N
строк? заархивированные слова?
в каждой строке по одному слову? При сортировке символы сравнить по их ??????кодам?
Пример?
?r???s?s
?r??????
?
??st
??ss
????
??st
????
?ss
?t
??st
??st? ??ss? ????? ??st? отсортированные в алфавитном порядке ? ????? ??ss? ??st? ??st?
???? и ??ss есть общий префикс ?? длиной ?? у слов ??ss и ??st общий
префикс ??s длиной ? и у слов ??st и ??st общего префикса нет? ?айденные общие префиксы
заменяем их длинами и получаем результат? ????? ?ss? ?t? ??st?
Слова
из чего видим? что у слов
?? Числа?палиндромы
? секунда
?? очков
Целое число называют палиндромом? если оно читается одинаково как слева направо? так и справа
налево? ?апример? число ??? ? палиндром? а ??? ? нет?
?аписать программу? которая для заданного числа находит ближайшие палиндромы?
?ходные данные? ? единственной строке текстового файла
????s?s
дано число
N ?0
N
9 223 372 036 302 733 229??
?ыходные данные? ? первую строку текстового файла
палиндром? не больше
Пример?
N?
?о вторую строку вывести
????s?s
N1
и
??????? вывести число N1 ? максимальный
минимальный палиндром? не меньше N ?
???????
???
?ценивание? ?ывод
N2 ?
???
???
N2
оценивается отдельно? каждое из них да?т ??? от стоимости теста?
?сли программа не смогла найти один из этих палиндромов? вывести вместо него число
?1?
???
Эстонская олимпиада по информатике
?адания
Региональный тур ??????????
?руппа преуспевших
?? Цирк
? секунда
? настольной игре ?Цирк? игральная доска состоит из
?летка номер
1
начальная? и клетка номер
N
N
?? очков
клеток? которые пронумерованы
1 . . . N?
? конечная? ? начале игры фишку игрока устанав?
ливают на начальную клетку? Цель игрока ? попасть в конечную клетку?
?а каждом ходу игрок кидает обычный ??гранный кубик и двигает фишку впер?д на столько
клеток? сколько точек выпало на кубике ?1 . . . 6? ?при выпадении на кубике числа
из клетки
r
в клетку
s фишка двигается
r + s??
?екоторые клетки соединены между собой односторонними туннелями? ?огда фишка после броска
кубика останавливается на клетке? являющейся началом туннеля? она сразу передвигается к концу
туннеля? ?сли фишка останавливается в конце туннеля? ничего не происходит?
?аписать программу? которая находит минимальное возможное количество бросков кубика? кото?
рым можно попасть в конечную клетку? если все броски дадут подходящие результаты?
?ходные данные? ? первой строке текстового файла
стола
N ?1
N
1000?
и количество туннелей
M ?0
ts?s?s дано
2·M
N ??
количество клеток игрового
? каждой из следующих
M
строк дано два разных целых числа? номера входной и выходной клеток одного туннеля? ?звестно?
что ни одна клетка не соединена с более чем одном туннелем? ?ачальная и конечная клетки не
являются началом туннеля?
?ыходные данные? ? первую строку текстового файла
ков кубика
K?
и в каждую из следующих
K
ts???? вывести искомое количество брос?
строк вывести одно целое число? числа? выпавшее на
кубике в порядке бросков кубика? ?а последнем ходу фишка должна остановиться точно на по?
следней клетке? т?к? перепрыгивать е? нельзя? ?звестно? что попасть в конечную клетку возможно?
?сли оптимальных решений несколько? вывести любое из них?
Пример?
ts?s?s
?? ?
? ??
?? ?
ts????
?
?
?
?гру можно закончить за два броска? если
?? на кубике выпадет ?? перейти из клетки ? в клетку ? и оттуда по туннелю в клетку ???
?? на кубике выпадет ?? перейти из клетки ?? в клетку ???
?стественно? одним броском в конечную клетку попасть невозможно?
???
Документ
Категория
Информационные технологии
Просмотров
21
Размер файла
83 Кб
Теги
1/--страниц
Пожаловаться на содержимое документа