Formigues en un túnel P57037


Statement
 

pdf   zip

html

En un túnel de longitud L hi ha n formigues, que representem com punts. Les formigues es mouen a velocitat 1, ja sigui cap a l’esquerra o cap a la dreta. Si dues formigues es troben al mateix punt, xoquen i ambdues fan mitja volta. Quant de temps trigaran a sortir totes les formigues del túnel?

Entrada

L’entrada consisteix en diversos casos, cadascun amb n i L, seguides de les posicions de les formigues: n nombres enters entre 0 i L, tots diferents i en ordre. Segueixen n nombres més, indicant el sentit inicial del moviment de cada formiga: un 1 vol dir cap a la dreta, i un -1 vol dir cap a l’esquerra.

Sortida

Per a cada cas, cal escriure el temps necessari perquè totes les formigues surtin del túnel.

Observació

Com més eficient sigui la solució enviada, més punts obtindrà, fins a un màxim de 100.

Public test cases

  • Input

    1 10
2
1

1 10
2
-1

6 14
1 2 3 9 11 13
-1 -1 -1 1 1 1

5 12
0 5 6 8 10
1 1 -1 -1 -1

    Output

    8
2
5
12
    • Information
    Author
    Alex Alvarez
    Language
    Catalan
    Official solutions
    C++
    User solutions
    C++