Задача 42: Игра
в слова (II открытая Кировская командная олимпиада)
Надеемся, что вам знакома следующая
игра. Выбирается слово и из его букв составляются другие осмысленные
слова, при этом каждая из букв исходного слова может быть
использована не более такого количества раз, которое она в нем
встречается.
Напишите программу, помогающую играть в эту игру.
Входные данные
В первой строке входного файла записано выбранное для игры
слово. В последующих строках задан "словарь" - множество слов,
которые мы считаем осмысленными. Их количество не превышает 1000.
Слово - это последовательность не более чем 255 маленьких латинских
букв. Каждое слово записано в отдельной строке. Заканчивается
словарь словом "ZZZZZZ" (состоящим из заглавных букв), которое мы не
будем считать осмысленным. Слова в словаре, как это ни странно, не
обязательно располагаются в алфавитном порядке.
Выходные данные
В выходной файл необходимо выдать список слов, которые можно
получить из исходного слова. Слова должны быть выданы в том же
порядке, в котором они встречаются в словаре. Каждое слово должно
быть записано в отдельной строке. Список слов должен заканчиваться
все тем же неосмысленным словом "ZZZZZZ".
Примеры входного и выходного файлов
C.IN
soundblaster
sound
sound
blaster
soundblaster
master
last
task
sos
test
bonus
done
ZZZZZZ
C.OUT
sound
sound
blaster
soundblaster
last
sos
bonus
done
ZZZZZZ
C.IN
windowsmustdie
summer
informatics
school
rules
olympiadisstarting
goodbymylovegoodby
exit
ZZZZZZ
C.OUT
ZZZZZZ
Решение:
Мы уже решали подобную задачку (Анаграммы).
Создадим два массива от a до z, в которых будем хранить, сколько раз
встречается та или иная буква в слове. Первый массив отдадим на
первое слово, а второй будем заполнять очередным проверяемым словом.
Первоначально инициализируем первый массив нулями и пройдем по
первому слову от начала до конца. Если в слове встретилась какая-то
буква, то увеличим соответствующей ей элемент на 1.
Затем, заведем цикл repeat - until, условием выхода из которого
будет прочтение строки ZZZZZZ. Если строка не равна ZZZZZZ, то
инициализируем второй массив нулями, а затем также для всех букв
этого слова будем увеличить соответствующие элементы второго
массива. Теперь сравним все элементы от a до z в обоих массивах.
Любой элемент первого массива должен быть не меньше элемента второго
массива (иначе получилось бы, что мы использовали при составлении
слова букву, которой нет в данном слове, или использовали больше
букв, чем есть).
Далее
ð
