Вероятность по дереву решений
Задача по программированию с проверкой онлайн
- Сложность
- Средняя
- Языки
- Python
- JavaScript
- TypeScript
- Java
- Go
- Темы
- Разбор и проверка данных
- Рекурсия и перебор
- Деревья и графы
Дерево решений записано строкой по грамматике дерево ::= (вес [признак дерево дерево]). Вес — вещественное число от 0 до 1, признак — слово из строчных латинских букв, а часть в квадратных скобках необязательна: у листа есть только вес, у остальных узлов есть признак и два поддерева. Между любыми двумя токенами (скобка, вес, признак) стоит хотя бы один пробел или перевод строки, кроме мест сразу после ( и перед ), где пробела может не быть. Лишние пробелы и переводы строк допустимы.
Чтобы найти вероятность того, что животное милое, начните с корня и числа p = 1. В каждом узле умножьте p на вес узла. Если узел — лист, остановитесь: p и есть ответ. Иначе, если у животного есть признак узла, перейдите в первое поддерево, а если нет — во второе.
Даны дерево tree и список животных: каждое животное — список его признаков. Верните вероятность для каждого животного в том же порядке. Погрешность до 1e-6. В дереве не больше 1000 узлов.
Пример: дерево "(0.5 cool\n ( 1.000)\n (0.5 ))" (три строки), животные [["cool"], []] → [0.5, 0.25].
Источник: Coding Competitions Archive, codejam/2009/round_1b/decision_tree · © Google LLC · Apache-2.0 · условие переведено и дополнено