Dalam tantangan ini, Anda melewati dua hal:
- Panjang tali,
N
- Daftar string
L
,, masing-masing dengan nilai poin yang ditetapkan. Setiap string yang tidak diteruskan memiliki nilai titik 0
Anda perlu membuat string panjang N
sehingga jumlah semua titik substring adalah sebesar mungkin.
Sebagai contoh:
5 [("ABC", 3), ("DEF", 4), ("CDG", 2)]
harus keluar
ABCDG
Karena dua substring dengan poin ( ABC
dan CDG
) memiliki total 5 poin, dan tidak ada konstruksi lain yang mungkin dapat memberikan 5 atau lebih poin.
Substring dapat digunakan beberapa kali dalam sebuah string, dan dapat tumpang tindih. Anda dapat mengasumsikan bahwa poin akan selalu positif, panjang substring akan antara 1 hingga N
karakter, dan itu N > 0
. Jika beberapa konstruksi maksimal, cetak salah satunya.
Program Anda harus berjalan dalam jumlah waktu yang wajar (tidak lebih dari satu menit untuk masing-masing contoh):
1 [("A", 7), ("B", 4), ("C", 100)] => C
2 [("A", 2), ("B", 3), ("AB", 2)] => AB
2 [("A", 1), ("B", 2), ("CD", 3)] => BB
2 [("AD", 1), ("B", 2), ("ZB", 3)] => ZB
3 [("AB", 2), ("BC", 1), ("CA", 3)] => CAB
3 [("ABC", 4), ("DEF", 4), ("E", 1)] => DEF
4 [("A", 1), ("BAB", 2), ("ABCD", 3)] => AAAA or ABAB or BABA or ABCD
5 [("A", 1), ("BAB", 2), ("ABCD", 3)] => BABCD or BABAB
5 [("ABC", 3), ("DEF", 4), ("CDG", 2)] => ABCDG
5 [("AB", 10), ("BC", 2), ("CA", 2)] => ABCAB
6 [("AB", 10), ("BC", 2), ("CA", 2)] => ABABAB
8 [("AA", 3), ("BA", 5)] => BAAAAAAA
10 [("ABCDE", 19), ("ACEBD", 18), ("ABEDC", 17), ("BCEDA", 16), ("EBDAC", 15), ("BACD", 14), ("CADB", 13), ("ABDC", 12), ("CABD", 11), ("EBDC", 10), ("ACE", 9), ("CBA", 8), ("AEC", 7), ("BE", 6), ("AE", 5), ("DC", 4), ("BA", 3), ("A", 2), ("D", 1)]
=> ACEBDACEBD
Ini adalah kode-golf , jadi siapkan jawaban terpendek Anda dalam bahasa favorit Anda!
sumber
DEF
tupel hilang komaJawaban:
Python 2.7, 503 Bytes
Ini bukan golf, juga tidak efisien; itu hanya enumerasi relatif layak string yang kasar. Saya tidak berpikir itu akan terlalu sulit untuk membuat heuristik yang dapat diterima untuk digunakan dengan A *, yang mungkin akan sedikit lebih cepat. Saya tidak repot melakukan itu, karena metode ini memecahkan semua contoh dalam waktu sekitar 47 detik di laptop saya.
Untuk mengujinya:
Penjelasan
The
v
Fungsi hanya menghitung nilai dari suatu string dengan mencari semua kejadian dari substring di L.m
Fungsi menyebutkan semua string panjangn
dengan awalane
yang dapat dihasilkan dari substring dil
.m
secara rekursif menyebut dirinya sendiri; panggilan pertama harus lulus dalam''
untuke
. Sebagai contoh:The
p
Fungsi hanya loop melalui semua string yang mungkin (seperti yang disebutkan olehm
) dan mengembalikan satu dengan nilai tertinggi (sebagaimana ditentukan olehv
).Perhatikan bahwa
m
fungsi sebenarnya memprioritaskan pencacahan dengan mengurutkan berdasarkan nilai substring. Ini ternyata tidak perlu untuk memastikan optimalitas, dan itu sebenarnya menghambat efisiensi sedikit; Saya bisa menyimpan ~ 20 atau lebih byte dengan menghapusnya.sumber