Молочные коктейли
Задача по программированию с проверкой онлайн
- Сложность
- Средняя
- Языки
- Python
- JavaScript
- TypeScript
- Java
- Go
- Темы
- Массивы и списки
- Словари и множества
В кофейне n вкусов коктейля, и каждый можно приготовить обычным (0) или с солодом (1). Для каждого вкуса нужно сделать ровно одну партию: либо обычную, либо с солодом. У каждого посетителя есть список любимых видов — пар [вкус, вид], вкусы нумеруются с 1. Посетитель доволен, если приготовлен хотя бы один из его видов. Среди любимых видов одного посетителя не больше одного с солодом.
Нужно угодить всем посетителям, приготовив как можно меньше партий с солодом. Если угодить всем можно, такой набор единственный. Верните список из n чисел: 1, если партия вкуса i с солодом, и 0, если обычная. Если угодить всем нельзя, верните пустой список. При отсутствии посетителей все партии обычные.
Ограничения: 1 ≤ n ≤ 2000, не больше 2000 посетителей, суммарно не больше 3000 пар.
Пример: 5, [[[1, 1]], [[1, 0], [2, 0]], [[5, 0]]] → [1, 0, 0, 0, 0].
Источник: Coding Competitions Archive, codejam/2008/round_1a/milkshakes · © Google LLC · Apache-2.0 · условие переведено и дополнено