Dalam tantangan ini, Anda perlu mempartisi daftar, di mana partisi memiliki ukuran maks, ukuran min, dan ukuran yang disukai. Saya akan menggunakan notasi (min,pref,max) untuk menunjukkan ukuran dalam tantangan ini.

Bagi mereka yang tidak terbiasa dengan partisi, daftar berikut telah dipartisi menjadi bagian dari 3:
[0..9] -> [[0,1,2],[3,4,5],[6,7,8]]

Ketika daftar ini tidak merata dibagi, Anda perlu partisi untuk menjadi seperti dekat dengan ukuran yang diinginkan mungkin: [0..10], (2,4,5) -> [[0,1,2,3],[4,5,6],[7,8,9]]. Partisi ini lebih disukai daripada [[0,1,2,3],[4,5,6,7],[8,9]], meskipun yang terakhir memiliki lebih dari panjang yang disukai. Secara formal, kita perlu meminimalkan jumlah (partitionLength-preferredSize)^2untuk setiap partisi.

Urutan panjang partisi tidak masalah: Untuk [0..5], (2,3,3), baik [[0,1,2],[3,4]]atau [[0,1],[2,3,4]]berfungsi. Jika tidak ada partisi mungkin, mengembalikan array kosong: [0..7], (4,4,5) -> [].

Anda dapat mengasumsikan itu 1<=min<=pref<=max, dan bahwa array yang dikirimkan kepada Anda adalah array integer yang tidak kosong. Array akan selalu menjadi argumen pertama. Anda dapat menerima min, maks, dan pref dalam urutan apa pun dan sebagai tuple atau sebagai argumen terpisah.

Program Anda harus berjalan dalam beberapa detik. Pada dasarnya, iterasi melalui setiap kemungkinan ukuran partisi dalam batas tidak diperbolehkan.

Kasus uji:

[1], (1,3,4)         -> [[1]]
[100], (1,2,3)       -> [[100]]
[1,2], (1,1,2)       -> [[1],[2]]
[1,2], (1,2,2)       -> [[1,2]]
[1,2], (1,3,3)       -> [[1,2]]
[1,2,3], (1,2,3)     -> [[1,2],[3]] or [[1,2,3]]
[1,2,3,4], (1,3,4)   -> [[1,2,3,4]]
[1,2,3,4,5], (3,3,4) -> []
[1,2,3,4,5], (2,2,2) -> []
[1,2,3,4,5], (3,3,5) -> [[1,2,3,4,5]]
[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49], (2,6,6) -> [[1,2,3,4,5,6],[7,8,9,10,11,12],[13,14,15,16,17,18],[19,20,21,22,23,24],[25,26,27,28,29],[30,31,32,33,34],[35,36,37,38,39],[40,41,42,43,44],[45,46,47,48,49]]

Ini adalah kode-golf , jadi bidik sesedikit mungkin byte dalam bahasa favorit Anda!

Haskell, 152

_%0=[]
s%k|(a,b)<-splitAt(div(z s)k)s=a:b%(k-1)
z=length
f s n p x=snd$minimum$(z s*p^2,[]):[(sum[(z x-p)^2|x<-s%k],s%k)|k<-[-div(-z s)x..div(z s)n]]

Di setiap partisi, jika ada dua daftar yang memiliki panjang yang berbeda dua atau lebih, akan selalu bermanfaat untuk menyusutkan daftar yang lebih besar dan memperbesar daftar yang lebih kecil. oleh karena itu, kita hanya perlu mempertimbangkan partisi dengan hanya dua ukuran daftar, yang menyederhanakan perhitungan.

program kemudian berjalan pada semua jumlah daftar yang mungkin ada di partisi. mengingat jumlah daftar di partisi, skor ditentukan secara unik. program menghitung partisi yang pas, dan nilainya.

kemudian ia menemukan minimum keseluruhan, dan mengembalikannya.

Penggunaan: input like f [1,2,3,4,5] 1 3 4( fadalah fungsi yang memecahkan tantangan)

Meskipun dimungkinkan untuk menghitung opsi terbaik secara numerik dan hanya kemudian mempartisi daftar sesuai, butuh terlalu banyak byte. namun, versi terakhir dari pendekatan ini adalah:

_%0=[]
s%k|(a,b)<-splitAt(div(length s)k)s=a:b%(k-1)
f s n p x|l<-length s=(s%)$snd$minimum$(l*p^2,0):[(k*j^2+mod l k*(1-2*j),k)|k<-[1..div l n],k*x>=l,j<-[p-div l k]]

CJam, 70

q~:S;_,[0L]a{_S2=e<),S0=>f{[__S1=-_*\]@@-j.+}[esL]a+:e<}j1={/(\e_}/;]p

Cobalah online

Kode menemukan urutan optimal ukuran partisi berdasarkan ukuran daftar, menggunakan pemrograman dinamis (melalui rekursi memoized), kemudian melanjutkan dan mempartisi daftar.