Embús
Veure com a PDF
A la nostra estimada Ciutat Linial els embussos son un greu problema. Recordem que és una ciutat amb un únic carrer que el travessa d'un extrem a un altre i on només hi cap un cotxe, de forma que si dos cotxes es troben de cara no hi ha forma de maniobrar per poder continuar endavant.
Com que tots els cotxes son del mateix model (negres i d'1 metre de llarg), han provat la següent solució:
- tots els cotxes circulen a una velocitat constant d'1 metre per segon
- si dos cotxes es toquen de cara, els conductors aturen els vehicles, se'ls intercanvien i fan mitja volta. Aquesta operació l'han perfeccionat de forma que la fan en un temps rècord d'1 segon.
Entrada
L'entrada comença amb el nombre de casos a processar. El màxim de casos a processar serà de 100.
Cada cas conté dues línies. La primera conté dos números: la llargada del carrer (entre 1 i 1.000.000) i el nombre de vehicles (entre 1 i 100.000). La segona línia conté la posició on es troben els vehicles comptant des de l'inici del carrer. No sabem la direcció en la que circulen cadascun dels cotxes.
Sortida
Per a cada cas caldrà indicar dos números: el temps mínim i el temps màxim que podem trigar a deixar el carrer net de vehicles.
Exemple d'Entrada
2
10 3
1 5 8
127 5
32 9 110 80 43
Exemple de Sortida
5 9
47 118
Comentaris