Начало
Рабочее место участника
| Выбрать соревнование | Задачи | Послать решение | Результаты проверки | Статистика по задачам | Вопросы и ответы | Результаты соревнования | Состояние сервера | Изменить данные | Управление командой | Помощь |
Задачи
774. Dice Password Security
Олимпиадные задачи на английском языке| 04/02/2008 | Зима 2008 дорешивание (3D) |
| 07/02/2008 | Тренировка (задачи Benelux APC 2007) (D) |
Ограничения: время – 2s/4s, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
NCIM Group sponsored problem.
The NCIM Group does a lot of work on IT solutions in defense and security. Good
security usually starts with picking a strong password. Generating a password at random
is generally a good practice. For example, a password like "2R4eZ9Rqup" is a bit harder
to guess than "god", "love", "sex" or "secret".
The problem with passwords consisting of random letters and digits is that they are hard
to remember. Instead of using letters and digits it is also possible to generate passwords
by putting random words together. Words are easier to remember than letters and digits.
Using a dictionary of 7776 (`6^5`) words, a 5-random-word password is about as strong as a
11-random-character password.
`7776^5\ =\ 28430288029929701376\ ≈\ 3*10^19`
`62^11\ =\ 52036560683837093888\ ≈\ 5*10^19`
Some applications hide the password you are typing on the screen by printing dots or
asterisks. This allows someone watching your screen to count the number of characters in
your password. The NCIM Group wants you to find out whether or not this compromises
the strength of your password.
You must write a program that calculates the number of possible passwords that can be
generated given:
- the dictionary of words,
- the amount of words used to generate the password and
- the length of the password.
Input
On the first line an integer `t` `(1\ ≤\ t\ ≤\ 100)`: the number of test cases. Then for each test
case:
One line with three positive integers `m` `(1\ ≤\ m\ ≤\ 7776)`, `n` `(1\ ≤\ n\ ≤\ 5)` and `q`
`(1\ ≤\ q\ ≤\ 20)`: the number of words in the dictionary, the number of words to
generate the password, and the number of queries, respectively.
The dictionary: `m` lines each containing one word `w_i`. Each word consists only of
lowercase letters. The length of each word will be between 3 and 10 inclusive. No
word in the dictionary will be a substring of another word in the dictionary.
`q` lines each containing a positive integer `l_j` `(1\ ≤\ l_j\ ≤\ 50)`, the length observed.
Output
For each testcase:
`q` lines with: the number of possible passwords with length `l_j`. This number will be
smaller than `2^63`.
Sample Input
1 4 2 2 aap noot mies piet 7 8
Sample Output
6 9
