Рок-группа роботов
Задача по программированию с проверкой онлайн
- Сложность
- Средняя
- Языки
- Python
- JavaScript
- TypeScript
- Java
- Go
- Темы
- Словари и множества
- Массивы и списки
Вы набираете группу из четырёх роботов: по одному из каждого из четырёх списков кандидатов a, b, c и d (списки одной длины, у каждого робота есть номер, номера в списке могут повторяться, роботы с одинаковым номером считаются разными). Группа подходит, если побитовое исключающее ИЛИ (XOR) четырёх номеров равно k.
Верните, сколькими способами можно выбрать подходящую группу, то есть число четвёрок позиций (i, j, l, m), для которых a[i] ^ b[j] ^ c[l] ^ d[m] = k.
Ограничения: длина каждого списка до 1000, номера и k от 0 до 10^9. Перебор всех четвёрок слишком медленен.
Пример: [0, 0], [2, 0], [0, 0], [0, 1], 3 → 4 (нужны номер 2 из второго списка и номер 1 из четвёртого, а в первом и третьем списках подходит любой из двух нулей).
Источник: Coding Competitions Archive, kickstart/2015/round_e/robot_rock_band · © Google LLC · Apache-2.0 · условие переведено и дополнено