Kami mendefinisikan sebagai daftar kekuatan yang berbeda yang menjumlahkan . Misalnya, .
Berdasarkan konvensi, kekuatan diurutkan di sini dari tertinggi ke terendah. Tapi itu tidak mempengaruhi logika tantangan, maupun solusi yang diharapkan.
Tugas
Diberikan semiprime , ganti setiap istilah dalam dengan daftar kekuatan lain yang menjumlahkan istilah ini, sedemikian rupa sehingga penyatuan semua sub-daftar yang dihasilkan adalah sampul yang tepat dari matriks didefinisikan sebagai:
dimana dan adalah faktor prima dari .
Ini jauh lebih mudah dipahami dengan beberapa contoh.
Contoh 1
Untuk , kami memiliki:
- dan V ( P ) = [ 4 , 2 , 1 ]
- dan V ( Q ) = [ 2 , 1
Untuk mengubah menjadi penutup M yang tepat , kita dapat membagi 16 menjadi 8 + 4 + 4 dan 4 menjadi 2 + 2 , sementara 1 dibiarkan tidak berubah. Jadi output yang mungkin adalah:
Output lain yang valid adalah:
Contoh # 2
Untuk , kami memiliki:
- dan V ( P ) = [ 32 , 4 , 1 ]
- dan V ( Q ) = [ 16 , 4 , 2 , 1 ]
Output yang mungkin adalah:
Aturan
- Karena faktorisasi bukan bagian utama dari tantangan, Anda dapat mengambil P dan Q sebagai input.
- Ketika beberapa solusi yang mungkin ada, Anda dapat mengembalikan salah satu atau semuanya.
- Anda dapat secara bergantian mengembalikan eksponen dari kekuatan (misalnya alih-alih [ [ 8 , 4 , 4 ).
- Urutan sub-daftar tidak menjadi masalah, juga urutan persyaratan dalam setiap sub-daftar.
- Untuk beberapa semiprimes, Anda tidak perlu membagi istilah apa pun karena sudah merupakan sampul sempurna M (lihat A235040 ). Tetapi Anda masih harus mengembalikan daftar (tunggal) daftar seperti [ [ 8 ] , [ 4 ] , [ 2 untuk N = 15 .
- Ini golf kode !
Uji kasus
Input | Possible output
-------+-----------------------------------------------------------------------------
9 | [ [ 4, 2, 2 ], [ 1 ] ]
15 | [ [ 8 ], [ 4 ], [ 2 ], [ 1 ] ]
21 | [ [ 8, 4, 4 ], [ 2, 2 ], [ 1 ] ]
51 | [ [ 32 ], [ 16 ], [ 2 ], [ 1 ] ]
129 | [ [ 64, 32, 16, 8, 4, 2, 2 ], [ 1 ] ]
159 | [ [ 64, 32, 32 ], [ 16 ], [ 8 ], [ 4 ], [ 2 ], [ 1 ] ]
161 | [ [ 64, 32, 16, 16 ], [ 8, 8, 4, 4, 4, 2, 2 ], [ 1 ] ]
201 | [ [ 128 ], [ 64 ], [ 4, 2, 2 ], [ 1 ] ]
403 | [ [ 128, 64, 64 ], [ 32, 32, 16, 16, 16, 8, 8 ], [ 8, 4, 4 ], [ 2 ], [ 1 ] ]
851 | [ [ 512 ], [ 128, 64, 64 ], [ 32, 16, 16 ], [ 8, 4, 4 ], [ 2 ], [ 1 ] ]
2307 | [ [ 1024, 512, 512 ], [ 256 ], [ 2 ], [ 1 ] ]
Jawaban:
K (ngn / k) ,
6663 byteCobalah online!
menerima (P; Q) alih-alih N
algoritma:
hitung A sebagai jumlah parsial dari V (P * Q)
gandakan setiap V (P) dengan masing-masing V (Q), urutkan produk dalam urutan menurun (sebut saja R), dan hitung jumlah parsialnya B
menemukan posisi elemen-elemen di B yang juga terjadi di A; potong R tepat setelah posisi itu
sumber
Jelly , 24 byte
Tautan monadik yang menerima daftar dua bilangan bulat
[P, Q]
yang menghasilkan satu daftar daftar yang mungkin seperti yang dijelaskan dalam pertanyaan.Cobalah online!(footer mencetak representasi string untuk menampilkan daftar apa adanya)
Atau lihat test-suite (mengambil daftar N dan menyusun ulang hasil menjadi seperti yang ada di pertanyaan)
Bagaimana?
Kami selalu dapat mengiris elemen dari terendah ke atas, dengan rakus (baik ada 1 di M atau kami memiliki input 4 , ketika M = [ [ 4 ] ] ) untuk menemukan solusi.M 1 M 4 M=[[4]]
Catatan: kode mengumpulkan semua (satu!) Solusi tersebut dalam daftar dan kemudian mengambil hasil head (only) - yaitu kepala akhir diperlukan karena partisi tidak dari semua kemungkinan pemesanan.
sumber
Python 2 ,
261233232231 byteCobalah online!
1 byte dari Jo King ; dan 1 byte lagi karena Kevin Cruijssen .
Dibawa sebagai input
p,q
. Mengejar algoritma serakah.sumber
-k-1
bisa~k
.i,j
tugas bisai,j=[i+1,i,0,j+1][j+1<len(v)::2]
untuk -1 bytewhile v[j]>-m
bisawhile-m<v[j]
Jelly , 41 byte
Cobalah online!
ÇIP$Ƈ
sumber
Jelly , 34 byte
Cobalah online!
Format input:
[P, Q]
(tautan TIO di atas tidak menerima ini, melainkan nomor tunggal, untuk membantu dengan kasus uji).Format output: Daftar semua solusi (ditampilkan sebagai representasi kisi dari daftar 3D di atas TIO).
Kecepatan: Turtle.
sumber
Pyth , 27 byte
Terinspirasi oleh penghancuran Jonathan Jelly dari solusi Jelly saya . DibutuhkanN sebagai input.
Coba di sini!
sumber
Haskell,
281195 bytesumber
(==)
, menggunakan1>0
alih-alih,True
dan tidak menggunakanwhere
. Jugan'
dapat dipersingkat .. Dengan ini Anda dapat menyimpan 72 byte: Cobalah online!