РСОП XXXI 2019
18
D.
DECRYPTING
108
Условие
ЗАДАЧА D. ДЕШИФРИРАНЕ
---
Петър и неговите приятели успели да разгадаят схемата за шифриране на съобщения на противниковата групировка. Всяко съобщение е редица от шифрирани знаци. При шифрирането, всеки знак се заменя с двоичен код, като шифриращите кодове изпълняват следните изисквания:
1. Кодовете на различните знаци са различни.
2. Кодовете може да са с различна дължина, но никой код не съдържа повече от 10 бита.
3. Кодът на нито един знак не е префикс (начало) на код на друг знак.
Шифриращите кодове са оформени в кодова таблица, която съдържа всички знаци, които могат да участват в съобщения и техните кодове. Например, с таблицата: А:01; B:10; С:0010; D:0000; може да се шифрират съобщения, съдържащи знаците {A,B,C,D}. Тази таблица отговаря на изискванията, а таблицата A:01; B:10; C:010; D:0000; не отговаря на изискванията, защото кодът на знака А е префикс на кода на знака C. Напишете програма, която по зададена кодова таблица и двоичен низ, който представлява коректно шифрирано съобщение, проверява дали кодовата таблица отговаря на изискванията и ако е така, декодира съобщението. Ако кодовата таблица не отговаря на изискванията, програмата трябва да изведе съобщение за грешка.
На стандартния вход ще бъдат зададени няколко тестови примера. Всеки тестов пример започва с ред, с броя N на елементите на кодовата таблица. Всеки един от следващите N реда е битов низ, който задава един елемент на кодовата таблица. Първите осем бита на низа са двоичното представяне на номера на знака в ASCII, а останалите K бита –кодът, с който се кодира този знак. На последния ред на примера е зададено коректно шифрирано съобщение – битов низ с дължина L. Тестовите примери завършват с ред, на който е зададена 0. В сила са следните ограничения 1 ≤ N ≤ 30, K ≤ 10, L ≤ 256. В различните тестови примери се използват различни множества от знаци, а кодовете на един и същ знак в различните таблици не са непременно еднакви.
За всеки тестов случай програмата трябва да изведе по един ред на стандартния изход дешифрираното съобщение, ако кодовата таблица отговаря на изискванията, а в противен случай – съобщението Wrong code table!.
Примерен вход:
4
0100000101
0100001010
010000110010
010001000000
0110100100100000
4
0100000101
0100001010
01000011010
011010010000
011010010100000
0
Примерен изход:
ABBACD
Wrong code table!