FMI No Stress 5 - Solutii
Taste
TDeque
Patrate6
Mere
Soluţia porneşte de la următoarea observaţie: Mickey Mouse nu poate câştiga pentru că Santa Klaus poate lua de fiecare dată câte K mere din coş, iar în acest caz Mickey Mouse nu îl poate depăşi. Ne rămâne să ne gândim când putem vorbi despre o remiză. Vom distinge cazurile:
- 1. Dacă [N / K] este impar, Santa Klaus va avea avantajul unei ture în plus. Deci acesta poate lua mereu K mere din coş, câştigând astfel jocul.
- 2. Dacă [N / K] este par şi N mod K == 0, rezultatul va fi remiză (cum ambii jucători mută optim, ambii vor lua K mere din coş în acest caz, terminând cu un număr egal de mere).
- 3. Dacă [N / K] este par şi N mod K > 0, cum Santa Klaus joacă optim, va lua iniţial N mod K mere din coş, asigurandu-şi astfel un "avantaj". În continuare, vor rămâne in coş exact N - N % K mere, ceea ce ne duce înapoi la al doilea caz. Cum Santa Klaus a reuşit să îşi creeze un avantaj, acesta câştigă de această dată.
Grid
Soluţia brută a problemei care ar fi luat 60 de puncte reprezintă o simulare a operaţiilor pe 3 vectori. Ultimele 4 teste sunt făcute astfel încât operaţiile să fie făcute doar pe primele elemente de pe fiecare rând.
O soluţie brută cu liste sau deque ar fi intrat în timp pentru toate cazurile. Pentru a face soluţia mai rapidă, se putea folosi şi metoda advance0. O altă structură interesantă în STL este forward_list1.
Pentru cei old-school, soluţia ar fi putut fi implementată cu şmenul lui Batog2 în O(sqrt(N)) sau cu treapuri3 în O(log(N)).
0: Advance
1: Forward List
2: Batog
3: Treapuri
