Rascacielos.

View as PDF

Submit solution

Points: 100 (partial)
Time limit: 1.0s
Memory limit: 256M

Author:
Problem type
Allowed languages
C, C++, Java, Pascal, Python

La ciudad de TeraCity tiene \(N\) rascacielos ubicados en una línea numerados convenientemente de izquierda a derecha desde \(0\) hasta \(N-1\). No existen otros rascacielos en la ciudad.

TeraCity está habitada por \(M\) criaturas místicas llamadas “nibble”. Los nibble están numerados de \(0\) hasta \(M-1\). El nibble \(i\) inicialmente reside en el rascacielos \(B_i\). El nibble \(i\) tiene un poder místico, representado con un entero positivo \(P_i\). Este poder místico los capacita para saltar entre rascacielos. En un salto simple, un nibble con superpoder p que se encuentra actualmente en el rascacielos b puede moverse al rascacielos \(b+p\)(si \(0 \leq b + p < N\)) o al rascacielos \(b-p\) (si \(0 \leq b \leq p < N\)).

El nibble \(0\) es el líder de todos ellos. Él tiene una noticia urgente para el nibble \(1\), y quiere que la noticia alcance al nibble \(1\) tan rápido como sea posible. Cualquier nibble que reciba la noticia puede hacer alguna de las siguientes acciones:

• Dar un salto para moverse a uno de los otros rascacielos.

• Comunicar la noticia a otro nibble que se encuentre en el mismo rascacielos.

Ayude a los nibble calculando el número mínimo total de saltos requeridos por todos los nibble para tratar de comunicar la noticia al nibble \(1\).

Entrada

La primera línea de la entrada contiene dos enteros \(N\) y \(M\). Cada una de las próximas \(M\) líneas contiene dos enteros \(B_i\) y \(P_i\).

Salida

Una línea simple conteniendo el número mínimo total de saltos, de lo contrario escriba \(-1\) si esto es imposible.

Ejemplo de Entrada Salida

5 3       
0 2
1 1
4 1

Ejemplo de Salida

5

Explicación

Este es una de las posibles maneras de comunicar la noticia utilizando \(5\) saltos:

• El nibble \(0\) salta al rascacielos \(2\) y entonces al rascacielos \(4\) (2 saltos).

• El nibble \(0\) comunica la noticia al \(2\).

• El nibble \(2\) salta al rascacielos \(3\), y entonces al rascacielos \(2\), y luego al rascacielos \(1\) (3 saltos).

• El nibble \(2\) comunica la noticia al nibble \(1\).

Subtareas

Para cada subtarea, \(0 \leq B_i < N\)

Subtarea 1 (10 puntos): \(1 \leq N \leq 10\), \(1 \leq P_i \leq 10\), \(2 \leq M \leq 3\)

Subtarea 2 (12 puntos): \(1 \leq N \leq 100\), \(1 \leq P_i \leq 100\), \(2 \leq M \leq 2,000\)

Subtarea 3 (14 puntos): \(1 \leq N \leq 2,000\), \(1 \leq P_i \leq 2,000\), \(2 \leq M \leq 2,000\)

Subtarea 4 (21 puntos): \(1 \leq N \leq 2,000\), \(1 \leq P_i \leq 2,000\), \(2 \leq M \leq 30,000\)

Subtarea 5 (43 puntos): \(1 \leq N \leq 30,000\), \(1 \leq P_i \leq 30,000\), \(2 \leq M \leq 30,000\)


Comments

There are no comments at the moment.