Ini adalah tindak lanjut ke Count array yang membuat set unik . Perbedaan yang signifikan adalah definisi keunikan.
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 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
. Karenanya, set yang Anda dapatkan dari daftar ini {1,2,3,4,5,6}
.
Kami memanggil array A
unik jika tidak ada array lain B
dengan panjang yang sama sehingga f(A) = f(B)
, kecuali untuk array A
terbalik. Sebagai contoh, f((1,2,3)) = f((3,2,1)) = {1,2,3,5,6}
tetapi tidak ada array panjang 3
yang menghasilkan jumlah penjumlahan yang sama.
Tugas
Tugas, untuk yang diberikan n
dan s
untuk menghitung jumlah array unik dengan panjang itu. Anda dapat berasumsi bahwa itu s
adalah antara 1
dan 9
. Anda hanya perlu menghitung array di mana elemen-elemennya adalah bilangan bulat yang diberikan s
atau s+1
. Misal jika s=1
array yang Anda hitung hanya berisi 1
dan 2
. Namun, definisi keunikan adalah sehubungan dengan array lain dengan panjang yang sama. Sebagai contoh konkret [1, 2, 2, 2]
adalah tidak unik karena memberikan set yang sama jumlah sebagai [1, 1, 2, 3]
.
Anda harus menghitung kebalikan dari array serta array itu sendiri (selama array bukan palindrome tentu saja).
Contohnya
s = 1
, jawaban untuk n = 2,3,4,5,6,7,8,9 adalah:
4, 3, 3, 4, 4, 5, 5, 6
Sebab s = 1
, susunan unik panjang 4 adalah
(1, 1, 1, 1)
(2, 1, 1, 2)
(2, 2, 2, 2)
s = 2
, jawaban untuk n = 2,3,4,5,6,7,8,9 adalah:
4, 8, 16, 32, 46, 69, 121, 177
Contoh array yang tidak unik s = 2
adalah:
(3, 2, 2, 3, 3, 3).
Ini memiliki jumlah penjumlahan yang sama dengan: (3, 2, 2, 2, 4, 3)
dan (3, 2, 2, 4, 2, 3)
.
s = 8
, jawaban untuk n = 2,3,4,5,6,7,8,9 adalah:
4, 8, 16, 32, 64, 120, 244, 472
Skor
Untuk yang diberikan n
, kode Anda harus menampilkan jawaban untuk semua nilai s
mulai dari 1
hingga 9
. Skor Anda adalah nilai tertinggi n
yang menyelesaikannya dalam satu menit.
Pengujian
Saya perlu menjalankan kode Anda di mesin ubuntu saya, jadi harap sertakan instruksi sedetail mungkin untuk cara mengkompilasi dan menjalankan kode Anda.
Papan peringkat
- n = 13 oleh Christian Sievers di Haskell (42 detik)
sumber
s
? Apa yang diwakilinya?Jawaban:
Haskell
The
orig
Fungsi menciptakan semua daftar panjangn
dengan entris
ataus+1
, membuat mereka jika mereka datang sebelum terbalik mereka, menghitung sublist merekasums
dan menempatkan mereka di peta yang juga ingat elemen pertama dari daftar. Ketika set jumlah yang sama ditemukan lebih dari sekali, elemen pertama digantiNothing
, jadi kita tahu kita tidak perlu mencari cara lain untuk mendapatkan jumlah ini.The
construct
pencarian fungsi untuk daftar yang diberikan panjang dan diberi nilai awal yang memiliki himpunan jumlah sublist. Bagian rekursifnyaconstr
pada dasarnya mengikuti logika yang sama dengan ini , tetapi memiliki argumen tambahan yang memberikan jumlah yang harus dimiliki oleh entri daftar. Ini memungkinkan untuk berhenti lebih awal ketika nilai sekecil mungkin terlalu besar untuk mendapatkan jumlah ini, yang memberikan peningkatan kinerja besar-besaran. Peningkatan besar lebih lanjut diperoleh dengan memindahkan tes ini ke tempat sebelumnya (versi 2) dan dengan mengganti daftar jumlah saat ini dengan aVector
(versi 3 (rusak) dan 4 (dengan keketatan tambahan)). Versi terbaru melakukan tes keanggotaan dengan tabel pencarian dan menambahkan beberapa kekakuan dan paralelisasi.Ketika
construct
telah menemukan daftar yang memberikan jumlah sublist dan lebih kecil dari kebalikannya, ia dapat mengembalikannya, tetapi kami tidak benar-benar tertarik padanya. Hampir akan cukup untuk hanya kembali()
untuk menunjukkan keberadaannya, tetapi kita perlu tahu apakah kita harus menghitungnya dua kali (karena itu bukan palindrom dan kita tidak akan pernah menangani kebalikannya). Jadi kami menempatkan 1 atau 2 sebagaiweight
daftar hasil.Fungsi
count
menyatukan bagian-bagian ini. Untuk setiap set jumlah sublist (berasal dariorig
) yang unik di antara daftar yang hanya berisis
dans+1
, ia memanggilvalue
, yang memanggilconstruct
dan, melaluiuniqueval
, memeriksa apakah hanya ada satu hasil. Jika demikian, itu adalah berat yang harus kita hitung, jika tidak jumlah himpunan tidak unik dan nol dikembalikan. Perhatikan bahwa karena malas,construct
akan berhenti ketika sudah menemukan dua hasil.The
main
Fungsi menangani IO dan loop daris
dari 1 sampai 9.Kompilasi dan Lari
Pada debian ini membutuhkan paket
ghc
,libghc-vector-dev
danlibghc-parallel-dev
. Simpan program dalam fileprog.hs
dan kompilasi denganghc -threaded -feager-blackholing -O2 -o prog prog.hs
. Jalankan dengan di./prog <n> +RTS -N
mana<n>
panjang array yang ingin kita hitung array unik.sumber