Solutii la concursul acm 2013 etapa nationala partea I

Solutii la concursul ACM ICPC 2013 etapa nationala partea I

h2. 'G. Election Time':http://acm.tju.edu.cn/toj/vcontest/showp9268_G.html
Aceasta a fost cea mai simplă problemă din concurs, fiind rezolvată de marea majoritate a echipelor.

Problema ne cerea să determinăm câştigătorul alegerilor dupa 2 tururi ştiind cate voturi va obţine fiecare candidat in cele 2 tururi. În plus după primul tur rămâneau doar primii k candidati.

Problema ne cerea să determinăm câştigătorul alegerilor dupa 2 tururi ştiind cate voturi va obţine fiecare candidat in cele 2 tururi. În plus în al doilea tur se calificau doar primii $k$ candidati.

O soluţie ar fi sortarea candidaţilor descresrescător după numărul de voturi primite în primul tur, iar pe urmă sortarea primilor k după numărul de votur din al doilea tur. Pentru a nu complica implementarea am ales sortarea unui vector de indici in funcţie de numărul de voturi.

O soluţie ar fi sortarea candidaţilor descresrescător după numărul de voturi primite în primul tur, iar pe urmă sortarea primilor k după numărul de voturi din al doilea tur. Pentru a nu complica implementarea am ales sortarea unui vector de indici in funcţie de numărul de voturi.

== code(cpp) |
#include <iostream>

Problema aceasta ne dădea un graf ponderat şi ne cerea să aflăm timpul minim în care putem traversa graful din nodul $S$ în nodul $D$ şi în care strângem cel putin $k$ unităţi de lemn. Atunci când traversăm o muchie primim $10$ unităţi de lemn in plus.

În ciuda faptului că problema e o problemă clasică de drum minim, ea a fost rezolvată de puţine echipe. Pentru a rezolva formăm un graf în care nodurile sunt determinate de perechi de forma $(nod iniţial, cantitate de lemn)$. În plus mai observăm că putem împărţi cantităţile de lemn la 10. Acum trebuie doar să aplicăm un algoritm de drum minim pentru a afla timpul de parcurgere din nodul $(S,0)$ în nodul $(D,⌈K/10⌉)$. Pentru a lua AC era suficienta folosirea algoritmului Bellman Ford cu coadă

În ciuda faptului că problema e o problemă clasică de drum minim, ea a fost rezolvată de puţine echipe. Pentru a rezolva formăm un graf în care nodurile sunt determinate de perechi de forma $(nod iniţial, cantitate de lemn)$. În plus mai observăm că putem împărţi cantităţile de lemn la 10 şi că nu ne interesează cantităţile de lemn mai mari decât $,⌈K/10⌉$. Acum trebuie doar să aplicăm un algoritm de drum minim pentru a afla timpul de parcurgere din nodul $(S,0)$ în nodul $(D,⌈K/10⌉)$. Pentru a lua AC era suficienta folosirea algoritmului Bellman Ford cu coadă.

h2. 'J. Template Library Management':http://acm.tju.edu.cn/toj/vcontest/showp9268_J.html

public

protected

9016