Misalkan kita mendefinisikan program sederhana yang mengambil larik array bilangan asli dengan beberapa panjang N dan melakukan hal berikut:
i=0 #start at the first element in the source array
P=[] #make an empty array
while L[i]!=0: #and while the value at the current position is not 0
P.append(L[i]) #add the value at the current position to the end of the output array
i=(i+L[i])%N #move that many spaces forward in the source array, wrapping if needed
return P #return the output array
Setiap program seperti itu akan berjalan selamanya atau pada akhirnya akan berakhir, menghasilkan daftar bilangan bulat positif. Tugas Anda adalah, mengingat daftar P bilangan bulat positif, menghasilkan daftar terpendek, L, dari bilangan asli yang berakhir dan menghasilkan P ketika dicolokkan ke program sebelumnya.
Daftar seperti itu selalu ada, karena orang hanya dapat menambahkan P[i]-1
nol setelah masing-masing P[i]
dalam daftar, lalu satu 0 terakhir, dan itu akan menghasilkan daftar asli. Misalnya, diberikan [5,5]
, satu solusinya [5,0,0,0,0,5,0,0,0,0,0]
. Namun, [5,0,5]
jauh lebih pendek, sehingga solusi otomatis tidak valid untuk program Anda.
[5,6]->[5,6,0,0]
[5,7]->[5,0,0,0,0,7,0,0]
[5,6,7]->[5,6,0,7]
[5,6,8]->[5,0,8,0,0,6,0,0,0]
[1,2,3,4]->[1,2,0,3,0,0,4,0]
[1,2,1,2]->[1,2,0,1,2,0,0]
[1,3,5,7]->[1,3,0,0,5,0,0,0,0,7]
[1,3,5,4]->[1,3,4,0,5,0,0]
Input adalah daftar bilangan bulat positif (dalam beberapa format Anda dapat menentukan) dan output harus dalam format yang sama. Ukuran daftar dan bilangan bulat bisa hingga 2 ^ 16. Ini kode golf, jadi program terpendek dalam byte menang!
Jawaban:
Python 3,
109 102 100 9593 byteSolusi rekursif. Sebut saja seperti
f([1,2,3,4])
. Saksikan lulus semua kasus uji.Kita mulai dengan
k=1
(panjang output) dani=0
(posisi dalam output), dan membuat daftarP
dengank
nol. Kemudian kita iterate sepanjang unsur-unsurx
dariL
, memperbaruiP[i]
keP[i]or x
(sehinggaP[i]
membuat nilainya jika itu nol) dani
untuk(i+P[i])%k
. Setelah itu, kami memeriksa bahwa nilai akhirP[i]
adalah nol, bertambahk
jika tidak, dan kembaliP
.Jika pada titik mana pun dari algoritma
P[i]
sudah nol, itu memasuki satu loop terjadi di sekitar beberapa nilai bukan nolP
, dan berakhir pada nilai bukan nol; lalu kita kambuh.sumber