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

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^N-1 ≡ 1 (mod N), unde N este număr prim.

Vom avea M = (N - 1) * K + Rest, deci:

• a^M (mod M) ≡ (a^(N-1))^K * (a^Rest) (mod M) ≡ 2^K * a^Rest (mod M) ≡ a^Rest (mod M)