h3. Soluţie

Pentru orice două autobuze vom găsi care sunt sensurile de mers pentru ele astfel ca cele două autobuze să nu se întâlnească şi să provoace un accident. Pentru un sens fixat putem afla pentru un autobuz pe ce interval de timp va fi pe o anumită stradă. El va fi în general pe o stradă $(i, j)$ pe un interval de tipul $[t1 + k*T … t2 + k*T]$ unde $t1$ este timpul din prima rută parcursă pentru a ajunge la $i$, $t2$ timpul pentru a ajunge la $j$ iar $T$ este durata totală a unei rute. Acum, pentru a determina dacă două autobuze se vor întâlni pe o rută $(i, j)$ trebuie ca ele să se deplaseze în sensuri opuse pe această rută, iar intervalele lor $[t1 + k*T1 .. t2 + k*T1]$ se intersectează cu intervalele $[tt1 + p*T2 … tt2 + p*T2]$. Este clar acum că putem transforma problema într-o instanţă de $2-SAT$ prin maparea autobuzelor în variabile logice, a sensurilor de mers în valorile $adevărat$ şi $fals$, iar pentru orice pereche de autobuze să fie o propoziţie logică ce ia valoarea $adevărat$ doar dacă sensurile de mers determinate de variabilele logice asociate autobuzelor sunt compatibile. Mai trebuie determinat într-un mod eficient dacă două clase de intervale de timp se intersectează. Aceasta rămâne ca temă cititorului.

Pentru orice două autobuze vom găsi care sunt sensurile de mers pentru ele astfel ca cele două autobuze să nu se întâlnească şi să provoace un accident. Pentru un sens fixat putem afla pentru un autobuz pe ce interval de timp va fi pe o anumită stradă. El va fi în general pe o stradă $(i, j)$ pe un interval de tipul $[t1 + k*T ... t2 + k*T]$ unde $t1$ este timpul din prima rută parcursă pentru a ajunge la $i$, $t2$ timpul pentru a ajunge la $j$, iar $T$ este durata totală a unei rute. Acum, pentru a determina dacă două autobuze se vor întâlni pe o rută $(i, j)$ trebuie ca ele să se deplaseze în sensuri opuse pe această rută, iar intervalele lor $[t1 + k*T1 ... t2 + k*T1]$ să se intersecteze cu intervalele $[tt1 + p*T2 ... tt2 + p*T2]$. Este clar acum că putem transforma problema într-o instanţă de $2-SAT$ prin maparea autobuzelor în variabile logice, a sensurilor de mers în valorile $adevărat$ şi $fals$, iar pentru orice pereche de autobuze să fie o propoziţie logică ce ia valoarea $adevărat$ doar dacă sensurile de mers determinate de variabilele logice asociate autobuzelor sunt compatibile. Mai trebuie determinat într-un mod eficient dacă două clase de intervale de timp se intersectează. Aceasta rămâne ca temă cititorului.

h2(#aladdin). 'Aladdin':problema/aladdin (Bursele Agora 2005/2006, Runda 1)

Pentru a vă familiariza cu subiectul prezentat în acest articol, vă propunem să încercaţi să rezolvaţi următoarele probleme:
# 'Excursion':http://www.oi.edu.pl/download/boi-2001.pdf - Baltic Olympiad in Informatics, 2001

# 'Peace Commision':http://www.oi.edu.pl/php/show.php?ac=e100000&module=show&file=zadania/oi8/spokojna - Polish Olympiad in Informatics, 2001

# 'Peaceful Commission':http://www.oi.edu.pl/php/show.php?ac=e100000&module=show&file=zadania/oi8/spokojna - Polish Olympiad in Informatics, 2001

h2(#bibliografie). Bibliografie:

# T. H. Cormen, C. E. Leiserson, R. R. Rivest - '_Introducere in Algoritmi_':http://zhuzeyuan.hp.infoseek.co.jp/ita/toc.htm

# T. H. Cormen, C. E. Leiserson, R. R. Rivest - '_Introducere în Algoritmi_':http://zhuzeyuan.hp.infoseek.co.jp/ita/toc.htm

# '_Satisfiability_':http://en.wikipedia.org/wiki/Satisfiability, Wikipedia
# '_BOI 2001 Competition Material_':http://www.oi.edu.pl/download/boi-2001.pdf
# '_CEOI 2002 Competition Material_':http://ics.upjs.sk/ceoi/Documents.html