Худшее разбиение префиксного дерева
Задача по программированию с проверкой онлайн
- Сложность
- Сложная
- Языки
- Python
- JavaScript
- TypeScript
- Java
- Go
- Темы
- Строки
- Математика
- Деревья и графы
Дан список words из M различных непустых строк из заглавных латинских букв и число серверов servers (1 ≤ servers ≤ M). Строки делят между серверами: каждая строка попадает ровно на один сервер, на каждом сервере оказывается хотя бы одна строка, серверы различимы. Каждый сервер строит префиксное дерево (trie) своих строк: по одному узлу на каждый различный префикс его строк, включая пустой префикс (корень).
Верните список из двух чисел: наибольшее возможное суммарное число узлов на всех серверах и число разбиений, на которых оно достигается, по модулю 1 000 000 007. Ограничения: M ≤ 400, длина строки ≤ 12, servers ≤ 100.
Пример: ["AAA", "AAB", "AB", "B"], 2 → [10, 8].
Источник: Coding Competitions Archive, codejam/2014/round_2/trie_sharding · © Google LLC · Apache-2.0 · условие переведено и дополнено