Входные данные: массив I из k натуральных чисел. Целые числа будут не больше 100 и k ≤ 100 .
Вывод: Ваш код должен вывести все возможные массивы O неотрицательных целых чисел длины k с ограничением 0 ≤ O i ≤ I i . Чтобы перейти от одного массива к другому, вы можете добавить или вычесть 1 к одному значению в массиве. Ваш код не должен выводить один и тот же массив дважды. Если количество выводимых массивов очень велико, ваш код должен продолжать выводить до тех пор, пока он не будет уничтожен.
Примеры
Если I - массив из k единиц, то это точно проблема итерации по всем кодам Грея с битовой шириной k , за исключением того, что первый и последний элемент не должны быть достижимы за один шаг.
Если
I = [2,1]
тогда один из возможных порядков выходных массивов(0,0),(0,1),(1,1),(1,0),(2,0),(2,1)
- Если
I = [2,1,3]
тогда возможно одно упорядочение выходных массивов(0,0,0),(0,0,1),(0,0,2),(0,0,3),(0,1,3),(0,1,2),(0,1,1),(0,1,0),(1,1,0),(1,1,1),(1,1,2),(1,1,3),(2,1,3),(2,1,2),(2,1,1),(2,1,0),...
.
Это соревнование по коду для игры в гольф, подача с исходным кодом с самой короткой длиной выигрывает. Не позволяйте коротким ответам на языках игры в гольф отговаривать вас от публикации ответов на других языках. Попробуйте найти самый короткий ответ на любом языке.
Это также проблема с ограниченной сложностью. Каждый новый массив должен быть выведен с O (k) временем, прошедшим с момента предыдущего выведенного массива (или начала программы для первого выведенного массива). Это означает, что время выполнения для каждого нового выходного массива (каждый из которых имеет длину k ) не должно превышать O (k) . То есть это должно занимать время, пропорциональное k, а не, например, k 2 или 2 k . Обратите внимание, что это не среднее время на вывод, а наихудшее время для каждого выводимого массива.
Вы можете предположить, что вся арифметика с 64-разрядными целыми числами может выполняться за постоянное время, а также может считывать и выводить их, а также присваивать, просматривать и изменять значения в массивах.
Одним из следствий ограниченной сложности является то, что решения, которые выводятся только при выходе из программы, неприемлемы.
I_i+1
? Можете ли вы достичь 0 отI_i
?)n
иk
ограничены? предполагая, что они идут в бесконечность с битовой шириной, как идтиОтветы:
Python 3 , 116 байт
Попробуйте онлайн!
Спасибо Mnemonic за -1 байт.
Функция генератора. (спасибо Деннису за напоминание, я забыл, что функция существует). Если выходные данные должны быть напечатаны в stdout, тогда используйте
print(t,flush=1)
для 9 дополнительных байтов, или, если Python вызывается с-u
,print(t)
достаточно для +1 байта.Останавливается с ошибкой (
IndexError
). Если вы хотите вызвать эту функцию и затем продолжить программу, вы должны ее перехватить.источник
k
шагов, потому что на каждом шагеi
увеличивается1
и послеk
шаговi==k
иd[i]
вызывает ошибку.not 0<=
наnot-1<
.yield t
вместоprint(t,flush=1)
?Stax , 22 байта
Запустите и отладьте его
Вот большой пример, демонстрирующий асимптотическое поведение. Нажмите run.
Распакованный, размазанный и прокомментированный, это выглядит так.
Запустите этот
источник
O(k)
битам, поэтомуk
время деления может занятьO(k²)
JavaScript (Node.js) , 114 байт
Попробуйте онлайн! Ungolfed:
источник
Котлин ,
181178 байтСпасибо: Ануш указал, что я неправильно понял задачу, сэкономив 2 байта. ovs указал на 1-байтовую экономию.
Попробуйте онлайн!
источник
while(true)
может бытьwhile(1<2)