(Diadaptasi dari Soal C pada kualifikasi pertama dari ACM Programming Contest 2012/2013 )
Anda memiliki beberapa array, bernama A 1 , A 2 , ..., A n , masing-masing diurutkan dalam urutan menaik. Setiap item dalam array akan menjadi bilangan bulat 32-bit.
Sebuah Sandwich adalah satu set indeks j 1 , j 2 , ..., j n sehingga A 1 [j 1 ] ≤ A 2 [j 2 ] ≤ .... ≤ A n [j n ].
A i [0] adalah elemen pertama dari A i .
Diberikan beberapa array, hasilkan setiap sandwich yang mungkin Anda dapat miliki dari array tersebut, dipisahkan oleh baris baru.
Jika ada fungsi bawaan yang melakukan ini dalam bahasa Anda, jangan gunakan itu.
Input dapat diberikan dengan cara apa pun, output harus dipisahkan dengan spasi putih, tetapi dapat diberikan dalam urutan apa pun.
Kasus cobaan:
[[1, 5, 7, 10], [2, 6, 6, 8, 12], [4, 5, 9]]
Keluaran:
0 0 0
0 0 1
0 0 2
0 1 2
0 2 2
0 3 2
1 1 2
1 2 2
1 3 2
2 3 2
Kasus cobaan:
[[10, 20, 30], [1, 2, 3]]
Keluaran:
Kode terpendek menang.
sumber
Jawaban:
APL (33)
Input dibaca dari keyboad, tetapi harus diberikan sebagai daftar APL, yaitu
Penjelasan:
B←,⍳⊃∘⍴¨A←⎕
: A adalah input yang dievaluasi, B adalah semua set indeks yang memungkinkan dalam daftar yang diberikan pada A.{(⍳⍴A)∘≡⍋⍵⌷¨A}¨B
: untuk setiap set indeks, dapatkan nilai dari daftar (⍵⌷¨A
) dan lihat apakah mereka diurutkan ((⍳⍴A)∘=⍋
)B/⍨
: pilih dari B semua set indeks di mana ekspresi sebelumnya benar (yaitu semua sandwich)1-⍨
: kurangi satu dari semua indeks, karena pertanyaan ini mengasumsikan array berbasis-0 dan array-APL adalah berbasis-1 secara default.↑
: mengatur daftar set indeks sebagai matriks (sehingga setiap set adalah pada barisnya sendiri)sumber
Mathematica
120130Edit
Versi ini bekerja dengan array ukuran yang bervariasi.
Pemakaian
Penjelasan
Menggunakan contoh pertama dari atas,
MapIndexed
menetapkan indeks untuk semua elemen. NB: Mathematica mulai menghitung dengan 1. (Kami akan mempertimbangkannya nanti.)Outer
menghasilkan semua daftar, masing-masing kandidat sebagai array sandwich, dan indeks elemen mereka;%
berisi hasil dari output sebelumnya. Angka-angka,10
dan22
yang saya sorot setelah mereka output, merujuk pada array sandwich{10,22}
yang belum diidentifikasi.Cases
menguji setiap elemen di atas untuk menentukan apakah suatu hubunganLessEqual
(kurang dari atau sama) berlaku. Hasil yang ditunjukkan di bawah ini adalah contoh di mana array sandwich terdeteksi. Sekali lagi, saya menyoroti{10,22}
dalam output.%%
mengacu pada hasil kedua dari belakang.:>
, [RuleDelayed] mengembalikan bagian-bagian dari instance yang menarik, yaitu, indeks sandwich array.-1
mengoreksi fakta bahwa Mathematica memulai array dengan 1 bukannya 0.x_ /; LessEqual @@ x [[Semua, 1]] == Benar:> x [[Semua, 2, 2]] - 1]
Grid
menampilkan hasilnya dalam kotak. Baris pertama0 1
berarti elemen 0 dari sublist pertama (yaitu 10 ) dan elemen 1 dari sublist kedua (yaitu 22 ) merupakan array sandwich pertama yang ditemukan.sumber
LessEqual
untuk bekerja dengan array dengan ukuran yang tidak ditentukan. Mungkin ada contoh lain di mana asumsi yang sama menghambat generalisasi. Ketika saya mendapat kesempatan, saya akan menggeneralisasi pendekatan.GolfScript, 51 karakter
Contoh input (pada stdin):
Contoh output (ke stdout):
(Perhatikan bahwa input harus diberikan tanpa koma, jika tidak, program kemungkinan besar akan macet.)
Saya kira saya harus menambahkan beberapa penjelasan tentang cara kerja kode ini:
~:A
hanya mengevaluasi input sebagai kode GolfScript dan menetapkan hasilnya (array array)A
. Itu juga meninggalkan salinanA
di stack untuk langkah selanjutnya.{,}%
mengganti setiap sub-array dengan panjangnya, dan{*}*
mengalikan panjangnya bersama-sama, memberikan jumlah total kandidat sandwich yang mungkin. Angka ini kemudian dikonversi oleh,
ke array yang banyak bilangan bulat berturut-turut mulai dari 0.{A{,.@.@/\@%}%\;}%
mengkonversi setiap nomor menjadi kandidat sandwich yang sesuai (yaitu array indeks yang valid ke dalam setiap sub-array diA
). Misalnya, diberi input di atas,0
akan memetakan ke[0 0 0]
,1
ke[1 0 0]
,2
ke[2 0 0]
,3
ke[3 0 0]
,4
ke[0 1 0]
dan seterusnya. (Mencari tahu persis bagaimana kode mencapai yang tersisa sebagai latihan untuk pembaca yang tertarik.){:k,,{.A=\k==}%.$=},
menyaring kandidat sandwich dengan memetakan masing-masing ke elemen yang sesuai dari sub-arrayA
(sehingga misalnya[0 0 0]
akan menghasilkan[1 2 4]
,[1 0 0]
akan menghasilkan[5 2 4]
, dan seterusnya, untuk input di atas), menyortir array yang dihasilkan dan membandingkannya dengan salinan yang tidak disortir . Jika mereka sama, array sudah diurutkan, dan dengan demikian kandidatnya memang sandwich.Akhirnya,
`
hanya mengubah array sandwich yang disaring menjadi string untuk output.sumber
R - 89 karakter
dimana
atau
sumber
Python,
149141140Python memiliki pustaka itertools yang berguna yang dapat menghasilkan permutasi. Ini hanya mengulangi semua permutasi yang mungkin dari indeks yang valid dan memeriksa apakah mereka memenuhi kriteria.
Saya pikir saya bisa membuat ini lebih pendek, masih bekerja di sana.
Sunting: Sekarang semua satu baris untuk kenyamanan membaca Anda!
sumber
r=range
akan menyimpan satu karakter.Python 120
... masih berpikir, "menghitung" adalah kata yang sangat panjang.
sumber
GolfScript (44 karakter)
Input dan output format yang sama dengan entri Ilmari.
Demo
Rincian kasar:
Petakan setiap baris input ke dalam array berpasangan
[value index]
Lipat produk Cartesian di atas baris
Saring ke entri yang 0, 2, 4, dll. Tidak berkurang.
Peta masing-masing ke entri 1, 3, 5, dll.
sumber
Q, 43
sumber