Programavimo pamokėlės

pamokelesm

Mokymų ciklas „Programavimo pamokėlės" skirtos visiems, kurie nori išmokti programuoti.

IT galvosūkiai

itgalvosukiai

Konkurso tikslas – skatinti moksleivius domėtis IT sprendžiant įvairiausius galvosūkius.

Informikas

informikasm

Konkurso tikslas – supažindinti moksleivius su menu informacinėse technologijose ir mūsų talismanu.

Dr. J. P. Kazicko konkursai

kkonkursai

Žemaitijos, Aukštaitijos, Suvalkijos ir Dzūkijos regionuose vykdomas IT konkursas.

       
×

Įspėjimas

JUser: :_load: Nepavyko įkelti nario su id: 825

Užduotis

Įsivaizduojamoje planetoje Gyvūnų žemė yra leidžiamas laikraštis. Laikraščio kiekvieno straipsnio pavadinimas s1 sudarytas iš mažųjų 26 lotyniškos abėcėlės raidžių. Planetos gyventojas, ruoniukas Jonas, nori nusipirkti keletą tokių laikraščių, iškirpti antraštes bei suklijuoti jas į vieną didelį žodį. Suklijavęs antraštes, Jonas iškerpa tam tikras raides iš gauto žodžio, kad būtų gautas naujas žodis s2. Laikoma, kad iškirpus raidę iš žodžio, nepaliekamas tarpas, t.y., žodis išlieka vientisas tik be iškirptų raidžių. Be to, iškirptų raidžių keletą kartų naudoti negalima.

Pavyzdžiui, jeigu straipsnio pavadinimas yra "ada", suklijavus du tokius pačius pavadinimus, gauname "adaada". Jeigu pašalinamos 1 ir 6 raidės, gaunamas naujas žodis "daad".

Kiek mažiausiai reikia laikraščio antraščių s1, kad Jonas jas suklijavęs bei pašalinęs tam tikras raides gautų žodį s2?

Duomenų faile in.txt yra dvi teksto eilutės. Pirmojoje eilutėje yra straipsnio pavadinimas s1, antrojoje žodis s2. Žodžiai gali būti sudaryti iš mažųjų 26 lotynų abėcėlės raidžių (1 ≤ |s1| ≤ 104, 1 ≤ |s2| ≤ 106).

Rezultatų faile out.txt, jeigu neįmanoma suklijuoti žodžio s2 pagal nurodytas sąlygas, išvedamas "-1" (be kabučių). Kitu atveju turi išvestas skaičius, kuris apibrėžia mažiausią reikalingą laikraščio antraščių s1 kiekį, kuris reikalingas Jonui suklijuoti žodį s2.
Pastabos

  • Atkreipkite dėmesį į tai, kad žinomas maksimalus s1.
  • Simbolius galima užrašyti sveikaisias skaičiais. ASCII lentelėje galima rasti, jog a-z mažosios lotyniškos raidės atitinka 97-122 sveikuosius skaičius.
in.txt out.txt

jonas
qwerty

-1

jonas
jonas

1

qwerty
qwqyyq

4

ab
baaabba

6

Detalus pavyzdys

3 pavyzdžio paaiškinimas, kaip gautas rezultatas.

1 pavadinimas paaiskinimas

Reikalavimai

  • Parašyti duomenų skaitymo funkciją void().
  • Uždavinį išspręsti optimizuotai. Kad tai būtų pasiekta, per s1 ir s2 galima iteruoti maksimaliai vieną kartą. Be to, turi būti sukurta funkcija, kurios vienas iš parametrų dvimatis masyvas int[][26], kurį funkcija turi užpildyti. Šiame dvimačiame masyve saugoma kiekvienai s1 pozicijai arčiausia kitų abėcėlės raidžių pozicija žodyje.
  • Sukurti funkciją, kuri per savo vardą grąžintų reikalingų s1 žodžių kiekį, o vienas iš funkcijos parametrų būtinai būtų apskaičiuotas dvimatis masyvas int[][26]. Funkcijos tipas int().

Papildoma informacija

  • Lygis: 3
  • Taškai: 100
Į viršų