Input: Array I dari k bilangan bulat positif. Bilangan bulat tidak akan lebih besar dari 100 dan k ≤ 100 .
Output: Kode Anda harus menampilkan semua kemungkinan array O dari bilangan bulat non-negatif dengan k dengan batasan 0 ≤ O i ≤ I i . Untuk mendapatkan dari satu array ke array berikutnya, Anda dapat menambah atau mengurangi 1 ke satu nilai dalam array. Kode Anda tidak boleh menampilkan array yang sama dua kali. Jika jumlah array yang berbeda untuk di-output sangat besar, kode Anda harus menjalankan keluaran selamanya sampai mati.
Contohnya
Jika saya adalah array dari k maka ini adalah masalah iterasi pada semua kode Gray dengan lebar bit k , kecuali bahwa elemen pertama dan terakhir tidak perlu dapat dijangkau dalam satu langkah.
Jika
I = [2,1]
kemudian salah satu kemungkinan pemesanan array output adalah(0,0),(0,1),(1,1),(1,0),(2,0),(2,1)
- Jika
I = [2,1,3]
kemudian salah satu kemungkinan pemesanan array output adalah(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),...
.
Ini adalah tantangan kode-golf, pengajuan dengan kode sumber dengan kemenangan terpendek. Jangan biarkan jawaban singkat dalam bahasa golf menghalangi Anda untuk mengirim jawaban dalam bahasa lain. Cobalah untuk memberikan jawaban terpendek dalam bahasa apa pun.
Ini juga merupakan tantangan dengan kompleksitas terbatas. Setiap array baru harus di-output dengan O (k) waktu berlalu sejak array yang di-output sebelumnya (atau awal program untuk array pertama yang di -output ). Ini berarti bahwa waktu berjalan per larik keluaran baru (masing-masing panjang k ) tidak boleh lebih besar dari O (k) . Itu harus mengambil proporsi waktu untuk k dan tidak, misalnya k 2 atau 2 k . Catatan ini bukan waktu rata-rata per output tetapi waktu kasus terburuk untuk setiap array yang dihasilkan.
Anda dapat mengasumsikan bahwa semua aritmatika pada bilangan bulat 64 bit dapat dilakukan dalam waktu konstan seperti dapat membaca dan mengeluarkannya serta penugasan dan mencari dan mengubah nilai dalam array.
Salah satu konsekuensi dari kompleksitas terbatas adalah bahwa solusi yang hanya dihasilkan pada saat keluar dari program tidak dapat diterima.
I_i+1
? Bisakah Anda mencapai 0 dariI_i
?)n
dank
terbatas? dengan asumsi mereka pergi hingga tak terbatas dengan lebar bit bagaimana cara pergiJawaban:
Python 3 , 116 byte
Cobalah online!
Terima kasih Mnemonic untuk -1 byte.
Fungsi generator. (terima kasih Dennis untuk mengingatkan saya, saya lupa fitur ada) Jika output harus dicetak ke stdout kemudian gunakan
print(t,flush=1)
untuk 9 byte tambahan, atau jika Python dipanggil dengan-u
,print(t)
cukup untuk +1 byte.Berhenti dengan kesalahan (
IndexError
). Jika Anda ingin memanggil fungsi ini dan kemudian melanjutkan program, Anda harus menangkapnya.sumber
k
langkah, karena pada setiap langkahi
meningkat dengan1
dan setelahk
langkahi==k
dand[i]
menyebabkan kesalahan.not 0<=
dengannot-1<
.yield t
bukanprint(t,flush=1)
?Stax , 22 byte
Jalankan dan debug itu
Inilah yang besar untuk menunjukkan perilaku asimptotik .
Dibongkar, tidak diserang, dan dikomentari, sepertinya ini.
Jalankan yang ini
sumber
O(k)
bit, jadik
waktu pembagian mungkin memakanO(k²)
waktu ...JavaScript (Node.js) , 114 byte
Cobalah online! Tidak Disatukan:
sumber
Kotlin ,
181178 byteTerima kasih kepada: Anush menunjukkan bahwa saya salah memahami tantangan menghemat 2 byte. Ovs menunjukkan penghematan 1 byte.
Cobalah online!
sumber
while(true)
dapatwhile(1<2)