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