Formigues en un túnel P57037


Statement
 

pdf   zip

thehtml

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++