• Infoarena Monthly 2014
• Format
• Clasament
• Organizatori
• Sponsori si premii
• Regulament
•  
• Runda 1
• Runda 2
• Runda 3
• Runda 4
• Runda 5
• Runda 6
• Runda 7
• Runda 8
• Runda 9
• Runda 10
• Runda 11
• Runda 12

Spargere2

Vom reţine un vector auxiliar cu următoarea semnificaţie:

• d[i] = suma maximă ce poate fi obţinută folosind primele i seifuri

Vom parcurge seifurile de la 1 la N, iar pentru fiecare seif i, avem câteva opţiuni:

• Deschid seiful i şi le ignor pe cele de dinainte.
• Deschid seiful i şi iau şi suma maximă obţinută prin folosirea primelor i - k seifuri.
• Nu deschid seiful i, deci iau suma maximă obţinută prin folosirea celor dinaintea sa, primelor i - 1 seifuri.

În concluzie, vom avea:

• d[i] = max( v[i], d[i - k] + v[i], d[i - 1] )

Rezultatul se găseşte în d[n].

Pitici5

Bacterii

După primul pas de multiplicare, numărul bacteriilor devine N * (N - 3) + N + 2, adică N * (N - 2) + 2, adică (N - 1) ² + 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^M-1 ≡ 1 (mod M), unde M este număr prim.

Vom avea 2^K = (M - 1) * Q + R, deci:

• (a²)^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)²]^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.

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

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]).

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