Temukan urutan pertukaran menguntungkan maksimal yang diberikan tabel nilai tukar.
Sebagai contoh perhatikan mata uang A riary (mata uang Anda rumah), B AHT, C edi, dan D enar mana tingkat dari satu ke yang lain (setelah setiap tingkat transaksi telah dikenakan) diberikan oleh (baris, kolom) masuk dalam tabel nilai tukar di bawah ini:
TO
A B C D
A 0.9999 1.719828 4.509549 0.709929
F B 0.579942 0.9999 2.619738 0.409959
R
O C 0.219978 0.379962 0.9999 0.149985
M
D 1.39986 2.429757 6.409359 0.9999
Jelas menukar A dengan A bukanlah ide bagus karena meja ini dengan senang hati akan menagih Anda untuk tidak melakukan apa pun.
Kurang jelas, tetapi benar dengan tabel ini, menukar A untuk mata uang lainnya dan kemudian menukar kembali adalah pembuat kerugian:
via B: 1.719828 × 0.579942 = 0.997400489976
via C: 4.509549 × 0.219978 = 0.992001569922
via D: 0.709929 × 1.39986 = 0.99380120994
Namun, bertukar A ke D kemudian D ke B kemudian B kembali ke A tidak keuntungan (diberikan cukup modal untuk tidak menyerah pembulatan):
0.709929 × 2.429757 × 0.579942 = 1.0003738278192194
Orang bisa berulang kali mengambil "makan siang gratis" ini sementara ada peluang.
Tapi rantai yang lebih menarik ada di sini, yaitu A ke D lalu D ke C lalu C ke B dan akhirnya B kembali ke A :
0.709929 × 6.409359 × 0.379962 × 0.579942 = 1.0026612752037345
Detail Tantangan
Mengingat tabel nilai tukar dalam format wajar yang perbaikan arti dari rumah-mata uang (misalnya 1 st baris dan 1 st kolom selalu rumah-mata)
(atau diberi meja tersebut dan indeks rumah-mata)
menemukan * urutan arbitrase maksimal dari pertukaran dimulai dan diakhiri dengan mata uang lokal sebagai indeks ke dalam daftar mata uang tanpa mengulangi penggunaan pertukaran apa pun (yaitu pertukaran Y-> X dapat mengikuti X-> Y satu, tetapi X-> Y mungkin tidak ikuti X-> Y).
Jika tidak ada peluang yang menguntungkan seperti itu, berikan daftar kosong, atau hasil lain yang tidak dapat dikacaukan dengan peluang yang diidentifikasi.
- misalnya untuk contoh di atas ( A-> D, D-> C, C-> B, B-> A ):
- menggunakan pengindeksan 0 satu mungkin kembali
[[0,3],[3,2],[2,1],[1,0]]
atau[0,3,2,1,0]
- menggunakan 1-pengindeksan mungkin kembali
[[1,4],[4,3],[3,2],[2,1]]
atau[1,4,3,2,1]
Format lain baik-baik saja asalkan tidak ada ambiguitas.
- Satu hal yang harus diperhatikan adalah kesempatan terbaik untuk menjadi satu transaksi dari rumah-> rumah (meja bodoh). Jika Anda memutuskan untuk pergi dengan mengecualikan indeks mata uang rumah dari kedua ujung opsi flat di atas (yaitu [3,2,1]
atau [4,3,2]
) dan daftar kosong untuk "tidak ada peluang" maka pastikan home-> home juga bukan daftar kosong.
* Jika ada beberapa peluang yang sama-sama menguntungkan dan menguntungkan, kembalikan salah satu dari mereka, beberapa di antaranya, atau semuanya.
Algoritma Bellman-Ford adalah salah satu cara untuk mendekati ini, tetapi mungkin bukan yang paling cocok untuk golf.
Uji Kasus
Input yang ditampilkan adalah dalam pengaturan yang digunakan dalam contoh, dan hasil yang ditampilkan menggunakan pengindeksan-0 untuk mendaftar ke-mata uang-indeks (ketika ada kesempatan, mata uang asal berada di akhir trailing saja; tidak ada peluang adalah daftar kosong).
[[0.999900, 1.719828, 4.509549, 0.709929],
[0.579942, 0.999900, 2.619738, 0.409959],
[0.219978, 0.379962, 0.999900, 0.149985],
[1.399860, 2.429757, 6.409359, 0.999900]] -> [3, 2, 1, 0]
[[0.9999, 1.5645, 0.9048, 1.0929],
[0.6382, 0.9999, 0.5790, 0.6998],
[1.1051, 1.7269, 0.9999, 1.2087],
[0.9131, 1.4288, 0.8262, 0.9999]] -> [1, 2, 0]
[[0.9999, 1.4288, 0.8262, 0.9131],
[0.6998, 0.9999, 0.5790, 0.6382],
[1.2087, 1.7269, 0.9999, 1.1051],
[1.0929, 1.5645, 0.9048, 0.9999]] -> [1, 2, 3, 1, 0]
[[1.002662, 1.719828, 4.509549, 0.709929],
[0.579942, 0.999900, 2.619738, 0.409959],
[0.219978, 0.379962, 0.999900, 0.149985],
[1.399860, 2.429757, 6.409359, 0.999900]] -> [3, 2, 1, 0, 0]
[[1.002662, 1.719828, 4.509549, 0.709929],
[0.579942, 1.002604, 2.619738, 0.409959],
[0.219978, 0.379962, 1.003000, 0.149985],
[1.399860, 2.429757, 6.409359, 1.002244]] -> [3, 3, 2, 2, 1, 1, 0, 0]
[[0.9999, 1.4288, 0.8262, 0.9131],
[0.6998, 0.9999, 0.5790, 0.6382],
[1.2087, 1.7269, 1.0001, 1.1051],
[1.0929, 1.4974, 0.9048, 0.9999]] -> [1, 2, 2, 0]
[[0.9999, 1.3262, 0.7262, 0.9131],
[0.6998, 0.9999, 0.5490, 0.6382],
[1.2087, 1.7269, 0.9999, 1.2051],
[1.0929, 1.5645, 0.9048, 0.9999]] -> [3, 2, 3, 1, 0]
[[0.9999, 1.5645, 0.9048, 0.5790],
[0.6382, 0.9999, 0.5790, 0.3585],
[1.1051, 1.7269, 0.9999, 0.6391],
[1.7271, 2.6992, 1.5645, 0.9999]] -> [1, 2, 0] and/or [3, 2, 0]
[[0.9999, 1.2645, 0.7048, 0.3790],
[0.4382, 0.9999, 0.3790, 0.1585],
[1.0001, 1.5269, 1.0001, 0.4391],
[1.5271, 2.4992, 1.3645, 0.9999]] -> []
[[0.9999, 1.2645, 0.7048, 0.3790],
[0.4382, 0.9999, 0.3790, 0.1585],
[0.9999, 1.5269, 1.4190, 0.4391],
[1.5271, 2.4992, 1.3645, 0.9999]] -> [2, 2, 0]
Ini adalah kode-golf sehingga solusi terpendek dalam byte menang, tetapi persaingan juga harus dibuat dalam bahasa, jadi jangan biarkan bahasa kode-golf membuat Anda menunda mengirimkan yang favorit!
sumber