Надёжная укладка (НТО 21/22 :: ТБС)
Легенда
Два студента-программиста решили создать небольшую онлайн-игру. Но, как и любое другое сетевое приложение, игра предполагает передачу игровых данных между сервером и клиентом. Для этого студенты спроектировали пакетный протокол. Чтобы времени хватило на учёбу и придумывание вселенной, ребята поручили его реализацию вам.
Чтобы упростить эту задачу, данные пакета представлены в виде цепочки целых чисел. Каждое число имеет свой интервал допустимых значений, все они прописаны в спецификации. Помимо этого, разработчики предполагают проверку целостности пакета исходя из того, что при передаче есть вероятность искажения одного бита в пакете, и в случае этого искажения пакет должен быть отброшен.
Так как речь идёт об игре в реальном времени, важна скорость передачи пакета, которая зависит в том числе от его размера. Следовательно, он должен быть минимально возможным (т.е. иметь минимальную длину в байтах). Но главное — чтобы работало.
Итак, ваша задача: написать две функции. Первая функция – pack, которая оборачивает данные в пакет согласно спецификации. Данные представлены списком v произвольной длины, а спецификация — двумя списками: в l хранятся нижние границы соответствующих чисел-полей, r – верхние. Все три списка содержат целые числа, длины списков равны. Гарантируется, что числа в данных принадлежат диапазонам, указанным в спецификации.
Вторая функция – unpack, которая должна декодировать пакет. В функцию передаётся пакет и спецификация. Учтите, что при передаче в пакете может быть одиночное искажение бита, которое ваша функция unpack должна определить и в соответствующем случае вернуть пустую цепочку как признак искажения.
Сигнатуры функций будут приведены в поле ввода решения после выбора нужного вам языка. Ваши функции не должны выводить что-либо в стандартные потоки вывода и ошибок, а также использовать статические или глобальные переменные. Мы оставляем за собой право обнулить подобные решения, даже если они пройдут. В ограничение на время выполнения входит время работы вспомогательного кода, но оно крайне незначительно.
Итоговый балл за задачу состоит из суммы результатов выполнения ваших функций на наборе тестов. За корректную передачу данных вы получите 1/3 от балла за отдельный тест, а оставшиеся 2/3 — если размер пакета будет минимально возможным.
Time Limit: 2 секунды
Memory Limit: 256 MB