← Volver a los ejercicios

UVa 11080, Place the Guards: dos colores por pedazo y el menor

El código de guardias corre sobre las dos entradas de la muestra y sobre tres casos más. En cada paso usted decide el color del cruce o qué pasa con la calle; al cerrar cada pedazo, cuántos guardias aporta; y al final del caso, qué número se imprime. Una respuesta equivocada dice qué se miró mal y se puede volver a intentar.
Enunciado y envío: https://vjudge.net/problem/UVA-11080. La página pide cuenta para ver el enunciado.

1. Lo que pide el juez

Una ciudad tiene v cruces, numerados de 0 a v − 1, con 1 ≤ v ≤ 200, y e calles, con 0 ≤ e ≤ 10000; cada calle une dos cruces y se recorre en los dos sentidos. Se ponen guardias en algunos cruces. Un guardia vigila su cruce, las calles que salen de él y los cruces del otro extremo de esas calles. Cada cruce y cada calle tienen que quedar vigilados, y ninguna calle puede tener guardias en sus dos extremos. Por cada caso se imprime el menor número de guardias que lo logra, o -1 si no se puede. La entrada empieza con el número T de casos; cada caso trae la línea v e y luego e líneas f t.

Entrada de muestra

Salida de muestra

2
-1

2. El código sobre cada caso

Se abre al terminar las preguntas.

Entrada del caso

Borde negro: el cruce u de la llamada de arriba. Calle ámbar: la que se está mirando. Calle roja: un choque. Al acertar la salida, los cruces cuadrados son los que llevan guardia.

3. Lo que cuesta y dónde deja de servir

Se abre al terminar las preguntas.

Con el tope del enunciado, v = 200 y e = 10000, ¿cuántas veces corre en total la línea 5, if color[v] == -1?

Los dos colores dan el mínimo porque la regla obliga a que cada calle tenga exactamente un extremo con guardia. En esta ciudad de dos centros unidos, cada uno con tres puntas, el código imprime 4. Si la regla no existiera y solo se pidiera que todo quede vigilado, ¿cuál sería el mínimo de guardias?

4. Para resolver sin ayuda

Se abre al terminar las preguntas.

Escriba la entrada de un caso con v = 9 y tres pedazos, uno de ellos un cruce aislado, cuya salida sea 4 y en el que sumar los cruces azules de cada pedazo dé 6. Diga qué cuenta deja cada pedazo y qué calle, agregada a su entrada, cambia la salida a -1.