Обманчивая война
Задача по программированию с проверкой онлайн
- Сложность
- Средняя
- Языки
- Python
- JavaScript
- TypeScript
- Java
- Go
- Темы
- Массивы и списки
- Поиск и сортировка
У Наоми и Кена по n блоков, все 2n масс различны и лежат в интервале от 0 до 1 (не включая границы). Игра состоит из n раундов: Наоми выбирает свой блок, Кен выбирает свой, блок тяжелее приносит очко, оба блока выбывают.
В «Войне» Наоми называет Кену массу выбранного блока честно. Кен знает свои блоки и играет оптимально: если у него есть блок тяжелее названного, он выставляет самый лёгкий из таких, иначе — самый лёгкий из своих. Наоми выбирает порядок блоков так, чтобы получить как можно больше очков.
В «Обманчивой войне» Наоми заранее знает все массы и может назвать любое число между 0 и 1, не равное массе ни одного блока Кена, при условии, что взвешивание её не выдаст: выставленный Кеном блок должен быть тяжелее названного числа тогда и только тогда, когда он тяжелее настоящего блока Наоми. Кен по-прежнему думает, что играет в «Войну», и действует по той же стратегии на основе названного числа. Наоми выбирает блоки и числа так, чтобы получить максимум очков.
Верните список из двух чисел: очки Наоми в «Обманчивой войне» и очки Наоми в «Войне».
Пример: [0.7, 0.2], [0.8, 0.3] → [1, 0].
Источник: Coding Competitions Archive, codejam/2014/qualification_round/deceitful_war · © Google LLC · Apache-2.0 · условие переведено и дополнено