Pertanyaan ini memiliki susunan yang mirip dengan Find a array yang sesuai dengan jumlah penjumlahan meskipun sangat berbeda dalam tujuannya.
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
. 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.
Kami hanya akan mempertimbangkan array di mana elemen-elemennya adalah bilangan bulat yang diberikan s
atau s+1
. Misal jika s=1
array hanya berisi 1
dan 2
.
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 seharusnya tidak menghitung kebalikan dari array serta array itu sendiri.
Contohnya
s = 1
, jawabannya selalu n+1
.
s = 2
, jawaban yang dihitung dari n = 1
atas adalah:
2,3,6,10,20,32,52,86
s = 8
, jawaban yang dihitung dari n = 1
atas adalah:
2,3,6,10,20,36,68,130
Skor
Untuk 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 = 24 oleh Anders Kaseorg di Rust (34 detik)
- n = 16 oleh Ourous in Clean (36 detik)
- n = 14 oleh JRowan dalam Common Lisp (49 detik)
sumber
Jawaban:
Karat , n ≈ 24
Membutuhkan Karat malam hari untuk
reverse_bits
fitur yang nyaman . Kompilasi denganrustc -O unique.rs
dan jalankan dengan (misalnya)./unique 24
.sumber
s
dans+1
di dalamnya?s
dans + 1
(karena Anda mengatakan itu adalah satu-satunya array yang akan kita pertimbangkan), meskipun tidak segera jelas apakah itu akan membuat perbedaan.Lisp umum SBCL, N = 14
fungsi panggilan (goahead ns)
di sini adalah waktu menjalankan
sumber
sbcl
entah bagaimana?Bersih
Tentu saja bukan pendekatan yang paling efisien, tapi saya tertarik melihat seberapa baik filter nilai-naif tidak.
Yang mengatakan, masih ada sedikit perbaikan yang harus dilakukan menggunakan metode ini.
Tempatkan dalam file bernama
main.icl
, atau ubah baris teratas menjadimodule <your_file_name_here>
.Kompilasi dengan
clm -h 1500m -s 50m -fusion -t -IL Dynamics -IL StdEnv -IL Platform main
.Anda bisa mendapatkan versi TIO (dan saya sendiri) gunakan dari tautan di tajuk, atau yang lebih baru dari sini .
sumber
s
? Dalam pertanyaan Anda menyatakan " Untuk n yang diberikan , kode Anda harus menampilkan jawaban untuk semua nilai s dari 1 hingga 9."