perb

Perb

== include(page="template/taskheader" task_id="perb") ==

Poveste şi cerinţă...

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.

h2. Date de intrare

Fişierul de intrare $perb.in$ ...

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.

h2. Date de ieşire

În fişierul de ieşire $perb.out$ ...

Î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.

h2. Restricţii

* $... ≤ ... ≤ ...$

* $1 ≤ N ≤ 600$
* $1 ≤ M ≤ 500 000$

h2. Exemplu
table(example). |_. perb.in |_. perb.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

| 12 4
  ACTACTGCTACG
  1 3
  1 9
  5 10
  1 12
| 2
  1
  1
  2

|
h3. 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$.

== include(page="template/taskfooter" task_id="perb") ==

5577