Runda 5: Koledzy z klasy
24.06.2009
Organizatorzy pewnego konkursu informatycznego zaprosili do udziału uczniów różnych klas. Po kilku dniach konkursu okazało się, że rozwiązania uczniów z tych samych klas są bardzo podobne. Organizatorzy bardzo się ucieszyli i postanowili odtworzyć podział na klasy na podstawie podobnieństw między rozwiązaniami uczestników. Jednak ponieważ rozwiązań jest bardzo, bardzo wiele, proces ten trzeba zautomatyzować. Potrzebny jest zatem program, który mając dane dwa rozwiązania będzie porównywał ich fragmenty, informując organizatorów, czy są one identyczne, czy nie. WejścieW pierwszych dwóch liniach wejścia znajdują się dwa ciągi znakowe,
każdy nie dłuższy niż 200 000 znaków, składające się z małych i
wielkich liter alfabetu angielskiego oraz cyfr - są to dwa porównywane
rozwiązania uczestników. Następnie na wejściu znajduje się conajwyżej
500 000 zapytań. Każde z nich jest opisane trzema liczbami a, b, n,
które oznaczają kolejno: początek fragmentu w rozwiązaniu pierwszym,
początek fragmentu w rozwiązaniu drugim oraz długość obu fragmentów.
Organizatorzy zauważyli, że oba fragmenty muszą mieć taką samą długość
- w przeciwnym wypadku nie mogłyby być identyczne! Wejście kończy się
zapytaniem WyjścieDla każdego zapytania należy wypisać jedno słowo: PrzykładDla danych wejściowych LoremipsumdolorsitametconsecteturadipiscingelitIntegernonmaurissed poprawną odpowiedzią jest TAK kod: CLASSMATES, limity: 9 s, 64 MB |
Copyright © 2008-2010 Wrocławski Portal Informatyczny
design: rafalpolito.com