시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
5 초 | 1024 MB | 2 | 2 | 2 | 100.000% |
Ett känguruord är ett ord som bär på en synonym till sig självt (en "unge"), på så vis att alla synonymens bokstäver förekommer i ordet, i samma ordning. T.ex. är pastej
ett känguruord, eftersom det bär på synonymen paj
(pastej
). Även aste
och atj
hade räknats som ungar om vi låtsas att de vore ord, men däremot inte paaj
eller etsa
. Formellt uttryckt måste ungen vara en subsekvens till ordet.
Vidare kan vi säga att en unge är stökig om den får plats i ordet på två olika sätt. paj
är inte en stökig unge, men om ursprungsordet hade varit paastej
hade den varit det -- då hade den kunnat gömmas som antingen paastej
eller paastej
.
Givet ett (påhittat) ord $S$, och en lista med (påhittade) synonymer, hur många av synonymerna är stökiga ungar till $S$?
a-z
, ordet $S$ som vi undrar över.a-z
.Ingen synonym kommer förekomma två gånger, eller vara lika med $S$.
Låt $M$ beteckna antalet bokstäver i $S$, och $K$ summan av antalet bokstäver i synonymerna. Då gäller att $M \le 100\,000$, $K \le 500\,000$.
Skriv ut ett heltal -- antalet ord som är stökiga ungar till $S$.
paastej 5 paj aste atj paaaj etsa
3
ababa 6 aa aba abb baa aabb xyz
2
I exempel 1 är de första tre orden ungar till $S$, och dessutom stökiga. Testfallet skulle därmed kunna finnas med i testgrupp 2 eller 4.
I exempel 2 är de fyra första orden ungar, varav de två första dessutom stökiga ungar. Det här testfallet skulle inte kunna vara med i testgrupp 2 eller 4.
Olympiad > Swedish Olympiad in Informatics > 2021 > Online Qualification F번