Nah, ketika saya membeli hadiah untuk dua istri saya, saya ingin mereka merasa sama pentingnya bagi saya, tetapi sulit untuk pergi berbelanja dengan anggaran tetap. Sebagai gantinya, saya membeli banyak barang dan membaginya menjadi dua kelompok dengan nilai yang sama mungkin. Lalu saya membeli banyak cokelat untuk memperbaiki sisanya.
Tetapi saya tidak ingin melakukan semua yang sulit ketika komputer saya dapat melakukannya. Dan kamu juga tidak. Jadi selesaikan masalah ini sehingga pada saat Anda perlu membagi hadiah di antara istri Anda, Anda tahu itu akan mudah.
Memasukkan
1 array elemen (N * 2) di mana N * 2 ditentukan pada baris pertama.
Elemen-elemen array di baris berikut.
Keluaran
2 array elemen N masing-masing sedemikian rupa sehingga:
Perbedaan (Jumlah elemen array 1) dan (Jumlah elemen array 2) sedekat mungkin dengan 0.
Contoh
Memasukkan
4
1 2 3 4
Keluaran
1 4
2 3
diff=0
Penafian : Saya tidak punya dua istri. Tetapi ketika saya merasa buruk, saya membayangkan memiliki dua istri. Dan tiba-tiba, saya bersyukur dan senang bahwa saya hanya punya satu. : D
sumber
1 1 1 1 1 5
jawaban yang benar adalah1 1 1
|1 1 5
, sementara1 1 1 1 1
|5
akan lebih masuk akal.Jawaban:
Jawa
Mencoba memecahkan masalah ini dalam dua fase:
Masukan seperti
sudah diselesaikan setelah fase 1 sebagai contoh
dan masukan suka
akan membutuhkan kedua fase sehingga
(setelah fase satu) menjadi hasil dari
Meskipun saya dapat menjamin upaya ini akan selalu memberikan solusi, saya tidak dapat membuktikan bahwa solusi optimal ditemukan dalam semua kasus. Dengan pembatasan daftar ukuran yang sama itu terasa cukup realistis bahwa tidak ada kasus sudut tertinggal. Buktikan bahwa aku salah ;-)
Program di ideone.com
sumber
Brachylog 2
Cobalah online!
Ini adalah kontes popularitas, tetapi itu tidak selalu berarti bahwa bahasa golf tidak cocok. (Sungguh, saya seharusnya menjawab di Jelly karena jawaban Jelly cenderung mendapatkan jumlah upvotes yang tidak proporsional untuk beberapa alasan terlepas dari siapa yang mengirimkannya atau seberapa pegolf mereka, tetapi Brachylog lebih mudah dibaca.)
Kami memulai dengan mengambil daftar semua permutasi dari input (
pᶠ
), dan membelah masing-masing (ᵐ
) menjadi dua bagian yang sama (ḍ
; kami bisa memberikannya subskrip jika Anda memiliki lebih dari dua istri karena suatu alasan). Kemudian kami memesan permutasi split ({…}ᵒ
) dengan mengambil jumlah (+
) dari masing-masing (ᵐ
) setengah, mengambil perbedaan absolut (yaituo-
, "memerintahkan perbedaan"), dan menggunakan perbedaan tersebut untuk menentukan urutan pengurutan. Hasil terbaik adalah yang pertama, jadi kami mengambil kepala daftar denganh
untuk mendapatkan hasilnya.sumber
Mathematica
Formulir input
String input harus diambil melalui STDIN.
assets
mengacu pada jumlah yang akan didistribusikan di antara para istri (atau kembar).length
adalah jumlah aset.Untuk tujuan saat ini kami akan mengasumsikan bahwa aset terdiri dari bilangan bulat dari 1 hingga 20.
Pengolahan
Apakah distribusinya tidak adil? Jadi, pilih yang lain.
@The Constructor mencatat bahwa istri 2 dapat menentang fakta bahwa istri 1 mendapatkan semua aset terbaik. Jadi yang berikut ini menghasilkan semua saham "adil" (perbedaan = perbedaan terendah) untuk istri 1; istri 2 mendapatkan aset yang tersisa; nol mengacu pada perbedaan aset untuk para istri. Ada 5448 cara untuk mendistribusikan aset berbobot 1 hingga 20. Hanya beberapa baris yang ditampilkan.
Formatnya adalah
Pengajuan sebelumnya dapat ditemukan di antara suntingan. Itu jauh lebih tidak efisien, bergantung seperti yang dilakukannya
Permutations
.sumber
J
Ada lembar contekan semua primitif J di tautan ini , jika Anda ingin mengikuti di rumah. Ingat: J umumnya dibaca dari kanan ke kiri, jadi itu
3*2+1
adalah 7, bukan 9. Setiap kata kerja (J untuk fungsi) adalah monadik, jadi di depan sukaf y
, atau diad, jadi di antara sukax f y
.Catatan dan penjelasan:
u/
berarti "lipatu
", jadi lakukan operasi biner di atas setiap elemen dalam daftar. Jadi misalnya:+/
berarti Lipat Plus , atau Jumlah ;<.
adalah Lesser Of , jadi<./
berarti Fold Lesser Of , atau Minimum .u"1
berarti "tampilu
di sel 1 dimensi", yaitu di atas setiap baris. Biasanya kata kerja dalam J adalah atom, atau berlaku untuk seluruh argumen. Ini berlaku untuk kedua argumen jika kata kerjanya digunakan secara dua arah (dengan dua argumen). Pertimbangkan yang berikut ini:#:
adalah kata kerja yang memperluas angka ke representasi binernya. Ketika Anda menggunakannya pada daftar dengan lebih dari satu elemen, itu juga akan menyelaraskan semua angka dengan benar, sehingga Anda#:i.2^n
akan mendapatkan setiap string panjang binern
./.
, bila digunakan secara dua arah, disebut Kunci . Menggunakan elemen daftar di sisi kiri sebagai kunci, dan yang di sisi kanan sebagai nilai. Ini mengelompokkan setiap set nilai yang berbagi kunci, dan kemudian melakukan beberapa operasi pada mereka.Dalam kasus
]/.
, operasi hanyalah kata kerja identitas, jadi tidak ada yang sama sekali istimewa yang terjadi di sana, tetapi fakta bahwa/.
akan membagi daftar bagi kita adalah bagian yang penting. Inilah sebabnya kami membuat daftar biner: sehingga untuk setiap daftar ("1
), kami dapat membagi hadiah untuk para istri dengan semua cara yang memungkinkan.1!:1]1
dan1!:2&2
merupakan operasi read-in dan write-out. Bagian1!:n
adalah kata kerja dan nomor lainnya adalah pegangan file.1
adalah konsol masuk,2
konsol keluar, dan3 4 5
stdin, stdout, dan stderr. Kami juga menggunakan".
saat membaca sehingga kami mengubah string input menjadi angka.sumber
Clojure
Uji
sumber
[1 4 5 6 7 8]
program Anda dihitung di[8 5 4]
[7 6 1]
Diff 3
mana solusi jelas dengan perbedaan 1 ada.MATLAB
Inilah solusi saya:
Sebagai contoh, daftar sekarang dalam kode sumber saya menghasilkan:
yang keduanya 16.
Jika saya golf kode saya, yang kurang menyenangkan saya mendapatkan karakter yang sangat tidak dioptimalkan. Kalahkan itu ;)
sumber
PHP
Peringatan: Kode sangat kotor
Ia mencoba setiap kemungkinan permutasi dari input array.
Sampel ideone untuk
4/1 2 3 4
: http://ideone.com/gIi174sumber
Python:
atau sedikit golf:
Atau bahkan lebih jauh golf, karena setengah dari garis-garis hanya makeup. (dengan asumsi saya bisa membuang array internal yang mentah, karena ini tidak ditentukan dalam op) Anda dapat meninggalkan
print
in (misalnya) shell interaktif, dan menambahkan[::-1]
(pada akhir, setelah[0]
) jika Anda benar-benar ingin diff terakhir.(hasil dalam
(0, ((1, 2, 7, 8), (3, 4, 5, 6)))
)Namun, ini hanya memaksa semua kombinasi yang memungkinkan, dan tidak boleh dianggap efisien dari jarak jauh. Namun, jika daftar yang panjangnya sama tidak masalah, ini juga akan berfungsi (pada array besar):
Dengan kode di bawah ini misalnya, ini berjalan dengan sedikit perbedaan: 500k pada 10 ^ 10 nilai maks tidak banyak, jadi bisa dikatakan. Ini juga jauh lebih cepat: di mana kode lain mungkin tidak akan selesai dalam waktu kurang dari setahun (dan itu sangat optimis), ini berjalan sekitar setengah detik, meskipun jarak tempuh Anda mungkin berbeda.
sumber
Paham Haskell
Saya menggunakan daftar monad untuk membaginya.
Lalu kami membuat penilai.
Dan kemudian fungsi yang akan meminimalkan perbedaan.
Dan sesuatu yang menggabungkan semuanya.
Selanjutnya parser.
Dan formatter output.
Dan sekarang programnya
Contoh:
sumber