Задания ЕГЭВариант № EGE_INF_1802
Добавлен 16 декабря 2017 г. в 0:45. Изменён 17 июня 2018 г. в 17:03.
Скачать PDFЗадание
Для реализации интерфейса ассоциативного массива, ключами которого являются строки, обычно используют сжатое префиксное дерево (trie). Каждая дуга префиксного дерева помечена строковой, а каждая вершина — бинарной меткой. Значение ключа можно получить соединением символов, написанных на дугах на пути от корня до соответствующего выделенного узла, имеющего метку 1.
В Таблице 1 содержится информация о дугах некоторого префискного дерева и их метках, а в Таблице 2 хранятся соответствующие метки вершин. На основании представленных данных определите количество ключей, имеющих префикс «КОД».
| Таблица 1 | ||
|---|---|---|
| ID_начало | ID_конец | Метка дуги |
| 0 | 1 | К |
| 1 | 2 | А |
| 1 | 3 | Т |
| 1 | 4 | О |
| 4 | 5 | РА |
| 5 | 6 | БЛЬ |
| 5 | 7 | Л |
| 9 | 8 | ЕК |
| 4 | 9 | Д |
| 8 | 10 | С |
| 12 | 11 | АНИЕ |
| 9 | 12 | ИРОВ |
| 12 | 13 | КА |
| 3 | 14 | ИРОВКА |
| 3 | 15 | ЁЛ |
| 18 | 16 | А |
| 18 | 17 | ИНА |
| 2 | 18 | РТ |
| 18 | 19 | ОН |
| 2 | 20 | ДЕТ |
| Таблица 2 | |
|---|---|
| ID | Метка вершины |
| 0 | 0 |
| 1 | 0 |
| 2 | 0 |
| 3 | 1 |
| 4 | 0 |
| 5 | 0 |
| 6 | 1 |
| 7 | 1 |
| 8 | 1 |
| 9 | 1 |
| 10 | 1 |
| 11 | 1 |
| 12 | 0 |
| 13 | 1 |
| 14 | 1 |
| 15 | 1 |
| 16 | 1 |
| 17 | 1 |
| 18 | 0 |
| 19 | 1 |
| 20 | 1 |
Ответ
5
Подробнее...