Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | perb.in, perb.out | Sursă | Algoritmiada 2011, Runda Finala |
| Autor | Adrian Airinei | Adăugată de |  Airinei Adrian •astronomy |
| Timp execuţie pe test | 0.5 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate | N/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. El 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.in | perb.out |
|---|---|
| 12 4 ACTACTGCTACG 1 3 1 9 5 10 1 12 | 2 1 1 2 |
Explicaţie
...
