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 adalah12
)23 2
(produk adalah46
)32 2
(produk adalah64
)22 3
(produk adalah66
)
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
)
Jawaban:
CJam,
32282312 byteCobalah 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
sumber
l2%_,,1>\e!m*{~S+m<~*}%$W=
.l2%S+e!{0\~*}%$W=
.CJam,
3635 byteCukup 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
sumber
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)
Solusi saya
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:
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
Tes menggunakan cuplikan di bawah ini di Firefox.
sumber
Python 3, 111 byte
Mungkin jauh lebih golf. Saya suka waktu berjalannya (O ( n log n ), kan?).
Tidak diganggu dengan penjelasan.
sumber
Pyth, 25 byte
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.
sumber
R, 164
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:
Diperluas dengan beberapa komentar
Dan beberapa uji coba (diimplementasikan sebagai fungsi yang disebut g)
sumber