Fişierul intrare/ieşire:perb.in, perb.outSursăAlgoritmiada 2011, Runda Finala
AutorAdrian AirineiAdăugată deastronomyAirinei Adrian astronomy
Timp execuţie pe test0.5 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Perb

SMB a studiat la biologie structura secventelor ADN. El primeste o secventa ADN de lungime N, secventa ce contine doar caracterele A, C, G sau T. SMB primeste apoi M intrebari de genul: care este numarul minim de caractere din secventa care trebuie modificate astfel incat subsecventa situata intre pozitiile x si y in sir sa fie periodica? De exemplu, subsecventa ACTACT este periodica de lungime 3, iar subsecventa ACTACTA nu este periodica.

Date de intrare

Fişierul de intrare perb.in va contine pe prima linie doua numere naturale, N si M, avand semnificatia din enunt. Pe urmatoarea linie urmeaza sirul ADN. Pe urmatoarele M linii se afla cate doua numere naturale x si y avand semnificatia din enunt.

Date de ieşire

În fişierul de ieşire perb.out se vor afla M linii, pe fiecare linie aflandu-se raspunsul la intrebarile din fisierul de intrare.

Restricţii

  • 1 ≤ N ≤ 600
  • 1 ≤ M ≤ 500 000

Exemplu

perb.inperb.out
12 4
ACTACTGCTACG
1 3
1 9
5 10
1 12
2
1
1
2

Explicaţie

Pentru prima intrebare, lungimea perioadei trebuie sa fie 1. Trebuie deci sa modificam 2 caractere pentru ca toate trei sa fie identice. Pentru a treia intrebare, trebuia ca subsecventa CTGCTA sa fie periodica. Pentru asta putem modifica un singur caracter, ultimul A in G si obtinem subsecventa CTGCTG care are perioada 3.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content