Potong rantai emas

32

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 = 15keduanya [3, 8]dan [4, 8]merupakan output yang valid.
  • Anda dapat mengembalikan daftar, atau mencetaknya dengan pemisah yang masuk akal.
  • Ini adalah , 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.

polfosol ఠ_ఠ
sumber
Saya tidak mengerti referensi "melakukan perubahan". Dalam contoh yang Anda posting, pada hari kedua Anda membayar dengan rantai 2-tautan (dan mendapatkan rantai-1-tautan (yang Anda bayar dengan hari sebelumnya) kembali sebagai perubahan, sesuai penjelasan Anda). Tetapi pada hari ketiga, Anda membayar dengan 1+2. Dari mana datangnya 2-link-chain kedua?
Flater
4
@Flater Manajer sudah memilikinya. Kami hanya membayar yang tambahan. Faktanya, RHS adalah tautan yang dimiliki manajer setiap hari
polfosol ఠ_ఠ

Jawaban:

15

05AB1E , 23 11 8 byte

ΔÍN-;иg=

Cobalah online!

Menggunakan pengindeksan berbasis 0.

Penjelasan:

             # start from the implicit input
Δ            # loop forever
 Í           # subtract 2
  N-         # subtract the current iteration number
    ;        # divide by 2
     и       # create a list of length x
      g      # get the length of the list
       =     # print

иgterlihat 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 ).

Grimmy
sumber
2
Saya telah menghapus jawaban saya. Milik saya menjadi 42 dan Anda menjadi 11 adalah terlalu besar perbedaan bagi saya untuk tidak merasa malu, haha. ;) Jawaban yang bagus, dan lol di Ø.Ø. 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.
Kevin Cruijssen
2
@KevinCruijssen Nnope, Ø.Øsebenarnya adalah ide pertama saya. Komentar anda mengilhami saya untuk mencoba hal-hal acak: Saya menemukan ®Ÿà, ï®M, dan yang lebih penting, иgyang 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.
Grimmy
2
Hehe, 05AB1E seharusnya tidak pernah crash, tetapi Anda benar bahwa kadang-kadang agak menjengkelkan itu tidak pernah terjadi .. Dalam warisan saya bahkan tidak tahu bagaimana menabrak, dan di masa lalu kami bahkan memiliki divisi eksplisit oleh nol kesalahan yang bisa kita panggil secara manual. xD Pada versi baru masih sering crash dengan kesalahan cukup sering ketika memberikan argumen yang salah untuk builtin tertentu. Dan bagus -3 lagi.
Kevin Cruijssen
2
+ msgstr "crash interpreter jika x negatif (ini adalah satu-satunya syarat keluar)." - Saya suka itu
John Dvorak
9

Python 2 , 75 byte

f=lambda n,i=0:n>=i<<i and f(n,i+1)or[min(n,2**j*i-i+j)for j in range(1,i)]

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, 31yang memberikan rantai 4 1 8 1 16 1 32(diurutkan:) 1 1 1 4 8 16 32.

Semua nomor dapat dibuat:

1       1
2       1 1
3       1 1 1
4       4
...
42      1 1 8 32
...
62      1 1 4 8 16 32
63      1 1 1 4 8 16 32

Contoh lain:

18: 4,11        ->  3 1 6 1 7
27: 5,14,27     ->  4 1 8 1 13 1
36: 5,14,31     ->  4 1 8 1 16 1 5
86: 6,17,38,79  ->  5 1 10 1 20 1 40 1 7
TFeld
sumber
1
Bukankah seharusnya Anda menambahkan f=ke awal? Karena Anda menggunakan panggilan ke fdalam fungsi lambda, dan saya hanya bisa berasumsi bahwa Anda merujuk ke lambda yang sama dengan yang Anda tetapkan.
randomdude999
@ randomdude999, Ya, saya lupa ...
TFeld
@ randomdude999 apakah aturan itu berlaku untuk semua bahasa, atau hanya python? Karena saya melihat jawaban javascript yang merupakan lambda murni dalam tantangan ini ...
Shadow
3
@Shadow Ini berlaku untuk semua bahasa, tetapi hanya untuk lambda rekursif.
TFeld
1
@Shadow Aturan yang lebih umum adalah bahwa Anda tidak dapat mereferensikan sesuatu yang tidak didefinisikan dalam kode Anda atau didefinisikan secara global dalam bahasa Anda, kecuali jika secara eksplisit diizinkan oleh tantangan. Kasus yang paling umum adalah fungsi rekursif, tetapi ini berlaku untuk situasi lain. Jawaban ini adalah contoh lain: ftidak rekursif, tetapi itu direferensikan dalam kode dan karenanya harus dinamai.
Arnauld
8

R , 77 69 byte

-8 Bytes berkat Aaron Hayman

pmin(n<-scan(),0:(k=sum((a=2:n)*2^a<=n))+cumsum((k+2)*2^(0:k))+1)[-n]

Cobalah online!

kk(k+1)2kn1,1,,1k(k+1),2(k+1),4(k+1),8(k+1),,(k+1)2k1

(Subchain terakhir mungkin perlu dibuat lebih pendek jika kita melebihi total panjang rantai.)

Tidak digabungkan (berdasarkan versi sebelumnya yang serupa):

n = scan()                            # read input
if(n - 1){                            # If n==1, return NULL
  k = match(F, (a = 2:n) * 2 ^ a > n) # compute k
  b = (k + 1) * 2 ^ (1:k - 1)         # lengths of subchains
  c = 1:k + cumsum(b)                 # positions of cuts
  pmin(c, n )                         # if last value is >n, coerce it to n
}

kkkk+12k+12k+24k+4k(k+1)2k1.)

a(k)nka(k)

Robin Ryder
sumber
Saya ragu itu akan membantu dengan kasus khusus n=1, tetapi cara alternatif untuk menghasilkan cutoff adalah pengulangan 1, 4, 4a(n-1)-4a(n-2).
Peter Taylor
@PeterTaylor Saya memiliki pengulangan yang sama untuk komputasi k; ini sesuai dengan OEIS A134401: oeis.org/A134401 Tetapi implementasi saya dari relasi perulangan membutuhkan lebih banyak byte daripada kode saat ini.
Robin Ryder
Sedikit pengaturan ulang saya turun ke 73. Cobalah online!
Aaron Hayman
@ Harunman Terima kasih! Langkah cerdas menggunakan sumbukan match.
Robin Ryder
69 byte dan singkirkan itu jika pernyataan yang membuat Anda kesal: Coba online!
Aaron Hayman
3

Jelly , 12 byte

’_‘ɼ:2»-µƬṖḊ

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!

Nick Kennedy
sumber
2

C ++, 109 , 107 byte

-2 byte terima kasih kepada Kevin

#include<iostream>
main(){int n,k=0;for(std::cin>>n;++k<<k<n;);for(n-=k;n>0;k*=2,n-=k+1)std::cout<<n<<',';}

Algoritma ini mirip dengan jawaban Robin Ryder. Kode ditulis dalam bentuk utuh yang dapat dikompilasi. Cobalah!

Detail:

std::cin>>n;               // get the value of n as input
while(++k<<k<n);           // determine k
for(n-=k;n>0;k*=2,n-=k+1)  // we don't need n, so the lengths...
    std::cout<<n<<' ';     // of links are subtracted repeatedly

Ini memiliki variasi C dengan panjang byte yang sama (tampaknya tidak memerlukan jawaban terpisah):

#include<stdio.h>
main(){int n,k=0;for(scanf("%d",&n);++k<<k<n;);for(n-=k;n>0;k*=2,n-=k+1)printf("%d,",n);}
polfosol ఠ_ఠ
sumber
Dua hal kecil untuk golf: =0setelah kdapat dihapus, karena ini 0secara default. std::cin>>n;while(++k<<k<n);bisa for(std::cin>>n;++k<<k<n;);. Saya juga punya perasaan for(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 :)
Kevin Cruijssen
1
@KevinCruijssen Terima kasih, tetapi beberapa kompiler tidak menetapkan nilai default ke variabel non-statis. Jadi saya pikir =0itu perlu untuk portabilitas;) Saya juga menyadari bahwa ruang setelah #includeitu tidak diperlukan.
polfosol ఠ_ఠ
Ah baiklah. Saya tidak tahu C ++ terlalu baik, jadi saya telah menggunakan kompiler online yang Anda tautkan dalam jawaban Anda untuk menguji beberapa hal. :) Anda lupa perubahan kedua yang saya usulkan dalam komentar saya: while-loop ke-for-loop dan meletakkan std::cin>>ndi dalamnya.
Kevin Cruijssen
103 byte
ceilingcat
1

Retina 0.8.2 , 61 byte

.+
11,$&$*
+`\b(1+),(\1(1*)1?\3)$
1$2¶1$1,$3
1+,
1
1A`
1+
$.&

Cobalah online! Port 1 terindeks dari jawaban @ Grimy. Penjelasan:

.+
11,$&$*

Mulai dengan N=2dan input dikonversi ke unary.

+`\b(1+),(\1(1*)1?\3)$

Berulang kali mencoba untuk mengurangi Ndari input dan kemudian bagi dengan 2.

1$2¶1$1,$3

Jika berhasil, ingat 1 lebih dari input pada baris sebelumnya, naikkan Npada baris saat ini, dan perbarui input ke nilai baru.

1+,
1

Hapus Ndan tambahkan nilai terakhir sehingga juga 1-diindeks.

1A`

Hapus input asli yang ditambahkan.

1+
$.&

Ubah hasilnya menjadi desimal.

Neil
sumber
1

Ruby , 62 byte

->n{(1...c=(0..n).find{|r|n<r<<r}).map{|b|[n,b-c+(c<<b)].min}}

Cobalah online!

Sebagian besar dicuri dari jawaban Python TFeld.

GB
sumber