whereswaldo
EGOI Practice Session Tasks
Spanish (ESP)¿Dónde está Wally?
Nombre del problema

whereswaldo

Límite de tiempo

11 segundos

Límite de memoria

1 gigabyte

Hay una permutación oculta P0 , P1 , ..., PN −1 de longitud N , y se garantiza que esta ha sido
generada de manera uniformemente aleatoria. La permutación contiene los números 1, 2, 3, ..., N
una única vez cada uno, en un cierto orden desconocido.
Puedes elegir dos posiciones l y r, para hacer preguntas de la forma: “¿Cuál es la suma dePl + Pl+1 + ⋯ + Pr ?”Tu objetivo es encontrar la posición del número 1 en P usando el mínimo número de preguntas
posibles. Se te puntuará dependiendo del número de preguntas usadas.

Interacción
En primer lugar, tu programa debe leer dos enteros en la misma línea, T y N .

T es el número de rondas en las que tu programa será puesto a prueba, y N es la longitud de P .
Después de esto hay T rondas:
Cuando una ronda comienza puedes empezar a hacer preguntas. Imprime una línea con “? a b”
para preguntar la suma de los números entre las posiciones a y b incluyendo ambos extremos (0 ≤ a ≤ b ≤ N − 1).
Después de cada pregunta tu programa debe leer un entero, la suma de los números en elintervalo.
Una vez que hayas encontrado la posición de 1, imprime una linea de la forma “! i”, donde i es elíndice tal que Pi = 1. Después de imprimir esto, la siguiente ronda empezará.
Asegúrate de hacer ﬂush después de hacer una pregunta, o tu programa podría recibir elveredicto Time Limit Exceeded.

whereswaldo (1 of 3)

En Python, print() hace ﬂush automáticamente. En C++, cout << endl; también hace ﬂush
además de añadir un salto de línea; si usas printf, usa fflush(stdout).

Restricciones y Puntuación
Tu programa será puesto a prueba en un solo testcase, con N = T = 1000. Se garantiza que lapermutación en cada ronda está generada aleatoriamente.
Si tu solución da una respuesta errónea en cualquiera de las rondas, tu envío recibirá el veredicto
Wrong Answer.
En caso contrario, la puntuación se calcula de la siguiente manera:
Mpuntuación = min (220 − 2500, 100) puntos,

donde M es el número de preguntas que tu programa ha usado en total en las T rondas.
La puntuación se redondeará al entero más cercano. Si la puntuación se hace negativa contará
como cero puntos.
Por tanto, si usas más de 550 000 preguntas recibirás 0 puntos, y si usas 300 000 o menos
preguntas recibirás 100 puntos. Entre estos valores, tu puntuación aumenta linealmente.

Herramienta de testing
Para facilitarte el testing de tu solución, tienes una sencilla herramienta que puedes descargar. Ver“attachments” al ﬁnal de la página del problema en kattis. El uso de la herramienta es opcional, yse te permite modiﬁcarla. Ten en cuenta que el programa oﬁcial con el que calcula laspuntuaciones kattis no es el mismo que esta herramienta.
Ejemplo de uso (con T=1000, N=10):
Para programas en Python, digamos solution.py (habitualmente ejecutado como pypy3solution.py):
python3 testing_tool.py pypy3 solution.py <<<"1000 10"
Para programas en C++, primero compilamos (por ejemplo con g++-std=gnu++17

solution.cpp -o solution.out) y luego ejecutamos:
python3 testing_tool.py ./solution.out <<<"1000 10"

Testcase de ejemplo
whereswaldo (2 of 3)

En el testcase de ejemplo, T = 2 y N = 10. En la primera de estas dos rondas, digamos que lapermutación oculta es “6 10 8 7 9 1 2 4 5 3”. La primera pregunta ? 0 9 pregunta la suma
de todos los números, que es 55, y la segunda pregunta ?

04 pregunta por

6 + 10 + 8 + 7 + 9 = 40.
grader output

tu output

2 10?0955?04
40?55
1!5?00
1!0whereswaldo (3 of 3)