Stran 1 od 1

Morilske besede

Objavljeno: Če Maj 18, 2017 11:15 am
Napisal/-a lukazlatecan
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
  • 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.

Re: Morilske besede

Objavljeno: So Maj 20, 2017 6:41 pm
Napisal/-a hinkopihpih
Zdi se mi, da sem našel napako. Besedi "aaaaaaaa" in "bbbbbbbb" sta prav tako morilski, saj se v prvem primeru k-krat oz. 4-krat ponovi beseda "aa", v drugem primeru pa se prav tolikokrat ponovi beseda "bb". Je to res napaka ali sem jaz narobe razumel nalogo?

Re: Morilske besede

Objavljeno: So Maj 20, 2017 7:11 pm
Napisal/-a Ptolomej
aaaaaaaaa je 4 ponovitev, toda njen podniz aaaa je tudi 4 ponovitev, kar pa po definicij morilske besede ne sme biti.
Torej aaaaaaaa ni morilska beseda.

Re: Morilske besede

Objavljeno: To Maj 23, 2017 4:33 pm
Napisal/-a lukazlatecan
Kot je že odgovoril Ptolomej, noben strnjeni podniz (razen praznega niza in cele besede) ne sme biti k-ponovitev.