Настройка
Предположим, вы получили n предохранителей с 1 ≤ n ≤ 5, каждый из которых имеет длину метра, и где каждый предохранитель имеет соответствующую скорость горения N метров в течение D часов.
Предохранитель может быть зажжен на одном или обоих концах, затем погашен на одном или обоих концах, повторно зажжен, повторно погашен и т. Д. Столько раз, сколько необходимо, пока предохранитель не будет полностью израсходован. Вы можете зажечь и погасить предохранители мгновенно, и вы можете наблюдать момент, когда предохранитель полностью сгорел (сгорел).
Предохранитель нельзя разрезать и не зажигать нигде, кроме как на его концах.
Такая настройка обеспечивает бесконечно точную систему синхронизации, измеряя время между любыми двумя событиями освещения / потребления предохранителей. Например, учитывая два предохранителя со скоростью горения 1 метр в час, вы можете измерить ровно 45 минут (3/4 часа) по
- одновременно: зажигание первого предохранителя на обоих концах, зажигание второго предохранителя на одном конце и маркировка начала вашего временного интервала
- загорается второй конец второго предохранителя в тот момент, когда сгорел первый предохранитель (30 минут спустя)
- отмечая конец вашего временного интервала в момент, когда сработал второй предохранитель (15 минут спустя)
Соревнование
Учитывая дробное число часов t и набор из n дробей, представляющих точную скорость записи n предохранителей, напишите программу или функцию, которая выводит / возвращает истинное значение, если t часов можно точно измерить путем систематического сжигания предохранителей, или ложное значение в противном случае.
Вход в программу может быть любым из следующих:
- аргументы командной строки в форме
TN/TD N1/D1 N2/D2 N3/D3 ...
- строка в форме,
TN/TD N1/D1 N2/D2 N3/D3 ...
прочитаннойstdin
или эквивалентной - строка формы,
TN/TD N1/D1 N2/D2 N3/D3 ...
переданная в качестве аргумента функции - массив строк,
["TN/TD", "N1/D1", "N2/D2", "N3/D3", ...]
переданных в качестве аргумента функции
Во всех случаях t = TN
/ TD
, где TN
, TD
∈ [1,10000].
Аналогично, во всех случаях: скорость горения для предохранителя i = N i / D i = N<i>
/ D<i>
, где N<i>
, D<i>
∈ [1,10] ∀ i .
Вы можете предположить, что всегда будет от 1 до 5 предохранителей (включительно), и что все входы действительны и находятся в диапазоне. Вы также можете предположить, что все входные дроби даны в самых низких терминах.
Вы не можете использовать числа с плавающей запятой с дробными компонентами для этой задачи.То есть, если вы используете числа с плавающей запятой в любом месте вашего приложения, они могут принимать только целые значения с нулевым дробным компонентом.
счет
Это испытание для игры в гольф , поэтому победителю присуждается самая короткая соответствующая заявка в байтах.
Пример входов / выходов
input: 29/6 3/2 2/3 3/5 3/7 7/5
output: true
One solution:
- light both ends of fuse 1, mark start of interval
- on fuse 1 consumption: light both ends of fuse 2, light one end of fuse 5
- on fuse 5 consumption: extinguish one end of fuse 2, light both ends of fuse 3,
light both ends of fuse 4
- on fuse 2 consumption: extinguish one end of fuse 3, extinguish both ends of
fuse 4
- on fuse 3 consumption: relight one end of fuse 4
- on consumption of fuse 4: mark end of interval (29/6 hours)
input: 2/1 3/1 5/1 7/1
output: false
input: 5/1 6/1 1/6 9/1 1/9
output: true
One solution:
- light fuse 1 at one end, light fuse 2 at both ends, light fuse 4 at both ends
- on fuse 1 consumption: extinguish one end of fuse 2, mark start of interval
- on fuse 4 consumption: relight one end of fuse 2
- on fuse 2 consumption: mark end of interval (5 hours)
Счастливого слияния! :)
Ответы:
Python 2, 305
Это версия для гольфа. Он практически непригоден для n> 3 , так как временная (и пространственная) сложность подобна 3 n 2 ... на самом деле это может быть слишком мало для времени. В любом случае, функция принимает список строк.
Слегка оптимизированная версия может завершить тесты за пару минут. Это может все еще быть медленным для невозможного случая n = 5 все же.
источник
Python 2, 331
Это немного длиннее, чем версия Feersum, но гораздо быстрее. Все тесты вместе занимают около 3 секунд на моем ноутбуке. Хотя полный поиск для n = 5 занимает около 10 минут. Часть кода похожа на версию feersum, но я специально не копировал какой-либо код.
Использование:
Объяснение:
Лямбда-выражение g выполняет некоторую предварительную обработку ввода, например, преобразовывает строки в дроби, отделяет целевое время от скорости записи и вычисляет время записи (= 1 / скорость записи).
Функция h делит все времена записи x на 3 набора n, b и w (n обозначает non_burning, b обозначает one_end_burning и w обозначает both_ends_burning). Он выполняет итерацию по всем этим схемам (кроме схемы n = x, b = [], w = []), определяет плавкий предохранитель с наименьшей скоростью горения (время сохранения в м) и рекурсивно вызывает h с обновленным временем горения. Я сохраняю все возможные времена, когда кто-то может измерить, используя предохранители. В рекурсивном вызове эти значения также обновляются.
Как только я нахожу значение, оно завершает все вызовы с True.
источник
1
«ы и0
» s, которые мы должны были ввести в один-на-времени на консоли без монитора. Иногда у нас не было1
с.