19 jul 2008

Salvando el universo

Salvando el universo, es el título del primer problema propuesto en la ronda de calificación del Google Code Jam de este año, esta ronda culminó el día jueves 18 a las 06:00 p.m. con un total de 6773 clasificados (25 puntos como mínimo). El número total de participantes que remitieron al menos una respuesta correcta (5 puntos) fue de 7154.

El primer lugar lo obtuvo el participante cuyo nick es rem al totalizar 75 puntos en una hora con 18 minutos, la respuesta más rápida también fue de rem y fue remitida en tan solo 9 minutos con 16 segundos... increíble!!

Bueno, bueno.... basta ya de tantas estadísticas, el problema en cuestión se encuentra traducido líneas abajo, si eres un entusiasta de la programación seguramente intentarás resolverlo (obviamente, para salvar el universo) en tal caso espero un comentario tuyo en el que me cuentes como te fué.

EL PROBLEMA


Una leyenda urbana cuenta que si accedes a la página principal de Google y realizas la búsqueda de la palabra "Google", el universo se autodestruirá. Tenemos un secreto que compartir contigo... es cierto!. Por favor no lo intentes y no le digas a nadie. Muy bien, tal vez no. Solamente estamos bromeando.

Lo mismo no es muy cierto para un universo muy pero muy lejano. En aquel universo, si realizas una búsqueda en un motor de búsqueda por su propio nombre, aquel universo se autodestruirá.

Para evitar esto, se ha ideado una solución interesante. Todas las consultas realizadas en aquel universo serán combinadas y transmitidas a un sistema central que decidirá cual de las consultas se realizarán en cual motor de búsqueda. El sistema central enviará una serie de consultas a un motor de búsqueda, y puede cambiar de motor de búsqueda cuando sea necesario. Las consultas serán procesdas en el orden que son recibidas. El sistema central nunca deberá enviar una consulta a un motor de búsqueda que coincida con su nombres. Para reducir los costos el número de cambios de motor de búsqueda debe ser minimizado.

Tu tarea es indicarnos cuántas veces deberá cambiar de motor de búsqueda el sistema central, asumiendo que lo programamos de manera óptima.

ENTRADA
La primera línea del archivo de entrada contiene el número de casos, N. N casos siguientes.
Cada caso inicia con un número S -- el número de motores de búsqueda. Cada una de las siguientes S líneas contienen el nombre de un motor de búsqueda. El nombre cada motor de búsqueda no puede ser mayor a cien caracteres y contendrá solamente letras mayúsculas, minúsculas, espacios y números. No habrán dos motores de búsqueda con el mismo nombre.
La siguiente línea contiene un número Q -- el número de consultas de entrada. Las siguientes Q líneas contendrá cada una una consulta. Cada consulta será el nombre de un motor de búsqueda en el caso actual.

SALIDA

Para cada caso de entrada, la salida debe ser:

Case #X: Y

donde X es el número de casos de prueba e Y es el número de cambios de motor de búsqueda. No cuente la elección inicial de un motor de búsqueda como un cambio.

EJEMPLO:
Entrada
2
5
Yeehaw
NSM
Dont Ask
B9
Googol
10
Yeehaw
Yeehaw
Googol
B9
Googol
NSM
B9
NSM
Dont Ask
Googol
5
Yeehaw
NSM
Dont Ask
B9
Googol
7
Googol
Dont Ask
NSM
NSM
Yeehaw
Yeehaw
Googol

Salida
Case #1: 1
Case #2: 0

En el primer caso, una posible solución es iniciar utilizando el motor Dont Ask, y cambiar a NSM luego de la consulta número 8.
Para el segundo caso, se puede utilizar B9, y no se requiere realizar ningún cambio.

5 comentarios:

Unknown dijo...

Estoy dsd la 1:00 am, pero porfin acabo XD, aun no entiendo muy bien porque debo agregar el ultimo motor de busqueda despues de "borrar" la lista y aumentar un cambio.

Si puede, dele una vista a mi codigo lo voy a colgar en esta direccion:
faridescate.4shared.com

Salu2 y espero seguir en contacto XD
Farid

Arnaldo dijo...

Hola Farid,
Puedes tomarlo así: para realizar una búsqueda siempre debes tener al menos un motor de búsqueda, si no dejas al menos uno no tendría lógica seguir buscando.
Y por otro lado, justamente cuando te haz quedado sin motores de búsqueda es la señal que debes cambiar de motor.
Ingresé a la dirección que pusiste pero no pude ver el código puede ser que no lo hayas puesto como público, lo mismo que me sucede a mí muy a menudo :D
Por cierto yo tb estoy de amanecida, lo intenté en la ronda 1C (4 a 6 am) del GCJ pero un error y unos minutos no me dejaron avanzar, de todo modos ha sido muy interesante.
Seguiremos trabajando,
Saludos!

Unknown dijo...

Si ya me di cuenta :S, ya lo puse como publico ahora si lo puede revisar XD, voy a intentar hacer el de los trenes... ya le cuento como me fue. Ya entendi lo de agregar el motor, gracias.

Cuidese, nos vemos ;).

Unknown dijo...

Otra vez molestandolo XD, ya termine el 2do ejercicio :O, me gustaria que le diera una revisada lo subi a la pagina faridescate.4shared.com ahora si no me olvido de ponerle publico...
No hay como la tranquilidad de la madrugada :D, ahora si a dormir.

Salu2
Farid

Arnaldo dijo...

Ok, le daré una mirada pero antes deberías remitir tu archivo de salida al GCJ para que valide tu respuesta.