Problemas Interactivos en Programación Competitiva | conjunto 2

La introducción a los problemas interactivos en la programación competitiva ya se trató en el artículo anterior . En este artículo, se discute otro problema basado en el mismo concepto.

Suponga que el juez tiene una array ordenada oculta (lo que significa que el usuario no puede acceder a ella).

El usuario (es decir, usted) necesita saber si un elemento dado VAL se encuentra en ese espacio de array ordenado dado por los índices de inicio y finalización como INICIO y FIN respectivamente.
Para que el usuario sepa si VAL existe o no en el espacio de array dado, el usuario debe interactuar con el juez para que el usuario pueda conocer el valor en un índice particular con la ayuda del juez.

Tomemos un ejemplo:
el usuario necesita encontrar VAL = 2 entre START = 0 y END = 5 .
El juez almacena la array ordenada arr[] = {1, 2, 3, 4, 5, 6} (indexación basada en 0).
Ahora el usuario puede dar entrada como índices al juez y el juez tiene que responder al usuario con el valor en ese índice.
Básicamente, para algún índice de entrada del usuario, el juez responde con el valor en ese índice de entrada y este proceso continúa hasta que el usuario descubre finalmente si el valor VAL está en la array o no.

El usuario intenta realizar una búsqueda binaria mientras se ordena la array. Aquí hay una parte del programa que el usuario usa al implementar la búsqueda binaria como:

TASK
{
    if VAL is equal to Value_Given_By_Judge
        Prints "Value exist" and return 
    else if VAL is less than A[mid]
        end = mid-1
    else if VAL is greater than A[mid]
        start = mid+1
}

Dos variables utilizadas por el usuario son start = 0 y end = 5

Ocurre la siguiente interacción:

User calculates mid = (start + end) / 2 = 2;
Judge outputs 3 // Value at index 2
User updates mid = (start + end) / 2 = 4
Judge OUTPUT : 5 // Value at index 4
User again performs TASK and prints "Value exists" 
and returns as it finds VAL  

Por lo tanto, para interactuar con el juez en línea, se requiere que el juez en línea tome la entrada del usuario y luego proporcione alguna salida correspondiente que pueda tomarse como entrada. Es similar a imprimir entrada/salida en la pantalla de salida, pero en algunos lenguajes como C++, Python, Java, etc., imprimir en la pantalla de salida es un proceso costoso/que consume mucho tiempo, por lo que lo que sucede es que toda la salida del programa se almacena en un área de búfer. y luego, después de que finaliza el programa, todos los valores del búfer se imprimen en la pantalla de salida por completo. Pero esto puede crear un problema con los problemas interactivos porque el juez en línea solo tomará información de la pantalla de salida (y no del búfer), por lo que se requiere transferir el contenido del búfer a la pantalla de salida real. Esta transferencia en realidad se llama empujarya que estamos obligando al búfer a cargar su contenido en la pantalla de salida.

Los comandos utilizados para empujar son los siguientes:

1. C++: flush(salida estándar)
2. Java: System.out.flush()
3. Python:
   importar sistema
   sys.stdout.flush()

Las siguientes preguntas se pueden practicar para desarrollar algunas habilidades de problemas interactivos y familiarizarse con su funcionamiento.
Problema 1
Problema 2