Rezultatul se găseşte în $d[n]$.
h1. 'Pitici5':problema/pitici5
Impartim piticii in doua categorii: cei care vor sa vada in fata lor un pitic de aceeasi culoare ca si ei (tipul $1$) si restul (tipul $2$). Piticii de tipul $1$ nu ne incurca deloc, ei pot fi inserati fara sa schimbe nimic. Ni se garanteaza ca exista solutie, deci ne imaginam piticii de tipul $2$ plasati intr-un sir de forma $ANANA...ANA$ in care trebuie sa inseram piticii de tipul $1$.
Ni se cere un sir minim lexicografic, deci completam sirul de la stanga la dreapta, la fiecare pas alegand varianta minima lexicografic, cu conditia sa putem completa restul pozitiilor. Singurul caz in care nu mai putem completa restul pozitiilor e cel in care plasam ultimul pitic de tipul $2$ si nu mai putem plasa piticii pe tip $1$ de culoare opusa acestuia.
Complexitatea algoritmului este $O(N)$.
h1. 'Bacterii':problema/bacterii
După primul pas de multiplicare, numărul bacteriilor devine $N * (N - 3) + N + 2$, adică $N * (N - 2) + 2$, adică $(N - 1) ^2^ + 1$. Se demonstrează prin inducţie că după $K$ paşi de multiplicare, numărul bacteriilor devine $[ (N - 1) la 2^K^ ] + 1$.
Vom folosi mica teoremă a lui Fermat:
* $a^N-1^ ≡ 1 (mod N), unde N este număr prim.$
* $a^M-1^ ≡ 1 (mod M), unde M este număr prim.$
Vom avea $2^K^ = (M - 1) * Q + R$, deci:
* $(a^2^)^K^ (mod M) ≡ (a^(M-1)^)^q^ * (a^R^) (mod M) ≡ 2^K^ * a^R^ (mod M) ≡ a^R^ (mod M)$
Înlocuind $a$ cu $N-1$ în relaţia de mai sus, obţinem $[(N-1)^2^]^K^ (mod M) ≡ (N-1)^R^ (mod M)$. Vom calcula mai întâi $R$, ridicând la putere $2$ la $K$ şi reţinând restul împărţirii la $M-1$. Apoi, vom ridica la $N-1$ la puterea $R$, reţinând restul împărţirii la $M$.
h1. 'Fibsmen':problema/fibsmen
Orice numar natural se poate scrie in mod unic ca suma de termeni Fibonacci neconsecutivi. Aceasta scriere se poate obtine in mod greedy (alegem tot timpul cel mai mare numar Fibonacci mai mic sau egal decat numarul curent) in O(k) unde k e numarul de numere Fibonacci mai mici decat N (in cazul nostru, k e maxim 78).
Urmatoarea observatie este ca daca ordonam termenii unei sume de numere Fibonacci distincte, putem grupa termeni consecutivi astfel incat sa creeze exact scrierea unica a lui N cu termeni neconsecutivi (e.g. 73 = (2 + 3) + (13) + (21 + 34) = 5 + 13 + 55), ceea ce inseamna ca putem construi solutia inductiv, parcurgand scrierea unica si calculand la fiecare pas:
A = numarul de scrieri al sumei de pana acum care contin termenul Fibonacci curent
B = numarul de scrieri al sumei de pana acum care NU contin termenul Fibonacci curent
Vom avea $M = (N - 1) * K + Rest$, deci:
Pentru a calcula, vom mai avea nevoie de faptul ca pt M<N, Fib(N) poate fi scris ca suma de numere Fibonacci intre Fib(M) si Fib(N-1) (inclusiv) in exact (N-M)/2 moduri (notam cu d[N][M]).
* $a^M^ (mod M) ≡ (a^(N-1)^)^K^ * (a^Rest^) (mod M) ≡ 2^K^ * a^Rest^ (mod M) ≡ a^Rest^ (mod M)$
Astfel, cand trecem de la un pas la urmatorul, noul A va fi A+B (deoarece putem adauga termenul Fibonacci curent la oricare din sumele precedente fara a altera unicitatea), iar noul B va fi A*d[curent][precedent+1] + B*d[curent][precedent] (deoarece A dintre sume deja contin Fib(precedent)). Rezultatul final va fi A+B (cu A si B de la ultimul pas).
==include(page="template/monthly-2014/footer")==
