Morilske besede
Objavljeno: Če Maj 18, 2017 11:15 am
Naj bo k neko celo število, večje od 1. Neka beseda (niz znakov) je k-ponovitev, če jo lahko dobimo tako, da staknemo k kopij neke krajše besede. Na primer: ababab je 3-ponovitev, baabaa je 2-ponovitev, abbaab pa ni niti 2-ponovitev niti 3-ponovitev.
Beseda je morilska, če je k-ponovitev, hkrati pa noben njen strnjeni podniz (razen praznega niza in cele besede) ni k-ponovitev.
Recimo, da lahko pri sestavljanju besed uporabljamo le prvih m malih črk angleške abecede. Zanima nas, koliko morilskih besed dolžine vsaj 1 in največ n se da pri teh omejitvah sestaviti.
Vhodni podatki
V prvi vrstici je eno celo število T, tj. število testnih primerov. Sledijo testni primeri; vsak je v svoji vrstici, v njej pa so tri cela števila, ločena s po enim presledkom: naprej m, nato k in nazadnje n.
Omejitve vhodnih podatkov
Izhodni podatki
Za vsak testni primer izpišite po eno vrstico, v njej pa naj bo eno samo celo število, namreč število morilskih besed, ki se jih da sestaviti pri danih m, n in k.
Omejitve izhodnih podatkov
Omejitve vhodnih podatkov zagotavljajo, da odgovor, po katerem sprašuje naloga, zagotovo ne bo večji od 1015.
Primer vhoda
Pripadajoč izhod
Komentar
Pri prvem testnem primeru so na primer možne naslednje štiri morilske besede: aaaa, bbbb, abababab in babababa.
Beseda je morilska, če je k-ponovitev, hkrati pa noben njen strnjeni podniz (razen praznega niza in cele besede) ni k-ponovitev.
Recimo, da lahko pri sestavljanju besed uporabljamo le prvih m malih črk angleške abecede. Zanima nas, koliko morilskih besed dolžine vsaj 1 in največ n se da pri teh omejitvah sestaviti.
Vhodni podatki
V prvi vrstici je eno celo število T, tj. število testnih primerov. Sledijo testni primeri; vsak je v svoji vrstici, v njej pa so tri cela števila, ločena s po enim presledkom: naprej m, nato k in nazadnje n.
Omejitve vhodnih podatkov
- 1≤T≤20
- 1≤m≤18
- 2≤k≤5
- 1≤n≤22
Izhodni podatki
Za vsak testni primer izpišite po eno vrstico, v njej pa naj bo eno samo celo število, namreč število morilskih besed, ki se jih da sestaviti pri danih m, n in k.
Omejitve izhodnih podatkov
Omejitve vhodnih podatkov zagotavljajo, da odgovor, po katerem sprašuje naloga, zagotovo ne bo večji od 1015.
Primer vhoda
Koda: Izberi vse
2
2 4 8
3 3 7
Pripadajoč izhod
Koda: Izberi vse
4
9
Komentar
Pri prvem testnem primeru so na primer možne naslednje štiri morilske besede: aaaa, bbbb, abababab in babababa.