Dalam tugas ini, kami mempertimbangkan array bilangan bulat positif seperti ini:
3 18 321 17 4 4 51 1 293 17
Input tersebut terdiri dari sepasang array seperti itu, baik dari panjang positif, sewenang-wenang, mungkin berbeda. Menentukan apakah pemesanan Total ≤ X ⊂ N × N , di mana N adalah himpunan bilangan bulat positif, ada sehingga kedua array masukan dalam rangka sehubungan dengan ≤ X . Perhatikan bahwa (A ≤ X B ∧ B ≤ X A) ↔ A = B harus memegang, yaitu, dua angka dianggap sama di bawah ≤ X jika dan hanya jika mereka adalah nomor yang sama.
Misalnya, jika inputnya adalah sepasang array
7 2 1 1 4 12 3
9 8 7 2 5 1
maka Anda seharusnya mencari tahu apakah total pemesanan ≤ X ada sedemikian rupa
7 ≤ X 2 ≤ X 1 ≤ X 1 ≤ X 4 ≤ X 12 ≤ X 3
dan
9 ≤ X 8 ≤ X 7 ≤ X 2 ≤ X 5 ≤ X 1.
Kiriman Anda dapat berupa subrutin atau program yang menerima dua larik (sebagaimana ditentukan di atas) input dengan cara yang ditentukan implementasi, menghitung apakah total pemesanan ≤ X memenuhi permintaan yang disebutkan di atas ada dan mengembalikan satu nilai yang mewakili “ya” atau berbeda nilai yang mewakili "tidak." Pilihan nilai-nilai ini arbitrer, harap dokumentasikan.
Anda dapat mengasumsikan bahwa array input masing-masing berisi tidak lebih dari 2 15 - 1 elemen dan bahwa masing-masing elemen berada dalam kisaran dari 1 hingga 2 15 - 1 inklusif. Anda mungkin mengharuskan setiap array diakhiri oleh sentinel konstan di luar rentang yang disebutkan di atas seperti 0. Silakan tentukan sentinel apa yang dibutuhkan. Anda mungkin memerlukan panjang array sebagai input tambahan jika panjangnya tidak dapat disimpulkan dari array itu sendiri (mis. G dalam bahasa seperti C). Selain larangan celah standar, Anda tidak diperbolehkan menggunakan rutinitas penyortiran topologi.
Tantangan ini adalah golf kode. Kiriman dengan jumlah karakter paling sedikit menang.
sumber
Jawaban:
Pyth,
2822Menciptakan fungsi
y
yang dapat Anda panggil dengan tuple yang berisi dua array. Mengembalikan "Benar" jika ada pemesanan total, "Salah" jika tidak.Program pembantu yang mendefinisikan dan memanggil fungsi di atas dengan stdin:
Coba di sini.
Kami pertama kali membaca kedua array. Kemudian kita akan membuat semua kombinasi dari kedua array. Kemudian untuk setiap kombinasi, kami akan menganggap array pertama adalah otoritatif, dan memeriksa apakah array konsisten dengan array kedua.
sumber
Receives two arrays ... in an implementation-defined way.
Anda dapat menyimpan setidaknya 7 karakter.GolfScript, 25 byte
Coba kode ini secara online.
Mengambil array dua (atau lebih!) Array di stack; mengembalikan 1 (benar) jika setiap pasang array input memiliki urutan total yang kompatibel, atau 0 (salah) sebaliknya.
Ia bekerja dengan mengulangi setiap pasangan array input yang mungkin (termasuk setiap array yang dipasangkan dengan dirinya sendiri), menyortir elemen-elemen dalam array pertama sesuai dengan posisi di mana mereka pertama kali terjadi pada array kedua (mengabaikan yang tidak ditemukan), dan memeriksa bahwa pesanan yang dihasilkan cocok dengan aslinya.
Walaupun kode ini dapat mengambil jumlah array input yang berubah-ubah, perlu dicatat bahwa kode ini hanya memeriksa konsistensi berpasangan . Sebagai contoh, ia mengembalikan true untuk input
[[1 2] [2 3] [3 1]]
, karena dua dari tiga array memiliki total order yang konsisten. Namun, itu sudah cukup untuk kasus dua input, itulah yang dibutuhkan oleh tantangan.Ini versi de-golf dengan komentar:
Ps. Dimungkinkan untuk secara sepele menyimpan satu atau dua byte dengan meminta input untuk diberikan secara langsung dalam variabel bernama
A
, dan / atau dengan mengubah format output ke array kosong untuk "ya" dan array yang tidak kosong untuk "tidak" . Namun, itu tampak agak curang bagi saya.sumber
J,
363026 byteMari kita panggil dua daftar input
a
danb
. Fungsi memeriksa (dengan(e.~(-:/:~)@#i.)
) apakaha
Elemen diurutkan (sehubungan dengana
) dib
a
Elemen diurutkan (sehubungan dengana
) dia
b
Elemen diurutkan (sehubungan denganb
) dia
b
Elemen diurutkan (sehubungan denganb
) dib
Input adalah daftar dua vektor integer.
Hasilnya adalah
1
jika ada pemesanan0
sebaliknya. (Runtime adalah O (n * n).)Pemakaian:
Cobalah online di sini.
sumber
b
tidak bisa disortir sehubungan denganb
?b=1 2 1
atau dalam contoh kedua sayab=7 2 1 1 4 12 3 1
Ruby, 79
Diharapkan input menjadi file dua baris angka yang dipisahkan oleh ruang. Kembali
true
ketika pemesanan ada,nil
jika tidak.sumber
nil
ataufalse
hanya merasa terlalu salah.nil
ataufalse
sama sekali tidak masalah.Haskell, 98 byte
Pengembalian
True
atauFalse
. Contoh penggunaan:[7,2,1,1,4,12,3] # [9,8,7,2,5,1]
->True
.Cara kerjanya: menghapus duplikat berturut-turut dari daftar input (misalnya:.
[1,2,2,3,2] -> [1,2,3,2]
Pesanan ada jika kedua daftar yang dihasilkan tidak mengandung duplikat dan persimpangan list1 dan list2 sama dengan persimpangan list2 dan list1.sumber