Adivina un número (Interactivo) P75481

ESTE PROBLEMA NO FUNCIONA

Haz un programa que juegue a “Adivina un número”, un juego donde deberás adivinar un número secreto.

A diferencia de la gran mayoría de los problemas de la OIE, donde tu programa debe calcular la salida correcta a una entrada dada, este problema es interactivo: la entrada que reciba tu programa cambiará en función de lo que tu programa haga.

Las normas de una partida de “Adivina un número” son las siguientes:

• Hay que adivinar un número secreto del 1 al 1000.
• En cada turno, tu programa puede preguntar ENTRE X Y, donde 1≤X≤Y≤ 1000.
• Puedes recibir tres respuestas: SI, si el número secreto está entre X y Y, ambos inclusive; MENOR si el número secreto es menor que X; MAYOR si el número secreto es mayor que Y.
• Cuando tu programa descubra cuál es el número secreto, debe escribir ES X.

Tu programa jugará exactamente 1000 partidas de “Adivina un número”, donde se le pedirá que adivine números distintos entre 1 y 1000 (es lícito usar esta información para encontrar el número secreto haciendo menos preguntas de las que serían necesarias).

Entrada/Salida

Cada partida empieza con la línea PARTIDA. Tu programa debe escribir entonces preguntas de la forma ENTRE X Y, cada una de las cuales recibirá un respuesta de la forma SI, MENOR o MAYOR. Cuando sepas cuál es el número secreto X, escribe ES X. Tu programa debe escribir un salto de línea depués de cada respuesta. Si usas valores inválidos de X o Y, o el número secreto que respondes no es correcto, tu programa será considerado erróneo. Tu programa debe finalizar cuando, al empezar una partida, la primera línea que lea no sea PARTIDA.

Tu programa dispone de 5 segundos de CPU para resolver las 1000 partidas.

Ejemplo

A modo de ejemplo, mostramos un posible intercambio de dos partidas (en vez de las 1000 que tendrán lugar en el juez on-line):

> PARTIDA
< ENTRE 1 100
> MAYOR
< ENTRE 101 200
> MAYOR
< ENTRE 201 300
> SI
< ENTRE 201 210
> MAYOR
< ENTRE 211 220
> MAYOR
< ENTRE 221 230
> MAYOR
< ENTRE 231 240
> SI
< ENTRE 231 231
> MAYOR
< ENTRE 232 232
> SI
< ES 232
> PARTIDA
< ENTRE 1 100
> SI
< ENTRE 1 10
> SI
< ENTRE 1 1
> SI
< ES 1
> FINAL 12
La última línea (FINAL 12) contiene el número de preguntas que tu programa ha realizado, en función de las cuales será puntuado.

Para poder probar que tu programa funciona correctamente antes de enviarlo al juez on-line, puedes usar el archivo que acompaña a este enunciado en la web de la Olimpiada Informática. Después de descargar y descomprimir tal archivo, podrás usar el comando

./adivina3.exe entrada.txt

para experimentar por tu mismo la entrada y la salida, y el comando

python conn.py ./programa.exe entrada.txt

para probar tu programa ./programa.exe contra un ejemplo de entrada entrada.txt. Encontrarás varios ejemplos de entradas, incluyendo un entrada-juez.txt que será semejante al que usará el juez para puntuar tu programa (este archivo y el del juez hacen ambos 1000 preguntas, pero en distinto orden).

Puntuación

Tu programa jugará exactamente 1000 partidas, donde deberá adivinar 1000 números del 1 al 1000, sin que haya números repetidos. La puntuación de tu programa dependerá del número de intentos que necesite para resolver las 1000 partidas:

• 0–20 Puntos. Requerir entre 50000 y 10000 intentos.
• 20–50 Puntos. Requerir entre 10000 y 7000 intentos.
• 50–80 Puntos. Requerir entre 7000 y 5600 intentos.
• 80–100 Puntos. Requerir entre 5600 y 5475 intentos.

La puntuación será siempre un número entero de puntos, y se calculará haciendo el promedio correspondiente, redondeando hacia abajo. Por ejemplo, un programa que acabe con 8000 intentos recibirá 40 puntos.

Prueba: Final OIE 2011 (Lunes)
Autor: Omer Giménez