Сжатие бинарных последовательностей
(Время: 1 сек. Память: 16 Мб Сложность: 19%)
Последовательность из символов «0» и «1» называется бинарной. Они широко применяются в информатике и других науках. Одно из неудобств бинарных последовательностей – их трудно запоминать. Для решения этой проблемы были предложены разные способы их сжатия. Программист Слава использует следующий способ: просматривая последовательность слева направо, он заменяет «1» на «a», «01» на «b», «001» на «c», …, «00000000000000000000000001» на «z». Напишите программу, которая поможет Славе автоматизировать этот способ сжатия.
Входные данные: Входной файл INPUT.TXT содержит бинарную последовательность – строку из символов «0» и «1» длиной не более 255 символов. Гарантируется, что к ней применим указанный способ сжатия.
Выходные данные: В выходной файл OUTPUT.TXT выведите одну строку из английских строчных букв от «a» до «z» – сжатие заданной бинарной последовательности.
Примеры
| № | INPUT.TXT | OUTPUT.TXT |
| 1 | 101 | ab |
| 2 | 101001 | abc |
| 3 | 0000000000000000000000001 | y |
Алфавит
(Время: 1 сек. Память: 16 Мб Сложность: 25%)
Воспитательница Галя работает в детском саду. Кроме детских игр в этом детском саду проходят занятия. Вот уже неделю ребята изучают буквы английского алфавита. Каждое утро воспитательница выстраивает всех своих подопечных в ряд и они играют в игру.
Первый ребенок в ряду громко называет первую букву алфавита – A. Второй должен назвать B, третий – C и так далее. По счастливому стечению обстоятельств всего в группе 26 детей и столько же сколько и букв в английском алфавите.
|
|
|
Если каждый ребенок без ошибки назовет свою букву, то группа отпразднует знание английского алфавита и ребята по этому случаю съедят большой торт. Однако, пока что группе не удается правильно назвать все 26 букв и каждое утро то один, то другой называет свою букву неправильно и игра на этом заканчивается.
Ребята учат буквы подряд и каждый из них знает первые несколько букв алфавита и не может назвать остальные. Поэтому возможность выиграть напрямую зависит от их расстановки. К примеру, если последним в ряду окажется ребенок, знающий английский алфавит только до буквы D, то букву он назвать не сможет и группа не выиграет независимо от того, насколько хорошо выучили алфавит остальные ребята.
Галя считает, что группа в целом уже достаточно хорошо знает алфавит и хочет помочь своим ребятам выиграть. Для этого ей нужно всего лишь расставить их так, чтобы первый ребенок в ряду знал алфавит хотя бы до буквы A, второй хотя бы до буквы B и так далее, последний в ряду должен знать все буквы.
Помогите Гале решить: в каком порядке расставить ребят, чтобы они смогли выиграть или выясните, что это пока невозможно.
|
|
|
Входные данные: Входной файл input.txt содержит строку, состоящую из 26 букв английского алфавита, записанных слитно; i-я из этих букв говорит о том, до какой буквы знает алфавит i-й ребенок.
Выходные данные: В первой строке выходного файла output.txt выведите YES, если воспитательнице удастся выстроить своих детей в ряд так, чтобы они выиграли и NO, если им для этого еще надо поучиться. Если расстановка возможна, во второй строке выведите перестановку из 26 чисел от 1 до 26 через пробел – порядок детей в ряду. Если решений несколько, можно вывести любое.
| № | INPUT.TXT | OUTPUT.TXT |
| 1 | ABCDEFGHIJKLMNOPQRSTUVWXYZ | YES 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
| 2 | BCARTYXYZZYZZYXYXYZZYZZYXV | YES 3 1 2 4 5 26 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 25 24 23 |
| 3 | AAZZZZZZZZZZZZZZZZZZZZZZZZ | NO |
Дата добавления: 2019-01-14; просмотров: 700; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!