Revizia anterioară Revizia următoare
Holiday
Autobuze2
- Se garantează că între oricare două staţii consecutive din traseul unui autobuz există o stradă directă.
- Se garantează că între A Ki şi A 1 există o stradă directă, pentru orice i, 1 ≤ i ≤ B.
Având în vedere precizările din enunţul problemei, putem crea un nou graf care folosindu-ne doar de staţiile prin care trece fiecare autobuz. Cum traseul parcurs de un autobuz este: A 1, A 2, ..., A K, A 1, A 2, etc., vom conecta între ele oricare două staţii consecutive din acest traseu printr-o muchie în noul graf. Vrem să pornim din nodul 1 şi să ajungem în nodul N, deci vom porni o parcurgere în lăţime din nodul 1, ţinând pentru fiecare nod i parcurs până acum:
- d[i] = numarul de noduri (staţii) parcurse din nodul 1 pana in nodul i
Răspunsul se va găsi în d[N]. Dacă nu am putut ajunge în nodul N, îl vom încuraja pe Antonio să o invite pe Antonia la un suc.
Litere2
- Două cuvinte fac parte din acelaşi grup dacă sunt formate din aceleaşi litere, repetate de oricâte ori.
Vom lua astfel fiecare cuvânt în parte şi vom marca toate cele 26 litere ale alfabetului englez ('a' - 'z') cu 1, dacă litera apare în cuvânt respectiv cu 0, dacă nu apare. Vom obţine astfel un şir binar de lungime 26. Putem privi acest şir binar ca fiind un număr scris în baza 2. Putem transforma acest număr în baza 10, reformulând afirmaţia iniţială astfel:
- Două cuvinte fac parte din acelaşi grup dacă numărul astfel obţinut asociat celor două cuvinte este acelaşi.
Deci, numărul de grupuri va fi egal cu numărul de valori distincte asociate numerelor. Pentru a determina acest număr ne vom folosi de o structură de date tip Hash sau de o sortare (aceasta fiind teoretic, soluţia de complexitate mai mare).
Timpul de execuţie al acestei probleme se putea mări destul de uşor dacă în program se foloseau elemente din STL sau tipul de date string, care se miscă mai lent în practică.
Treesmen
