Seorang musafir perlu menginap selama n hari di sebuah hotel di luar kota. Dia kehabisan uang tunai dan kartu kreditnya telah kedaluwarsa. Tetapi dia memiliki rantai emas dengan n link.
Aturan di hotel ini adalah penghuni harus membayar sewa setiap pagi. Pelancong mencapai kesepakatan dengan manajer untuk membayar satu mata rantai emas untuk setiap hari. Tetapi manajer juga menuntut agar pelancong harus membuat kerusakan sesedikit mungkin pada rantai sambil membayar setiap hari. Dengan kata lain, dia harus menemukan solusi untuk memotong sesedikit mungkin tautan.
Memotong tautan menciptakan tiga subkunci: satu berisi hanya tautan terpotong, dan satu di setiap sisi. Sebagai contoh, memotong tautan ketiga dari rantai panjang 8 menciptakan subchains panjang [2, 1, 5]. Manajer senang melakukan perubahan, sehingga pelancong dapat membayar hari pertama dengan rantai panjang 1, lalu hari kedua dengan rantai panjang 2, mendapatkan rantai pertama kembali.
Kode Anda harus memasukkan panjang n , dan menampilkan daftar tautan untuk memotong panjang minimum.
Aturan :
- n adalah bilangan bulat> 0.
- Anda dapat menggunakan pengindeksan berbasis 0 atau 1 untuk tautan.
- Untuk beberapa angka, solusinya tidak unik. Misalnya, jika
n = 15
keduanya[3, 8]
dan[4, 8]
merupakan output yang valid. - Anda dapat mengembalikan daftar, atau mencetaknya dengan pemisah yang masuk akal.
- Ini adalah kode-golf , jadi kode terpendek dalam byte menang.
Kasus uji :
Input Output (1-indexed)
1 []
3 [1]
7 [3]
15 [3, 8]
149 [6, 17, 38, 79]
Contoh terperinci
Untuk n = 15, memotong tautan 3 dan 8 menghasilkan subchains of length [2, 1, 4, 1, 7]
. Ini adalah solusi yang valid karena:
1 = 1
2 = 2
3 = 1+2
4 = 4
5 = 1+4
6 = 2+4
7 = 7
8 = 1+7
9 = 2+7
10 = 1+2+7
11 = 4+7
12 = 1+4+7
13 = 2+4+7
14 = 1+2+4+7
15 = 1+1+2+4+7
Tidak ada solusi dengan hanya satu potongan, jadi ini adalah solusi optimal.
Tambahan
Perhatikan bahwa masalah ini terkait dengan partisi integer. Kami sedang mencari partisi P dari n sehingga semua bilangan bulat dari 1 sampai n memiliki setidaknya satu patition yang merupakan bagian dari P .
Berikut adalah video YouTube tentang satu kemungkinan algoritma untuk masalah ini.
sumber
1+2
. Dari mana datangnya 2-link-chain kedua?Jawaban:
05AB1E ,
23118 byteCobalah online!
Menggunakan pengindeksan berbasis 0.
Penjelasan:
иg
terlihat seperti noop, tetapi sebenarnya melakukan dua hal yang berguna: itu memotong ke integer (;
mengembalikan float), dan itu crash penerjemah jika x negatif (ini adalah satu-satunya kondisi keluar).Solusi 23 byte menggunakan pendekatan yang sangat berbeda, jadi ini untuk anak cucu:
ÅœʒR2äθP}ʒæOê¥P}θ2äθη€O
( TIO , penjelasan ).sumber
Ø.Ø
. Apakah Anda hanya mencoba beberapa hal acak untuk memetakan dan memetakan semua negatif-1
? Apapun, jawaban yang sangat bagus dan jauh lebih pendek daripada yang saya perkirakan. Saya berpikir sekitar 20 byte setelah saya memposting 42-byter saya yang buruk.Ø.Ø
sebenarnya adalah ide pertama saya. Komentar anda mengilhami saya untuk mencoba hal-hal acak: Saya menemukan®Ÿà
,ï®M
, dan yang lebih penting,иg
yang menghasilkan ini bagus 8-byter. Saya selalu merasa menjengkelkan bahwa osabie lebih suka tidak melakukan apa-apa selain menabrak dalam banyak kasus (div oleh 0, tipe yang salah, dll), jadi crash ini akan berguna.Python 2 , 75 byte
Cobalah online!
Penjelasan:
Membangun urutan potongan 'biner', dengan nomor dasar yang cocok dengan jumlah potongan.
Misalnya:
63
dapat dilakukan dalam 3 pemotongan, yang berarti partisi di basis-4 (karena kami memiliki 3 dering tunggal):Cuts:,
5, 14, 31
yang memberikan rantai4 1 8 1 16 1 32
(diurutkan:)1 1 1 4 8 16 32
.Semua nomor dapat dibuat:
Contoh lain:
sumber
f=
ke awal? Karena Anda menggunakan panggilan kef
dalam fungsi lambda, dan saya hanya bisa berasumsi bahwa Anda merujuk ke lambda yang sama dengan yang Anda tetapkan.f
tidak rekursif, tetapi itu direferensikan dalam kode dan karenanya harus dinamai.R ,
7769 byte-8 Bytes berkat Aaron Hayman
Cobalah online!
(Subchain terakhir mungkin perlu dibuat lebih pendek jika kita melebihi total panjang rantai.)
Tidak digabungkan (berdasarkan versi sebelumnya yang serupa):
sumber
n=1
, tetapi cara alternatif untuk menghasilkan cutoff adalah pengulangan1, 4, 4a(n-1)-4a(n-2)
.k
; ini sesuai dengan OEIS A134401: oeis.org/A134401 Tetapi implementasi saya dari relasi perulangan membutuhkan lebih banyak byte daripada kode saat ini.sum
bukanmatch
.Jelly , 12 byte
Cobalah online!
Terjemahan jawaban 05AB1E Grimy jadi pastikan untuk mengungguli yang juga! Sedikit kecewa ini datang dalam satu byte lebih lama, tetapi setidaknya memiliki sesuatu yang sedikit seperti emoticon sebagai tiga byte pertama!
sumber
JavaScript (ES6), 66 byte
Ini adalah port jawaban TFeld .
Cobalah online!
sumber
C ++,
109, 107 byte-2 byte terima kasih kepada Kevin
Algoritma ini mirip dengan jawaban Robin Ryder. Kode ditulis dalam bentuk utuh yang dapat dikompilasi. Cobalah!
Detail:
Ini memiliki variasi C dengan panjang byte yang sama (tampaknya tidak memerlukan jawaban terpisah):
sumber
=0
setelahk
dapat dihapus, karena ini0
secara default.std::cin>>n;while(++k<<k<n);
bisafor(std::cin>>n;++k<<k<n;);
. Saya juga punya perasaanfor(n-=k;n>0;k*=2,n-=k+1)
bisa disederhanakan entah bagaimana dengan menggabungkan barang-barang, tetapi tidak yakin bagaimana caranya. PS: Mengubah pembatas koma ke ruang terlihat sedikit lebih baik karena Anda tidak melihat satu jejak imo, tapi ini murni kosmetik :)=0
itu perlu untuk portabilitas;) Saya juga menyadari bahwa ruang setelah#include
itu tidak diperlukan.std::cin>>n
di dalamnya.Retina 0.8.2 , 61 byte
Cobalah online! Port 1 terindeks dari jawaban @ Grimy. Penjelasan:
Mulai dengan
N=2
dan input dikonversi ke unary.Berulang kali mencoba untuk mengurangi
N
dari input dan kemudian bagi dengan 2.Jika berhasil, ingat 1 lebih dari input pada baris sebelumnya, naikkan
N
pada baris saat ini, dan perbarui input ke nilai baru.Hapus
N
dan tambahkan nilai terakhir sehingga juga 1-diindeks.Hapus input asli yang ditambahkan.
Ubah hasilnya menjadi desimal.
sumber
Ruby , 62 byte
Cobalah online!
Sebagian besar dicuri dari jawaban Python TFeld.
sumber