Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | x.in, x.out | Sursă | .com 2012 Runda 1 |
| Autor | Eugenie Daniel Posdarascu, Mihai Gheorghe | Adăugată de |  Edp100 •edp100 |
| Timp execuţie pe test | 0.35 sec | Limită de memorie | 36864 kbytes |
| Scorul tău | N/A | Dificultate |   3/5 |
Vezi solutiile trimise | Statistici
X
In anul X, mayasii au facut rost de 2 siruri de caractere cu litere mici ale alfabetului englez. Aceste 2 siruri ii puteau ajuta in a ghici prost viitorul si in a afla ca pe data de 21.12.2012 sfarsitul lumii isi va face aparitia. Ei trebuiau sa raspunda corect la urmatoarele Q intrebari de forma (x, y) care reprezinta: daca am elimina secventa din primul sir de la pozitia x la pozitia y inclusiv, si am pune in locul secventei caracterul X, cate secvente palindroame de lungime impara si mai mare ca 1 exista care au centrul fixat in caracterul X? Deoarece la inceput au prezis bine viitorul si au aflat ca nu va veni sfarsitul lumii, ei totusi si-au dat seama ca nu folosesc la nimic cel de al doilea sir. Ca urmare au mai adaugat o propritate pe care trebuie sa o respecte sirurile palindroame cerute. La primul pas de extindere din centrul X, caracterul cu care se extinde sirul palindrom trebuie sa fie primul caracter din cel de al 2-lea sir, la cel de al 2-lea pas de extindere, caracterul trebuie sa fie cel de al 2-lea caracter din al doilea sir, etc. Mai exact la cel de al i-lea pas de extindere, caracterul cu care se extinde sirul palindrom trebuie sa fie cel de al i-lea caracter din al doilea sir. Un pas de extindere a unui sir palindrom este atunci cand adaugi atat in stanga cat si in dreapta sirului un caracter nou (trebuie sa fie acelasi caracter pentru a se respecta proprietatea de sir palindrom). Practic un pas de extindere reprezinta marirea sirului palindrom cu 2 caractere (unul in stanga si unul in dreapta).
Date de intrare
Fişierul de intrare x.in va contine pe prima linie 3 numere naturale N, M, Q. N este lungimea primului sir, M este lungimea celui de al doilea sir iar Q este numarul de intrebari. A doua linie contine un sir de N caractere ce reprezinta primul sir. A treia linie contine un sir de M caractere ce reprezinta cel de al doilea sir. Pe urmatoarele Q linii sunt cele Q intrebari de forma (x, y).
Date de ieşire
Fişierul de ieşire x.out va contine Q linii. Pe linia i trebuie sa afisati raspunsul la intrebarea i.
Restricţii
- 1 ≤ N ≤ 1.000.000
- 1 ≤ M ≤ 1.000.000
- 1 ≤ Q ≤ 500.000
Exemplu
| x.in | x.out |
|---|---|
| 5 4 1 badab abac 3 3 | 2 |
Explicaţie
Primul pas de extindere va fi facut de caracterul 'a' iar cel de al doilea va fi facut de catre caracterul 'b'.
