Solutii ONIS 2014, Runda 4

onis-2014/solutii-runda-4

h1. Soluţii ONIS 2014, Runda 4

h1. 'Joc17':problema/joc17

(toc)*{text-align:center} *Lista de probleme*
* 'Football':onis-2014/solutii-runda-4#football
* 'Curs Valutar':onis-2014/solutii-runda-4#cursvalutar
* 'Bani':onis-2014/solutii-runda-4#bani
* 'Cercuri5':onis-2014/solutii-runda-4#cercuri5
* 'Cuvant':onis-2014/solutii-runda-4#cuvant
* 'Speculum':onis-2014/solutii-runda-4#speculum
* 'Dans':onis-2014/solutii-runda-4#dans
* 'Subsiruri3':onis-2014/solutii-runda-4#subsiruri3
* 'Joc17':onis-2014/solutii-runda-4#joc17
* 'Arhipelag':onis-2014/solutii-runda-4#arhipelag

Castigatorul jocului e in dependenta de aria matricii pe care se coloreaza,daca aria matricii este numar impar atunci castiga primul jucator(First) daca aria matricii este numar par atunci castiga al doilea(Second)

==include(page="onis-2014/solutii-runda-4/football")==

h1. Football

==include(page="onis-2014/solutii-runda-4/cursvalutar")==

Problema se rezolva prin metoda backtracking, se face un back care construieste toate sumele posibile. Insa aceasta nui destul, pentru ca ar depasi timpul de executie,de aceea generam raspunsurile pt n<=25 prin backtracking dupa care in program afisam doar raspunsurile generate

==include(page="onis-2014/solutii-runda-4/bani")==
==include(page="onis-2014/solutii-runda-4/cercuri5")==
==include(page="onis-2014/solutii-runda-4/cuvant")==

h1. Arhipelag

==include(page="onis-2014/solutii-runda-4/speculum")==
==include(page="onis-2014/solutii-runda-4/dans")==
==include(page="onis-2014/solutii-runda-4/subsiruri3")==
 
==include(page="onis-2014/solutii-runda-4/joc17")==
 
==include(page="onis-2014/solutii-runda-4/arhipelag")==

Pentru a rezolva problema e nevoie sa construim prin listele de adiacenta graful,dupa care sa-l parcurgem dfs si sa aflam componentele conexe si cate sunt ele, nr de insule in fiecare component conex il v-om retine intr-un vector v[i], dupa parcurgerea dfs acest vector v[i] il sortam descrescator. Dupa care creem vectorul rs[i] in care adunam nr de insule in timp ce parcurgem vectorul v[i]

protected

public