Gambaran
Dalam tantangan ini, tugas Anda adalah secara acak menghasilkan fungsi matematika monoton antara dua set.
Memasukkan
Input Anda adalah dua bilangan bulat positif s
dan n
.
Setelah mendapatkan input ini, program Anda akan menghasilkan fungsi matematika acakf
dari set ke . Dengan kata lain, adalah "aturan" yang mengambil -tuple bilangan bulat antara dan , dan mengembalikan satu bilangan bulat tersebut. Selain itu, harus monoton dalam pengertian berikut. Jika dan dua- tuple seperti itu berlaku untuk setiap koordinat , maka .{0,1,...,s-1}n
{0,1,...,s-1}
f
n
0
s-1
f
A
B
n
A[i] ≥ B[i]
i
f(A) ≥ f(B)
Distribusi tepat dari fungsi monotonik f
tidak masalah, selama masing-masing fungsi tersebut memiliki probabilitas positif yang dihasilkan (dengan asumsi RNG sempurna).
Keluaran
Output Anda akan menjadi enumerasi input dan output dari f
. Ini harus berisi semua n
-tupel bilangan bulat di antara 0
dan s-1
dalam beberapa urutan, masing-masing diikuti oleh output yang sesuai dari f
. Format output yang tepat fleksibel (sesuai alasan).
Contohnya
Input s = 3
dan n = 2
mungkin menghasilkan output
(0, 0) 0
(0, 1) 1
(0, 2) 2
(1, 0) 0
(1, 1) 1
(1, 2) 2
(2, 0) 1
(2, 1) 1
(2, 2) 2
Ini berisi semua pasangan di atas set {0, 1, 2}
tepat sekali, dan masing-masing diikuti oleh nilai- f
nya. Kondisi monotonisitas juga terpenuhi. Tupel diberikan di sini dalam urutan leksikografis, tetapi ini tidak perlu.
Sebagai contoh lain, s = 2
dan n = 4
mungkin menghasilkan
(0, 0, 0, 0) 0
(0, 0, 0, 1) 0
(0, 0, 1, 0) 0
(0, 0, 1, 1) 0
(0, 1, 0, 0) 1
(0, 1, 0, 1) 1
(0, 1, 1, 0) 1
(0, 1, 1, 1) 1
(1, 0, 0, 0) 0
(1, 0, 0, 1) 1
(1, 0, 1, 0) 0
(1, 0, 1, 1) 1
(1, 1, 0, 0) 1
(1, 1, 0, 1) 1
(1, 1, 1, 0) 1
(1, 1, 1, 1) 1
Berikut ini adalah semua output yang mungkin untuk s = 2
dan n = 2
(hingga penataan ulang tupel); program Anda harus secara acak menampilkan salah satunya:
(0,0) 0
(0,1) 0
(1,0) 0
(1,1) 0
-------
(0,0) 0
(0,1) 0
(1,0) 0
(1,1) 1
-------
(0,0) 0
(0,1) 0
(1,0) 1
(1,1) 1
-------
(0,0) 0
(0,1) 1
(1,0) 0
(1,1) 1
-------
(0,0) 0
(0,1) 1
(1,0) 1
(1,1) 1
-------
(0,0) 1
(0,1) 1
(1,0) 1
(1,1) 1
Aturan dan Penilaian
Anda dapat menulis program atau fungsi lengkap. Hitungan byte terendah menang, dan celah standar tidak diizinkan. Kode dengan penjelasan lebih disukai.
Tidak ada batasan pada kompleksitas waktu, tetapi saya akan memberikan bonus -15% jika solusi Anda selalu dijamin selesai dalam jumlah waktu tertentu (tergantung pada input, dan dengan asumsi RNG sempurna yang berjalan dalam waktu konstan) .
sumber
Jawaban:
Pyth, 35 byte (38 - 15% = 31,45 lebih jauh ke bawah)
Demonstrasi
Input dalam format:
Output dalam format:
Cukup membuat kemungkinan acak dan mengujinya.
Alternatif versi 37 byte yang saya yakin memenuhi syarat untuk bonus:
Demonstrasi
Ini dimulai dengan menghasilkan semua fungsi monotonik yang mungkin, kemudian mengeluarkannya secara acak. Ini jauh lebih lambat, dan paling disukai
2,2
.sumber
3, 2
. Sayangnya, saya bahkan tidak mendapat respons3, 3
dari pelaksana pyth online. Apakah ada loop tanpa akhir untuk kombinasi ini ?!2, 4
, tetapi tidak banyak lagi.CJam, 40 byte - 15% = 34 byte
Pendekatan ini menghasilkan semua fungsi yang valid dan kemudian memilih secara acak. Run time setidaknya O (s 2s n ) , tetapi konstan untuk input yang diberikan.
Saya ragu inilah yang ada dalam pikiran OP, tetapi dijamin akan selesai dalam waktu tertentu (tergantung pada input [...]) dan karenanya memenuhi syarat untuk bonus.
Cobalah online di penerjemah CJam .
sumber
Julia, 64 byte (-15% = 54,4)
Tidak Disatukan:
Ini akan berjalan dengan cepat, dengan satu-satunya masalah yang mungkin terjadi dengan memori untuk s dan n yang cukup besar (g (10,10) harus menghasilkan array 10 ^ 10, jadi jelas itu akan kehabisan memori - bahkan jika setiap nomor adalah satu byte, itu 10 gigabytes data).
Output adalah pengindeksan berbasis 1, jadi untuk menentukan hasil untuk input yang diberikan, Anda perlu menambahkan satu untuk setiap nilai input. Misalnya, untuk menemukan f (1,2,6,0,3), Anda perlu memeriksa
K[2,3,7,1,4]
.sumber