Solutii ONIS 2014, Runda 4

Solutii ONIS 2014, Runda 3

h1. Soluţii ONIS 2014, Runda 3

h1. 'Joc17':problema/joc17

(toc)*{text-align:center} *Lista de probleme*
* 'Football':onis-2014/solutii-runda-3#football
* 'Curs Valutar':onis-2014/solutii-runda-3#cursvalutar
* 'Bani':onis-2014/solutii-runda-3#bani
* 'Cercuri5':onis-2014/solutii-runda-3#cercuri5
* 'Cuvant':onis-2014/solutii-runda-3#cuvant
* 'Speculum':onis-2014/solutii-runda-3#speculum
* 'Dans':onis-2014/solutii-runda-3#dans
* 'Subsiruri3':onis-2014/solutii-runda-3#subsiruri3
* 'Joc17':onis-2014/solutii-runda-3#joc17
* 'Arhipelag':onis-2014/solutii-runda-3#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-3/football")==

h1. 'Football':problema/football

==include(page="onis-2014/solutii-runda-3/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-3/bani")==

h1. 'Arhipelag':problema/arhipelag

==include(page="onis-2014/solutii-runda-3/cercuri5")==
 
==include(page="onis-2014/solutii-runda-3/cuvant")==
 
==include(page="onis-2014/solutii-runda-3/speculum")==
 
==include(page="onis-2014/solutii-runda-3/dans")==
 
==include(page="onis-2014/solutii-runda-3/subsiruri3")==
 
==include(page="onis-2014/solutii-runda-3/joc17")==
 
==include(page="onis-2014/solutii-runda-3/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 insule(noduri) are acel component conex, 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