Pertimbangkan A
panjang array n
. Array hanya berisi bilangan bulat positif. Sebagai contoh A = (1,1,2,2)
. Mari kita definisikan f(A)
sebagai himpunan jumlah semua sub-susunan berdekatan yang tidak kosong dari A
. Dalam hal ini f(A) = {1,2,3,4,5,6}
. Langkah-langkah untuk menghasilkan f(A)
adalah sebagai berikut:
Subarrays dari A
adalah (1), (1), (2), (2), (1,1), (1,2), (2,2), (1,1,2), (1,2,2), (1,1,2,2)
. Jumlah masing-masing adalah 1,1,2,2,2,3,4,4,5,6
. Oleh karena itu, set yang Anda dapatkan dari daftar ini {1,2,3,4,5,6}
.
Tugas
Diberikan satu set jumlah yang S
diberikan dalam urutan yang diurutkan yang hanya berisi bilangan bulat positif dan panjang array n
, tugas Anda adalah menghasilkan setidaknya satu array X
sedemikian rupa f(X) = S
.
Misalnya, jika S = {1,2,3,5,6}
dan n = 3
kemudian output yang valid adalah X = (1,2,3)
.
Jika tidak ada array seperti itu, X
kode Anda harus menampilkan nilai konstan apa pun.
Contohnya
Input:, n=4, S = (1, 3, 4, 5, 6, 8, 9, 10, 13)
kemungkinan keluaran:X = (3, 5, 1, 4)
Input:, n=6, S = (2, 3, 4, 5, 7, 8, 9, 10, 12, 14, 17, 22)
kemungkinan keluaran:X = (5, 3, 2, 2, 5, 5)
Input:, n=6, S = (2, 4, 6, 8, 10, 12, 16)
kemungkinan keluaran:X = (4, 2, 2, 2, 2, 4)
Input:, n=6, S = (1, 2, 3, 4, 6, 7, 8, 10, 14)
kemungkinan keluaran:X = (4, 2, 1, 1, 2, 4)
Input: n=10, S = (1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 14, 15, 16, 17, 18, 19, 20, 23, 24, 25)
, mungkin keluaran: X = (1, 1, 3, 1, 2, 1, 2, 5, 4, 5)
.
Input: n=15, S = (1, 2, 3, 4, 6, 7, 8, 9, 10, 11, 13, 14, 15, 16, 17, 18, 20, 21, 22, 23, 24, 25, 26, 27, 28, 30, 31)
, mungkin keluaran: X = (1, 2, 1, 3, 3, 1, 3, 3, 1, 3, 3, 1, 2, 1, 3)
.
Format input dan output
Kode Anda dapat mengambil input dan memberikan output dalam format yang mudah dibaca yang menurut Anda nyaman. Namun, tolong tunjukkan hasil pengujian pada contoh-contoh dalam pertanyaan.
Durasi
Anda harus dapat menjalankan kode hingga selesai untuk semua contoh dalam pertanyaan. Pada prinsipnya harus benar n
hingga 15
tetapi Anda tidak perlu membuktikannya akan cukup cepat untuk semua input.
Jawaban:
Sekam , 20 byte
Cobalah online!
Mengembalikan satu solusi, atau daftar kosong jika tidak ada. Kasing uji terakhir (
n=15
) selesai dalam 3,8 detik pada TIO.Penjelasan
Program ini memiliki dua bagian. Pada bagian pertama (
¡
dan di sebelah kanannya), kita membangun daftar tak hingga yangk
elemen ke-nya adalah daftar yang berisi semuak
daftar panjang yang jumlah irisannyaS
. Kami melakukan ini secara induktif, mulai dari irisan 1-elemenS
, dan pada setiap langkah, menambahkan setiap elemenS
ke setiap daftar, dan menjaga mereka yang memiliki jumlah awalanS
. Di bagian kedua (!
dan di sebelah kiri), kita mengambiln
elemen ke-10 dari daftar, yang berisin
daftar panjang. Dari jumlah tersebut, kami memilih yang pertama yang jumlah irisannya sebenarnya mengandung setiap elemenS
.Dalam kode, pertama mari kita ganti
o
danȯ
(yang menyusun dua dan tiga fungsi menjadi satu) dengan tanda kurung untuk kejelasan.Ada beberapa bagian yang perlu penjelasan lebih lanjut. Dalam program ini, superskrip
⁰¹
keduanya merujuk pada argumen pertamaS
. Namun, jikaα
ada fungsi, makaα¹
berarti "berlakuα
untukS
", sementara⁰α
berarti "tancapkanS
ke argumen keduaα
". Fungsi¦
memeriksa apakah argumen pertama berisi semua elemen yang kedua (menghitung multiplisitas), jadiS
harus argumen kedua.Pada bagian pertama, fungsi yang
¡
menggunakan dapat diartikan sebagaiS(f~Λ€∫)(×:)¹
. CombinatorS
berperilaku sepertiSαβγ -> (αγ)(βγ)
, yang berarti bahwa kita dapat menyederhanakannya(f~Λ€∫¹)(×:¹)
. Bagian kedua×:¹
,, adalah "mix withS
by prepending", dan hasilnya diteruskan ke bagian pertama. Bagian pertamaf~Λ€∫¹
,, berfungsi seperti ini. Fungsi inif
memfilter daftar berdasarkan suatu kondisi, yang dalam hal ini adalah~Λ€∫¹
. Ia menerima daftar daftarL
, jadi kami punya~Λ€∫¹L
. Combinator~
berperilaku seperti~αβγδε -> α(βδ)(γε)
: argumen pertama diteruskan keβ
, yang kedua keγ
, dan hasilnya digabungkan denganα
. Ini artinya sudah kita milikiΛ(€¹)(∫L)
. Bagian terakhir∫L
hanyalah jumlah kumulatif dariL
,€¹
adalah fungsi yang memeriksa keanggotaanS
, danΛ
mengambil kondisi (di sini€¹
) dan daftar (di sini∫L
), dan memeriksa apakah semua elemen memuaskannya. Sederhananya, kami memfilter hasil pencampuran dengan apakah jumlah kumulatifnya semuanyaS
.sumber
Ruby , 135 byte
Cobalah online!
Gunakan pencarian pertama yang luasnya. n = 10 bekerja pada TIO, n = 15 membutuhkan waktu lebih dari satu menit, tetapi bekerja pada mesin saya.
Ruby , 147 byte
Cobalah online!
Versi yang dioptimalkan, bekerja pada TIO selama n = 15 (~ 20 dtk)
Sebenarnya, ini adalah awal dari pendekatan non-brute-force. Saya harap seseorang akan mengerjakannya dan menemukan solusi lengkap.
Ide pertama:
Yang membawa kami ke pengoptimalan berikutnya:
Ruby , 175 byte
Cobalah online!
~ 8,5 detik pada TIO. Tidak buruk...
... dan seterusnya (akan diterapkan)
sumber
Haskell,
117111 byte6 byte disimpan berkat @nimi!
Cobalah online!
f
r
i
n
s
Kapan
n
nol (diangkut ken<1
) daftar harus siap, jadi kami memeriksa apakah semua nilai telah terlihat. Jika tidak, kami mengembalikan daftar kosong untuk menunjukkan tidak ada solusi, kalau tidak kami mengembalikan daftar tunggal yang berisi daftar kosong, di mana elemen yang dipilih akan ditambahkan. Kasus ini juga bisa ditangani dengan persamaan tambahanJika
n
tidak nol, kami kembaliIni adalah daftar (1) daftar dari mana elemen pertama (2) berasal
s
dan sisanya (5) berasal dari panggilan rekursif, dalam kondisi (4) di mana semua jumlah baru beradas
. Jumlah baru dihitung dalam (3) - catatan yangt
diambil dari daftar tunggal, peretasan golf jelek untuk apa yang akan Haskell idiomatiklet t=y:map(y+)i
. Panggilan rekursif (5) menjadi seperti barur
mengatur yang lama tanpa elemen-elemen yang muncul di antara jumlah barut
.Fungsi utama
&
memanggil fungsi helper dengan mengatakan bahwa kita masih harus melihat semua nilai (r=s
) dan belum ada jumlah (i=[]
).Untuk tujuh byte lebih, kita dapat membatasi perhitungan hanya memberikan hasil pertama (jika ada), yang jauh lebih cepat dan menangani semua kasus uji dalam waktu kurang dari 2 detik.
Cobalah online! (ini adalah variasi hanya hasil pertama dari versi lama)
sumber
map
, saya hanya mencoba<$>
tetapi itu membutuhkan parens ekstra ... @Anush Saya tidak tahu solusi waktu polinomialBersih , 177 byte
Cobalah online!
Memakan waktu sekitar 40 detik pada mesin saya untuk
n=15
test case, tetapi waktu habis pada TIO.Bersih , 297 byte
Cobalah online!
Yang ini mencakup beberapa optimasi yang dibuat oleh GB dan juga beberapa dari saya. Saya pikir beberapa dari mereka dapat dibuat lebih umum, jadi saya akan menambahkan penjelasan setelah selesai.
Butuh sekitar 10 detik di mesin saya, 40 detik di TIO.
sumber
@mention
Anda besok ketika mereka sudah habis, sayangnya tidak punya waktu hari ini.Python 3 , 177 byte
Cobalah online!
(beberapa baris baru / spasi ditambahkan untuk menghindari pembaca harus menggulir kode)
Port langsung jawaban Jelly saya (dengan beberapa modifikasi, lihat bagian "catatan" di bawah)
Hasil penelusuran lokal:
Saya dengar itu
itertools
verbose, tetapicombinations
implementasi terbaik saya bahkan lebih verbose:Catatan .
a[p//n:p%n+1]
membutuhkan waktu sekitar 2x lebih lama, tetapi menghemat beberapa byte.combinations
mengembalikan iterator, ini lebih ramah-memori.sumber
Jelly , 35 byte
Cobalah online!
Jalankan secara lokal: (n = 15 membutuhkan lebih dari 1 GB RAM)
(sebenarnya saya menjalankan versi UTF8-encoded, yang membutuhkan lebih dari 35 byte, tetapi hasilnya tetap sama)
Solusi ini menggunakan korsleting untuk mengurangi run-time.
Penjelasan
Kami mencatat bahwa jumlah semua awalan tidak kosong hadir dalam input, dan jumlahnya meningkat secara ketat. Kita juga dapat mengasumsikan bahwa elemen terbesar dan terbesar kedua adalah jumlah awalan.
Belum diuji (tetapi harus memiliki kinerja yang identik)
Jelly , 32 byte
Cobalah online!
Versi yang lebih tidak efisien (tanpa korsleting):
Jelly , 27 byte
Cobalah online!
Untuk tes n = 15, dibutuhkan hingga 2GB RAM dan tidak berakhir setelah ~ 37 menit.
catatan :
Ẇ§
dapat diganti denganÄÐƤẎ
. Mungkin lebih efisien.sumber
APL (NARS), karakter 758, byte 1516
Fungsi G dalam G x (dengan bantuan fungsi H) akan menemukan semua permutasi x. Fungsi d dalam xdy mencari apakah array y menghasilkan mengikuti array latihan x mengembalikan nilai Boolean. Fungsi F dalam x F y akan mengembalikan array r dengan panjang x, sedemikian sehingga ydr benar (= 1) Sedikit lama implementasi, tetapi inilah yang menghitung semua kasus dalam pengujian lebih sedikit waktu ... Kasus terakhir untuk n = 15 hanya berjalan 20 detik saja ... saya harus mengatakan ini tidak menemukan banyak solusi, kembalikan hanya satu solusi (akhirnya sepertinya begitu) dalam waktu yang lebih singkat (tidak dieksplorasi tes untuk input yang berbeda ...) 16 + 39 + 42 + 8 + 11 + 11 + 18 + 24 + 24 + 54 + 11 + 12 + 7 + 45 + 79 + 69 + 12 + 38 + 26 + 72 + 79 + 27 + 15 + 6 + 13 (758)
sumber