• 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

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

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