Spesifikasi
Tantangan ini sederhana untuk dinyatakan: input Anda adalah array non-kosong dari integer non-negatif, dan tugas Anda adalah mempartisi menjadi sesedikit mungkin peningkatan berikutnya. Lebih formal lagi, jika array input adalah A
, maka output adalah array array B
sehingga:
- Setiap array dalam
B
bentuk partisiA
menjadi disjoint (tidak harus berdekatan). Secara induktif, ini berarti bahwa baikB
array singleton yang mengandungA
, atau elemen pertamaB
adalahA
urutan dan sisanya membentuk partisiA
dengan urutan berikutnya dihapus. - Setiap array dalam
B
(tidak harus sepenuhnya) meningkat. - Jumlah array di
B
minimal.
Baik input dan output dapat diambil dalam format array asli bahasa Anda. Perhatikan bahwa mungkin ada beberapa output yang benar.
Contoh
Pertimbangkan array input A = [1,2,1,2,5,4,7,1]
. Satu kemungkinan keluaran adalah B = [[1],[1,2,4,7],[1,2,5]]
. Kondisi partisi terbukti dari diagram ini:
A 1 2 1 2 5 4 7 1
B[0] 1
B[1] 1 2 4 7
B[2] 1 2 5
Juga, setiap array B
meningkat. Akhirnya, A
tidak dapat dibagi menjadi dua urutan yang meningkat, jadi panjangnya B
juga minimal. Jadi ini adalah output yang valid.
Aturan dan penilaian
Anda dapat menulis fungsi atau program lengkap. Hitungan byte terendah menang, dan celah standar tidak diizinkan. Tidak ada batasan waktu, tetapi Anda harus mengevakuasi solusi Anda pada semua kasus uji sebelum mengirimkannya.
Uji kasus
Hanya satu output yang mungkin ditampilkan, tetapi mungkin ada beberapa opsi yang valid. Secara khusus, urutan array dalam hasil tidak masalah (tetapi masing-masing array harus dalam urutan yang meningkat).
[0] -> [[0]]
[3,5,8] -> [[3,5,8]]
[2,2,2,2] -> [[2,2,2,2]]
[1154,1012,976,845] -> [[845],[976],[1012],[1154]]
[6,32,1,2,34,8] -> [[1,2,8],[6,32,34]]
[1,12,1,12,1,13] -> [[1,1,1,13],[12,12]]
[6,4,6,13,18,0,3] -> [[0,3],[4,6,13,18],[6]]
[1,2,3,2,3,4,7,1] -> [[1,1],[2,2,3,4,7],[3]]
[0,9,2,7,4,5,6,3,8] -> [[0,2,3,8],[4,5,6],[7],[9]]
[7,1,17,15,17,2,15,1,6] -> [[1,1,6],[2,15],[7,15,17],[17]]
[4,12,2,10,15,2,2,19,16,12] -> [[2,2,2,12],[4,10,15,16],[12,19]]
[10,13,9,2,11,1,10,17,19,1] -> [[1,1],[2,10,17,19],[9,11],[10,13]]
[3,7,3,8,14,16,19,15,16,2] -> [[2],[3,3,8,14,15,16],[7,16,19]]
[15,5,13,13,15,9,4,2,2,17] -> [[2,2,17],[4],[5,9],[13,13,15],[15]]
[0,5,2,0] -> [[0,5],[0,2]]
(yaitu, mendaur ulang nol pertama alih-alih menggunakan masing-masing satu kali). Apakah itu disengaja?B
, semoga sekarang lebih jelas.Jawaban:
Haskell, 54 byte
Contoh penggunaan:
foldr(#)[] [4,12,2,10,15,2,2,19,16,12]
->[[2,2,2,12],[4,10,15,16],[12,19]]
Cara kerjanya: buka daftar input mulai dari ujung kanan. Membangun daftar keluaran (daftar) dengan mengawali elemen saat
n
untuk sublist pertamal
di manan
kurang atau sama dengan kepalal
. Jika tidak ada, buat daftar singleton barun
di akhir daftar output.sumber
Pyth, 20 byte
Cobalah online: Demonstrasi atau Test Suite
Pendekatan serakah. Saya membuat
len(input)
daftar kosong. Kemudian saya mengulangi setiap nomor dalam daftarinput
pilih yang pertama, yang masih diurutkan setelah menambahkan nomor.Penjelasan:
sumber