infoarena informatica de performanta

Carti

O stare a cartilor de pe masa se poate reprezenta printr-un numar din intervalul [0, 8191] in felul
urmator: scriind numarul in sistem binar obtinem forma b₁₂b₁₁...b₁b₀, unde b_i = 1, daca si numai daca cartea cu valoarea i+1 se afla pe masa.
Sa consideram vectorul win_i cu semnificatia:

• win_i = true, daca jucatorul care este la mutare in starea i are strategie sigura de castig
• win_i = false, in caz contrar

Determinarea valorilor win_i este destul de simpla. Daca dintr-o stare se poate ajunge intr-o stare in care jucatorul pierde, inseamna ca starea curenta este o stare cu strategie sigura de castig:

• win_i = true, daca din starea i se poate ajunge intr-o stare j astfel incat win_j = false
• win_i = false, in caz contrar

Dintr-o stare i se poate ajunge intr-o stare j daca j se poate obtine din i prin scaderea a cel mult k biti consecutivi. Asadar pentru a vedea in ce stari putem ajunge dintr-o stare i, trebuie sa incercam toate valorile lui k posibile si toate pozitiile pe care poate aparea sirul de biti consecutivi.

win[state]:=0;
for i:=1 to k do
begin
mask:=0;
for j:=0 to i-1 do mask:=mask or (1 shl j);
for j:=0 to 13-i do
if (state and (mask shl j))=(mask shl j)
then
if not DoesWin(state-(mask shl j))
then
begin
win[state]:=1;
break;
end;
if win[state]=1
then break;
end;

Ramane sa calculam numarul nr asociat starii initiale de pe masa, si daca win_nr = true sa afisam Alice, iar in caz contrar sa afisam Bob. Pentru a calcula win_nr vom avea nevoie de examinarea a 2^N stari, asadar algoritmul final are complexitatea O(2^N * K) pentru fiecare configuratie din fisierul de intrare.