Produk Gabungan Maksimum

11

Kami diberi daftar bilangan bulat p1, ..., pk (tidak harus berbeda) di mana masing-masing memiliki nilai antara 1 dan 9, termasuk. Dengan menggunakan masing-masing p1, ..., pk tepat sekali, kita dapat membentuk rangkaian angka, untuk mencapai daftar angka baru; kami kemudian mengeluarkan produk dari daftar baru ini. Tujuannya adalah untuk memaksimalkan produk ini dengan memilih rangkaian angka terbaik.

Sebagai contoh, kita diberikan daftar: 2 3 2 (dipisahkan oleh spasi). Kami dapat membentuk rangkaian berikut:

  • 2 3 2(produk dari rangkaian ini adalah 12)
  • 23 2(produk adalah 46)
  • 32 2(produk adalah 64)
  • 22 3(produk adalah 66)

Karena produk terbesar yang dapat kami bentuk rangkaian adalah 66, kami mengeluarkannya.

Aturan:

  • Harus ada setidaknya satu perkalian (yaitu, Anda tidak bisa hanya menggabungkan semua angka dan keluaran itu).
  • Anda tidak dapat menggunakan operator lain selain dari perkalian, atau menyisipkan tanda kurung, dll.
  • Asumsikan bahwa daftar bilangan bulat yang diberikan dipisahkan oleh spasi, dan semua bilangan bulat memiliki nilai antara 1 dan 9.

Kode terpendek (dalam byte) menang!

Kasus uji:

Input: 1 2 3; Output: 63(yaitu, 21*3)

Input: 2 5 9; Keluaran: 468( 52*9)

Input: 1 2 3 4; Keluaran: 1312( 41*32)

Ryan
sumber
Haruskah kita menulis seluruh program atau fungsi mengambil parameter input dan mengembalikan hasilnya juga baik-baik saja?
randomra
@randomra Ya, tidak apa-apa.
Ryan
Untuk setiap pasangan angka a, b, produk a * b.kurang dari ab gabungan sederhana (= a * 10 ^ (digit b) + b). Jadi hanya 1 produk (seperti itu wajib). Tambahkan ini: codegolf.stackexchange.com/q/49854/21348
edc65

Jawaban:

8

CJam, 32 28 23 12 byte

0le!f{~*}:e>

Cobalah online di penerjemah CJam .

Terima kasih kepada @ user23013 karena membantu saya menghemat 16 byte penuh!

Ide

Mengganti karakter dalam string input membaginya menjadi bilangan bulat (kelompok digit berurutan) yang dipisahkan oleh spasi. Dengan mendorong nol dan kemudian mengevaluasi string input yang diijinkan, kami mendorong dua atau lebih bilangan bulat. Mengalikan dua paling atas akan menghasilkan produk input dibagi menjadi dua bilangan bulat atau nilai suboptimal.

Kode

 le!         e# Push all possible character permutations of the input.
0   f{  }    e# For each permutation:
             e#   Push 0, then the permuted string.
      ~      e#   Evaluate the string. Pushes one or more integers.
       *     e#   Multiply the two topmost integers.
         :e> e# Retrieve the greatest integer in the array.
Dennis
sumber
1
l2%_,,1>\e!m*{~S+m<~*}%$W=.
jimmy23013
2
l2%S+e!{0\~*}%$W=.
jimmy23013
2

CJam, 36 35 byte

q~]_,([SL]m*{s},\e!\m*{z[s~]:*}%$W=

Cukup lurus ke depan. Iterasi semua kemungkinan kombinasi dan urutkan berdasarkan produk. Kemudian output terbesar. Semua ini, ingatlah bahwa setidaknya 1 perkalian harus ada.

Akan segera tambahkan penjelasan.

Cobalah online di sini

Pengoptimal
sumber
1

JavaScript (ES6) 125

Sunting Saya pikir @oberon sudah benar: "setiap digit baru harus digabungkan ke angka terkecil"

Saya tidak akan mengubah jawaban ini mencuri idenya. Implementasi dalam ES6 akan menjadi 70 byte (tanda diubah dibandingkan untuk membandingkan sebagai jumlah dan bukan string)

f=l=>l.split(' ').sort().reverse().map(d=>-a>-b?a+=d:b+=d,a=b='')||a*b

Solusi saya

f=l=>(i=>{for(r=0;a=b='',k=--i;r<a*b?r=a*b:0)for(v of l)k&1?a+=v:b+=v,k/=2})(1<<~-(l=l.split(' ').sort().reverse()).length)|r

Seperti yang saya katakan di komentar, untuk setiap pasangan angka a, b, produk a * b kurang dari gabungan sederhana ab (= a * 10 ^ (digit b) + b). Jadi lebih baik menghindari produk dan lebih memilih penggabungan, tetapi karena setidaknya 1 produk diminta, kita harus membuat 2 angka dan mengalikannya.

Saya mencoba semua kemungkinan pengelompokan angka, membangun sepasang angka untuk dikalikan. Masing-masing angka dibangun dengan jelas mengambil digit dalam urutan menurun.

Misalnya, dengan daftar 4 angka, [1 2 3 4] - coba:

  • 4 * 321
  • 43 * 21
  • 42 * 31
  • 41 * 32
  • 432 * 1
  • 431 * 2
  • 421 * 3

Maks dari nilai ini adalah hasil yang kita butuhkan.

Pengelompokan dapat dihitung perulangan pada bitmap 4 bit, dengan nilai min 0001 dan nilai maks 0111 (yaitu 1 << (4 -1) - 1)

Tidak terlalu bermain golf

f=l=>{
  l = l.split(' '); // string to array
  l.sort().reverse(); // decreasing order 
  m = 1 << (l.length-1); starting value fro loop
  r = 0 
  // loop from m-1 down to 1
  for(i=m; --i; )
  {
    a = b = '';
    k = i;
    for(v of l) // divide the digits base on bits of i
    {
      k & 1 ? a+=v : b+=v;
      k /= 2;
    }
    if (r < a*b) r = a*b; // remember max value in r
  }
  return r
}

Tes menggunakan cuplikan di bawah ini di Firefox.

f=l=>(i=>{for(r=0;a=b='',k=--i;r<a*b?r=a*b:0)for(v of l)k&1?a+=v:b+=v,k/=2})(1<<~-(l=l.split(' ').sort().reverse()).length)|r

t=l=>(i=>{for(x=r='';a=b='',k=--i;r<a*b?(r=a*b,x=' = '+a+'x'+b):0)for(v of l)k&1?a+=v:b+=v,k/=2})
(1<<~-(l=l.split(' ').sort().reverse()).length)|| x

function go()
{
  R.value = f(I.value) // TEST AS IS
   + t(I.value) // Some more info
}

test=['1 2 3 4','1 2 3','2 5 9','8 9 8']

test.forEach(t => O.innerHTML = O.innerHTML + (t + ' -> ' + f(t)) + '\n')
Type your list: <input id=I><button onclick='go()'>-></button><input readonly id=R><br>
<pre id=O></pre>

edc65
sumber
1

Python 3, 111 byte

Mungkin jauh lebih golf. Saya suka waktu berjalannya (O ( n log n ), kan?).

l=sorted(map(int,input().split()),reverse=1);m=[0,0]
for x in l:i=m[0]>m[1];m[i]=m[i]*10+x
print(m[0]*m[1])

Tidak diganggu dengan penjelasan.

# edc65 has already explained that the optimal solution can be found applying a single
# multiplication. thus, given that
#     (10x + d)y > (10y + d)x
# where x, y are the two numbers and d is the next digit to insert, it follows that
#     y > x
# and thus each new digit must be concatenated to the smallest number. obviously, digits
# should be added in descending order.
l = sorted(map(int, input().split()), reverse=1)
m = [0,0]
for x in l:
    i = m[0] > m[1]
    m[i] = m[i]*10 + x
print(m[0] * m[1])
Oberon
sumber
0

Pyth, 25 byte

eSsmm*ss<dkss>dkr1ld.pcz)

Saya mengulangi setiap permutasi input. Kemudian karena setiap kombinasi optimal terdiri dari dua bilangan bulat, saya hanya membaginya pada setiap posisi yang memungkinkan, dan mengalikan perpecahan bersatu. Saya kemudian mengurutkan dan mendapatkan elemen terakhir.

orlp
sumber
0

R, 164

function(n){l=length(n);a=sort(n,T);i=1;while(a[i]==a[i+1]&&i<l-2)i=i+2;a[c(i,i+1)]=a[c(i+1,i)];eval(parse(t=paste0(c(a[1:l%%2==1],"*",a[1:l%%2==0]),collapse='')))}

Sebagai metode saya tidak yakin apakah ini kuat. Dengan kasus-kasus yang telah saya uji tampaknya berfungsi setiap waktu. Saya mencoba mengujinya terhadap solusi pengoptimal dan tampaknya OK juga untuk itu. Saya lebih dari siap untuk terbukti salah :) Ada ruang untuk bermain golf, tetapi saya berharap untuk mendapatkan umpan balik tentang metode ini terlebih dahulu.

Proses umum adalah:

  • Urutkan daftar dalam urutan menurun
  • Tukar pasangan ganjil / genap pertama yang berbeda
  • Gabungkan item genap dan ganjil dari daftar
  • Evaluasi produk dari dua hasil

Diperluas dengan beberapa komentar

function(n){
    l=length(n);
    a=sort(n,T);    # sort descending order
    # Determine which pair to swap
    i=1;
    while(a[i]==a[i+1]&&i<l-2)i=i+2;
    a[c(i,i+1)]=a[c(i+1,i)];  # swap pair   
    # concatenate the even and odd indices items around a * and evaluate    
    eval(parse(t=paste0(c(a[1:l%%2==1],"*",a[1:l%%2==0]),collapse=''))) 
}

Dan beberapa uji coba (diimplementasikan sebagai fungsi yang disebut g)

> g(c(1,2,3))
[1] 63
> g(c(2,5,9))
[1] 468
> g(c(1,2,3,4))
[1] 1312
> g(c(1,2,3,5,5,5))
[1] 293132
> g(c(1,5,7,7,9,9))
[1] 946725
> g(c(1,7,8,9,9,9))
[1] 978117
> g(c(7,8,9,9,9))  #Test case provided edc65 to randomra
[1] 97713
MickyT
sumber