BitCell

Enunt :

Petrică are n cartonaşe cu numere naturale distincte. El vrea să găsească cel mai mare număr care se poate forma prin unirea a două cartonaşe diferite. Două cartonaşe se pot uni dacă primul cartonaş se termină cu cifra cu care începe al doilea cartonaş. Ajutaţi-l pe Petrică să găsească numărul dorit.

Petrică are n=5 cartonaşe
2393 1963 1971 120 34
Cel mai mare număr care se poate forma este 19711963

Date de intrare
Fişierul de intrare NUMAR.IN conţine pe prima linie numărul de cartonaşe n, iar pe a doua linie n valori naturale reprezentând numerele de pe cele n cartonaşe. Valorile de pe linia a doua sunt separate prin câte un spaţiu.

Date de ieşire
Fişierul de ieşire NUMAR.OUT conţine cel mai mare număr care se poate forma prin unirea a două cartonaşe astfel încât al doilea cartonaş începe cu cifra cu care se termină primul cartonaş. Dacă nu există soluţie atunci se afişează 0.

Restricţii şi precizări
• 2 ≤ n≤ 10000, n număr natural
• Numerele de pe cartonaşe sunt numere naturale cu valori mai mici sau egale cu 20000.

Exemple
NUMAR.IN
5
2393 1963 1971 120 34
NUMAR.OUT
19711963
Explicaţie
Se unesc cartonaşele ce conţin numerele 1971 şi 1963
NUMAR.IN
2
456 89
NUMAR.OUT
0
Explicaţie
Cele două cartonaşe nu se pot uni în modul cerut de problemă

Timp maxim de execuţie/test : 1 secundă

Am reusit sa rezolv aceasta problema dar 4 dintre teste depasesc timpul de executie.


Imi puteti da niste sfaturi ca sa mai reduc din cod si sa functioneze mai repede varog frumos?

Ai putea încerca să rezolvi problema cu șiruri în loc de metoda acutală de calcul cu puterii. O altă abordare productivă ar fi să încarci elementele într-un vector ordonat. În felul acesta ai mai reduce din complexitate.

Conform simulărilor, varianta cu șiruri ar fi în medie cu 130% mai rapidă.

Algoritmul lui jolgau s-a executat in 776243 nano secunde
Algoritmul cu siruri s-a executat in 299634 nano secunde
t(jolgau)/t(siruri) = 2.59064

Nu ai nevoie să optimizezi codul (deși într-adevăr e loc de ceva optimizări) ci să găsești un algoritm mai eficient. Problema poate fi rezolvată în O(n). Pentru asta, formezi două tablouri, maxInceput și maxSfarsit, unde maxInceput[i] va reprezenta numărul maxim dintre cele citite care începe cu cifra i (analog, în maxSfarsit[i] vei salva numărul maxim care se termină cu cifra i). Folosești apoi cele două tablouri pentru determinarea numărului maxim care poate fi obținut (las asta în seama ta).

Multumesc, acuma o sa o implementez.