Gigel şi Resturile

Având în vedere faptul că numărul de pe foaia lui Gigel are maxim 106 cifre în baza B, nu îl putem transforma în baza 10 direct, urmând ca mai apoi să îl împărţim la K. Aşadar, avem un număr A0A1...An-1 în baza B. Îl vom transforma în baza 10, reţinând la fiecare pas doar restul care ne interesează prin procedeul descris în cele ce urmează.

Vom nota cu X numărul pe care dorim să îl obţinem. Iniţializăm X cu 0. Parcurgem cifrele una câte una, începând cu A0. Pentru fiecare cifră Ai, vom înmulţi X cu B şi vom adăuga Ai la X. Având în vedere că nu ne interesează numărul în sine, ci doar restul împărţirii acestuia la K, vom reţine de fiecare dată X modulo K.

Triopalindrom

Un şir de caractere A1A2...A3*k este triopalindrom dacă:

  • A1 = Ak+1, A2 = Ak+2, ..., Ak = A2*k
  • Ak+1 = A2*k+1, Ak+2 = A2*k+2, ..., A2*k = A3*k

Cu alte cuvinte, un şir de caractere A1A2...A3*k este triopalindrom dacă:

  • Ai = Ai+k, pentru oricare 1 ≤ i ≤ 2*k

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(N2).

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.

Dreapta

Pentru inceput trebuie observat ca 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:

  • 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
  • Pentru fiecare punct din query se cauta binar pozitia pe care ar trebui sa o aiba in sirul sortat al punctelor de intersectie. Daca inainte si dupa pozitia ocupata in sir se gaseste un numar impar de puncte atunci punctul din query se afla in interiorul poligonului