Zabavno dejstvo iz sveta matematike
1/998001 nam da urejeno zaporedje od 000 do 999. 1/998001 = 0.000001002003004...

Zabavno dejstvo iz sveta računalništva
Leta 1936 so Rusi naredili računalnik na vodo. (Vir: http://gizmodo.com/5879106/the-russian-computer-that-ran-on-water)

Morilske besede

Moderatorji: hinkopihpih, Matic Conradi

lukazlatecan
Site Admin
Prispevkov: 23
Pridružen: Po Apr 24, 2017 5:29 pm
Kraj: Celje

Morilske besede

OdgovorNapisal/-a lukazlatecan » Č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
  • 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.
Mathematicians have tried in vain to this day to discover some order in the sequence of prime numbers, and we have reason to believe that it is a mystery into which the human mind will never penetrate. - Leonhard Euler

hinkopihpih
Prispevkov: 11
Pridružen: Ne Apr 30, 2017 2:11 pm

Re: Morilske besede

OdgovorNapisal/-a hinkopihpih » So Maj 20, 2017 6:41 pm

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?

Ptolomej
Prispevkov: 253
Pridružen: Po Apr 24, 2017 9:02 pm
Kraj: Celje

Re: Morilske besede

OdgovorNapisal/-a Ptolomej » So Maj 20, 2017 7:11 pm

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.
Meje mojega jezika so meje mojega sveta.- Ludwig Wittgenstein

lukazlatecan
Site Admin
Prispevkov: 23
Pridružen: Po Apr 24, 2017 5:29 pm
Kraj: Celje

Re: Morilske besede

OdgovorNapisal/-a lukazlatecan » To Maj 23, 2017 4:33 pm

Kot je že odgovoril Ptolomej, noben strnjeni podniz (razen praznega niza in cele besede) ne sme biti k-ponovitev.
Mathematicians have tried in vain to this day to discover some order in the sequence of prime numbers, and we have reason to believe that it is a mystery into which the human mind will never penetrate. - Leonhard Euler


Vrni se na “Poskusno kolo”

Kdo je na strani

Po forumu brska: 0 registriranih uporabnikov in 2 gosta