Давайте множество целых чисел больше 1 и назовем его X . Мы определим S (i) как множество всех членов X, делимых на i, где i> 1 . Хотел бы выбрать из этих подмножеств группу таких, что
Их союз - это множество X
Ни один элемент X не входит в два множества.
Например, мы можем перегруппироваться {3..11}
как
{3,4,5,6,7,8,9,10,11}
S(3): {3, 6, 9, }
S(4): { 4, 8, }
S(5): { 5, 10, }
S(7): { 7, }
S(11):{ 11}
Некоторые наборы не могут быть выражены таким образом. Например, если мы возьмем {3..12}
, 12
это кратное 3 и 4, предотвращающее взаимное исключение наших наборов.
Некоторые наборы могут быть выражены несколькими способами, например {4..8}
могут быть представлены как
{4,5,6,7,8}
S(4): {4, 8}
S(5): { 5, }
S(6): { 6, }
S(7): { 7, }
но это также может быть представлено как
{4,5,6,7,8}
S(2): {4, 6, 8}
S(5): { 5, }
S(7): { 7, }
задача
Наша цель - написать программу, которая будет принимать набор в качестве входных данных и выводить наименьшее количество подмножеств, которые покрывают его таким образом. Если их нет, вы должны вывести некоторое значение, отличное от положительного целого числа (например 0
).
Это вопрос кода игры в гольф, поэтому ответы будут оцениваться в байтах, причем меньше байтов будет лучше.
тесты
{3..11} -> 5
{4..8} -> 3
{22,24,26,30} -> 1
{5} -> 1
источник
[5..5]
? Можем ли мы получить такие вещи, как[8..4]
?12
является множителем того и другого3
и4
мешает нашим сетам быть взаимоисключающими »: почему? Я не вижу ничего другого в постановке задачи, которая требует включения12
в оба подмножества.[22,24,26,30]
все кратны2
. Вы уверены, что было бы не лучше удалить это и поместить в песочницу?Ответы:
Python 2 , 167 байт
Попробуйте онлайн!
-9 байтов благодаря Zacharý
-4 байта благодаря Mr. Xcoder
-2 байта, используя списки вместо наборов
-5 байтов, используя
a in [...]
вместоany([a == ...])
.-2 байта благодаря Mr. Xcoder
-8 байтов за счет слияния операторов
-5 байтов благодаря Mr. Xcoder
-7 байтов благодаря Mr. Xcoder / Zacharý
+7 байтов, чтобы исправить ошибку
-1 байт благодаря ovs
нота
Это очень медленно для больших максимальных чисел, потому что оно никоим образом не оптимизировано; это не было в течение 2 минут на устройстве мистера Xcoder для
[22, 24, 26, 30]
.источник
Клинго , 51 байт
демонстрация
источник
x(3..12).
(или мне нужно обновить?). Кстати, вы можете предложить хорошее введение в клинго?UNSATISFIABLE
в таком случае. Я в основном использовал руководство Потасско .Mathematica, 105 байт
Попробуйте онлайн
скопируйте и вставьте код с помощью Ctrl + V,
вставьте ввод в конце кода,
нажмите Shift + Enter для запуска
вход
принимает список в качестве входных
выходов 0, если их нет
источник
Check
Haskell, 136 байт
Попробуйте онлайн!
Как это устроено
Потратьте много времени на
{22,24,26,30}
.источник
Желе,
3835343331282524232019 байт-5 байт благодаря Leaky Nun
Попробуйте онлайн!
Я думаю, что третий контрольный пример работает, но он очень медленный.
0
выводится, когда нет решений.Объяснение (возможно, неправильно поняли это объяснение):
источник
ṀḊŒPðḍ@þ@⁹Sḟ1ðÐḟḢL
ṀḊ
самом деле это действительно крутой трюк!Юлия, 91 байт
источник
[Text to display](link to website)