Entrada: Uma matriz I de k números inteiros positivos. Os números inteiros não serão maiores que 100 e k ≤ 100 .
Saída: Seu código deve gerar todas as matrizes possíveis O de números inteiros não negativos de comprimento k com a restrição de que 0 ≤ O i ≤ I i . Para passar de uma matriz para a próxima, você pode adicionar ou subtrair 1 a um valor na matriz. Seu código não deve gerar a mesma matriz duas vezes. Se o número de matrizes diferentes a serem produzidas for muito grande, seu código deve continuar produzindo para sempre até que seja eliminado.
Exemplos
Se eu sou uma matriz de k ones, então este é exatamente o problema de iterar sobre todos os códigos Gray de largura de bit k , exceto que o primeiro e o último elemento não precisam ser alcançáveis em uma única etapa.
Se,
I = [2,1]
então, uma ordem possível das matrizes de saída for(0,0),(0,1),(1,1),(1,0),(2,0),(2,1)
- Se,
I = [2,1,3]
então, uma ordem possível das matrizes de saída é(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),...
.
Este é um desafio do código-golfe, a submissão com o código-fonte com o menor comprimento vence. Não deixe que as respostas curtas nos idiomas do golfe o desanimam de postar uma resposta em outros idiomas. Tente encontrar a resposta mais curta em qualquer idioma.
Este também é um desafio de complexidade restrita. Toda nova matriz deve ser impressa com tempo O (k) decorrido desde a matriz anterior impressa (ou o início do programa para a primeira matriz impressa). Isso significa que o tempo de execução por nova matriz de saída (cada um tem o comprimento k ) não deve ser maior que O (k) . Ou seja, deve levar tempo proporcional a k e não, por exemplo, k 2 ou 2 k . Observe que este não é o tempo médio por saída, mas o pior caso para cada matriz gerada.
Você pode assumir que toda a aritmética em números inteiros de 64 bits pode ser executada em tempo constante, assim como a leitura e a saída, assim como a atribuição e a pesquisa e a alteração e alteração de valores nas matrizes.
Uma conseqüência da complexidade restrita é que soluções que somente saem na saída do programa não são aceitáveis.
I_i+1
Pode atingir 0 de?I_i
?)n
ek
é limitada? assumindo que eles vão para o infinito com largura pouco como irRespostas:
Python 3 , 116 bytes
Experimente online!
Obrigado Mnemonic por -1 byte.
Função de gerador. (obrigado Dennis por me lembrar, esqueci que o recurso existe). Se a saída for impressa em stdout, use-a
print(t,flush=1)
por 9 bytes adicionais ou, se Python for chamado com-u
, seráprint(t)
suficiente para +1 bytes.Pára com um erro (
IndexError
). Se você quiser chamar esta função e continuar o programa, precisará capturá-la.fonte
k
etapas, porque a cada etapai
aumenta as etapas1
após e depois e causa um erro.k
i==k
d[i]
not 0<=
pornot-1<
.yield t
vez deprint(t,flush=1)
?Stax , 22 bytes
Execute e depure
Aqui está um grande exemplo para mostrar o comportamento assintótico Pressione Executar.
Descompactado, não jogado e comentado, é assim.
Execute este
fonte
O(k)
bits, então divisãok
vezes pode levarO(k²)
tempo ...JavaScript (Node.js) , 114 bytes
Experimente online! Ungolfed:
fonte
Kotlin ,
181178 bytesObrigado a: Anush apontou que eu não entendi o desafio de economizar 2 bytes. ovs apontou uma economia de 1 byte.
Experimente online!
fonte
while(true)
pode serwhile(1<2)