Latar Belakang

Mata uang resmi negara imajiner Golfenistan adalah foo , dan hanya ada tiga jenis koin yang beredar: 3 foo , 7 foo , dan 8 foo . Orang dapat melihat bahwa tidak mungkin untuk membayar jumlah tertentu, seperti 4 foos, menggunakan koin ini. Namun demikian, semua jumlah yang cukup besar dapat dibentuk. Tugas Anda adalah menemukan jumlah terbesar yang tidak dapat dibentuk dengan koin (5 foos dalam hal ini), yang dikenal sebagai masalah koin .

Memasukkan

Input Anda adalah daftar bilangan bulat positif, yang mewakili nilai koin yang beredar. Dua hal dijamin tentang hal itu:L = [n1, n2, ..., nk]

• GCD elemen Ladalah 1.
• L tidak mengandung angka 1.

Mungkin tidak disortir dan / atau mengandung duplikat (pikirkan koin edisi khusus).

Keluaran

Karena GCD dari Ladalah 1, setiap bilangan bulat yang cukup besar mdapat dinyatakan sebagai kombinasi linier non-negatif dari elemen-elemennya; dengan kata lain, kita punya

 m = a1*n1 + a2*n2 + ... + ak*nk 

untuk beberapa bilangan bulat . Output Anda adalah bilangan bulat terbesar yang tidak dapat diungkapkan dalam formulir ini. Sebagai petunjuk, diketahui bahwa output selalu kurang dari , jika dan merupakan elemen maksimal dan minimal dari ( referensi ).ai ≥ 0(n1 - 1)*(nk - 1)n1nkL

Aturan

Anda dapat menulis program atau fungsi lengkap. Hitungan byte terendah menang, dan celah standar tidak diizinkan. Jika bahasa Anda memiliki operasi bawaan untuk ini, Anda mungkin tidak menggunakannya. Tidak ada persyaratan untuk efisiensi waktu atau memori, kecuali bahwa Anda harus dapat mengevaluasi kasus pengujian sebelum mengirim jawaban Anda.

Setelah saya memposting tantangan ini, pengguna @vihan menunjukkan bahwa Stack Overflow memiliki duplikat yang tepat . Berdasarkan diskusi Meta ini , tantangan ini tidak akan dihapus sebagai duplikat; namun, saya meminta semua jawaban berdasarkan versi SO harus mengutip aslinya, diberi status Komunitas Wiki, dan dihapus jika penulis asli ingin memposting jawaban mereka di sini.

Uji Kasus

[3, 7, 8] -> 5
[25, 10, 16] -> 79
[11, 12, 13, 14, 13, 14] -> 43
[101, 10] -> 899
[101, 10, 899] -> 889
[101, 10, 11] -> 89
[30, 105, 70, 42] -> 383
[2, 51, 6] -> 49

Pyth, 23 byte

ef!fqTs.b*NYQY^UTlQS*FQ

Ini sangat lambat, karena memeriksa semua nilai hingga produk dari semua koin. Berikut adalah versi yang hampir identik, tetapi 1) mengurangi set koin menjadi koin yang tidak dapat dibagi satu sama lain dan 2) hanya memeriksa nilai hingga (max(coins) - 1) * (min(coins) - 1)(47 byte):

=Qu?.A<LiHdG+GHGQYef!fqTs.b*NYQY^UTlQS*thSQteSQ

Penjelasan

                   S            range 1 to
                    *FQ         product of input
 f                             filter by
               UT                range 0 to T 
              ^  lQ              cartesian power by number of coins
   f                            filter by
      s.b*NYQY                   sum of coin values * amounts
    qT                           equals desired number T
  !                             nothing matching that filter
e                             take last (highest) element

Perl, 60 54 51 byte

50 byte kode + 1 byte baris perintah

$.*=$_,$r.=1x$_."|"}{$_=$.while(1x$.--)=~/^($r)+$/

Akan melakukan golf dan memposting penjelasan nanti. Pendekatan dasar adalah membiarkan mesin regex melakukan kerja keras dengan pencocokan string. Misalnya, ia akan membuat regex yang mirip ^(.{3})*(.{7})*(.{8})*$dan cocok dengan untaian panjang di nmana nturun dari produk input sampai gagal mencocokkan.

Perhatikan bahwa ini akan menjadi lambat secara eksponensial karena jumlah argumen meningkat.

Penggunaan: Argumen dibaca dari STDIN (dipisahkan baris baru), misalnya:

printf "101\n10" | perl -p entry.pl

R , 84 78 byte

$a_1, a_2,\ldots$

a=scan();max((1:(b<-min(a)*max(a)))[-colSums(combn(outer(a,0:b),sum(!!a)))])

Cobalah online!

$a_i$outercolSums

Versi yang lebih cepat tetapi lebih lama (dua byte) hanya mempertimbangkan max(a):

a=scan();max((1:(min(a)*(b<-max(a))))[-apply(combn(outer(a,0:b,"*"),sum(!!a)),2,sum)])

Versi yang sedikit lebih pendek (78 byte) yang paling sering memakan waktu terlalu login atau terlalu banyak ruang untuk berjalan di Coba secara online adalah

a=scan();max((1:(b<-prod(a)))[-apply(combn(outer(a,0:b,"*"),sum(!!a)),2,sum)])

Python2, 188 187 byte

def g(L):
 M=max(L);i=r=0;s=[0]*M;l=[1]+s[1:]
 while 1:
    if any(all((l+l)[o:o+min(L)])for o in range(M)):return~-s[r]*M+r
    if any(l[(i-a)%M]for a in L):l[i]=1
    else:r=i
    s[i]+=1;i=(i+1)%M

Lekukan kedua diberikan sebagai 4 spasi pada SO, itu harus tab.

Sebenarnya solusi 'cepat', bukan bruteforce, menggunakan 'Metode Wilf' seperti yang dijelaskan di sini .

Javascript ES6, 120 130 126 128 127 125 karakter

f=a=>`${r=[1|a.sort((a,b)=>a-b)]}`.repeat(a[0]*a[a.length-1]).replace(/./g,(x,q)=>r[q]|a.map(x=>r[q+x]|=r[q])).lastIndexOf(0)

Versi 126 karakter alternatif:

f=a=>{r=[1];a.sort((a,b)=>a-b);for(q=0;q<a[0]*a[a.length-1];++q)r[q]?a.map(x=>r[q+x]=1):r[q]=0;return r.join``.lastIndexOf(0)}

Uji:

"[3, 7, 8] -> 5\n\
[25, 10, 16] -> 79\n\
[11, 12, 13, 14, 13, 14] -> 43\n\
[101, 10] -> 899\n\
[101, 10, 899] -> 889\n\
[101, 10, 11] -> 89\n\
[30, 105, 70, 42] -> 383\n\
[2, 51, 6] -> 49".replace(/(\[.*?\]) -> (\d+)/g, function (m, t, r) {
  return f(JSON.parse(t)) == r
})