Fişierul intrare/ieşire:x.in, x.outSursă.com 2012 Runda 1
AutorEugenie Daniel Posdarascu, Mihai GheorgheAdăugată deedp100Edp100 edp100
Timp execuţie pe test0.35 secLimită de memorie36864 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

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.inx.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'.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content