Pornind de la această observaţie, problema revine la setarea lungimii $k$ a şirului de caractere şi la parcurgerea caracterelor de la primul către ultimul. Pentru fiecare poziţie $i$, vom verifica dacă $Ai = Ai+k$. În momentul în care dăm peste $2*k$ poziţii consecutive care respectă această proprietate, este evident că am dat peste o secvenţă de tip triopalindrom, deci o vom număra. Complexitate: O(N^2^).

h1. 'Div4':problema/div4
 
Un număr este divizibil cu $4$ dacă restul împărţirii sale la $100$ este divizibil cu $4$. În alte cuvinte, un număr este divizibil cu $4$ dacă ultimele $2$ cifre ale sale sunt divizibile cu $4$. Pentru a ne apropia şi mai mult de rezolvarea problemei, vom spune că un număr este divizibil cu $4$ dacă:
 
* Penultima cifră a sa este impară, iar ultima cifră este $2$ sau $6$
* Penultima cifră a sa este pară, iar ultima cifră este $4$ sau $8$
 
Având în vedere că trebuie să eliminăm exact $K$ cifre şi că ne interesează ultimele $2$ cifre ale numărului rămas, ne vom concentra doar asupra ultimelor $K+2$ cifre ale numărului. Vom proceda în felul următor. Vom seta penultima cifră a numărului. Să presupunem ca am setat cifra de pe poziţia $i$ şi că numărul nostru are în total $C$ cifre. Dacă această cifră este impară, ne interesează numărul de apariţii ale cifrelor $2$ şi $6$, aflate în dreapta ei. Pentru ca cifra de pe poziţia $i$ şi cifrele de după să fie ultimele cifre din număr, va trebui şă ştergem exact $C-i-1$ cifre. Deci, vom avea de şters înca $K-(C-i-1)$ cifre din primele $i-1$. Avem exact combinări de $i-1$ luate câte $K-(C-i-1)$ modalităţi de a face acest lucru. Vom înmulţi acest număr cu numărul de apariţii ale cifrelor $2$ şi $6$ aflate în dreapta cifrei alese şi vom actualiza răspunsul. Vom proceda analog şi la setarea unei cifre pare.
 

h1. 'Dreapta':problema/dreapta

Pentru inceput trebuie observat ca orice punct din interiorul unui poligon are urmatoarea proprietate:

Pentru inceput trebuie observat orice punct din interiorul unui poligon are urmatoarea proprietate:

* Exista cel putin o dreapta care trece prin acel punct astfel incat daca se taie dreapta in doua semidrepte (cu capatul semidreptelor in punctul respectiv), ambele semidrepte intersecteaza poligonul intr-un numar impar de laturi.

Folosind aceasta observatie ne putem gandi la o abordare de genul urmator:

Folosind aceasta observatie ne putem gandi la abordare de genul urmator:

* Calculam punctele de intersectie ale dreptei pe care se afla toate punctele din query-uri cu laturile poligonului
* Sortam punctele de intersectie dupa $x$ si daca sunt egale dupa $y$

public

protected