(Creat de ==user(user="Cosmin" type="tiny")== la data de _2006-08-03_ categoria __, autor(i) _Cosmin_)

==Include(page="template/raw")==
 

Concursul a fost unul reusit, adunand un numar respectabil de participanti.
Concurentii ce vor participa la IOI au fost in forma azi ocupand primele trei pozitii ale clasamentului. greco a impresionat placut fiind singurul ce a rezolvat perfect problema de idee a concursului. Il remarcam pozitiv si pe wefgef care se tine aproape de ei, de asemenea o remarca negativa ar fi la adresa lui Adrian Vladu care nu a participat la aceasta pregatire ,desi ea a fost adresata direct lotului olimpic.

Aceasta problema a fost considerata una medie, pentru ca algoritmii de drum minim in grafuri sunt foarte frecvent folositi la concursurile de programare.

Obsevam ca fiecare paznic va fi la orasul de unde a pornit la timpii multipli de $2*(l{~i~}-1)$ (din cauza miscarii dute-vino). Astfel toti paznicii vor fi in acelasi timp la orasul initial al fiecaruia la toti timpii multipli de {$cmmmc(2*(l{~1~}-1), 2*(l{~2~}-1), ..., 2*(l{~n~}-1))$}. Din cauza ca $l{~i~} < 8$ cel mai mic multiplu comun maxim posibil al numerelor din problema poate fi {$cmmmc(2*4, 2*3, 2*5) = 120$}, astfel pozitiile paznicilor pe reteaua noastra de orase cicleaza si perioada ciclului este $120$ sau un divizor al sau. Vom crea un graf in care nodurile sunt stari ale problemei (oras, {$timp % 120$}). Acum am redus problema la determinarea drumului de cost minim de la ({$1, 0$}) la ({$N, timp % 120$}), putem folosi un algoritm de drum minim la alegere Dijkstra cu heapuri sau bellman ford.

Obsevam ca fiecare paznic va fi la orasul de unde a pornit la timpii multipli de {$2*(l{~i~}-1)$} (din cauza miscarii dute-vino). Astfel toti paznicii vor fi in acelasi timp la orasul initial al fiecaruia la toti timpii multipli de {$cmmmc(2*(l{~1~}-1), 2*(l{~2~}-1), ..., 2*(l{~n~}-1))$}. Din cauza ca $l{~i~} < 8$ cel mai mic multiplu comun maxim posibil al numerelor din problema poate fi {$cmmmc(2*4, 2*3, 2*5) = 120$}, astfel pozitiile paznicilor pe reteaua noastra de orase cicleaza si perioada ciclului este $120$ sau un divizor al sau. Vom crea un graf in care nodurile sunt stari ale problemei ({$oras$}, {$timp &#0037; 120$}). Acum am redus problema la determinarea drumului de cost minim de la ({$1, 0$}) la ({$N, timp &#0037; 120$}), putem folosi un algoritm de drum minim la alegere Dijkstra cu heapuri sau bellman ford.

h2. Pscpld