Problemas interactivos en programación competitiva

Los Problemas Interactivos son aquellos problemas en los que nuestra solución o código interactúa con el juez en tiempo real. Cuando desarrollamos una solución para un problema interactivo, es posible que los datos de entrada proporcionados a nuestra solución no estén predeterminados, pero se construyen específicamente para ese problema. La solución realiza una serie de intercambios de datos con el juez y al final de la conversación el juez decide si nuestra solución fue correcta o no.
 

Adivinando el número (un problema interactivo)

En este problema el usuario tiene que adivinar el número durante una comunicación con el juez. Al usuario se le proporciona el límite superior e inferior y puede preguntarle al juez si un número es el número que debe adivinar. El juez responde con -1 si el número es menor que el número a adivinar o 1 si el número es mayor que el número a adivinar o 0 si es igual al número a adivinar.
 

Enfoque 1: adivinanzas lineales 
 

El usuario puede consultar al juez por todos los números entre el límite inferior y el límite superior para encontrar la solución. 
 

#include <bits/stdc++.h>
using namespace std;
 
int main()
{
    int lower_bound = 2;
    int upper_bound = 10;
 
    // Number to be guessed is 6
 
    // Iterating from lower_bound to upper_bound
    for (int i = lower_bound; i <= upper_bound; i++) {
        cout << i << endl;
 
        // Input the response from the judge
        int response;
        cin >> response;
 
        if (response == 0) {
            cout << "Number guessed is :" << i;
            break;
        }
    }
 
    return 0;
}
 
// This code is contributed by divyeshrabadiya07

import java.util.*;
class GFG {
    public static void main(String[] args)
    {
        Scanner sc1 = new Scanner(System.in);
        int lower_bound = 2;
        int upper_bound = 10;
 
        // Number to be guessed is 6
 
        // Iterating from lower_bound to upper_bound
        for (int i = lower_bound; i <= upper_bound; i++) {
            System.out.println(i);
 
            // Input the response from the judge
            int response = sc1.nextInt();
 
            if (response == 0) {
                System.out.println("Number guessed is :" + i);
                break;
            }
        }
    }
}

if __name__=='__main__':
    lower_bound = 2;
    upper_bound = 10;
 
    # Number to be guessed is 6
 
    # Iterating from lower_bound to upper_bound
    for i in range(lower_bound, upper_bound + 1):
        print(i)
 
        # Input the response from the judge
        response = int(input())
 
        if (response == 0):
            print("Number guessed is :", i, end = '')
            break;
 
            # This code is contributed by rutvik_56

using System;
class GFG
{
    public static void Main(string[] args)
    {      
        int lower_bound = 2;
        int upper_bound = 10;
  
        // Number to be guessed is 6
  
        // Iterating from lower_bound to upper_bound
        for (int i = lower_bound; i <= upper_bound; i++)
        {
            Console.WriteLine(i);
  
            // Input the response from the judge
            int response = int.Parse(Console.ReadLine());
  
            if (response == 0) {
                Console.WriteLine("Number guessed is :" + i);
                break;
            }
        }
    }
}
 
// This code is contributed by Pratham76

2
Number guessed is :2

Complejidad de tiempo: O(n)
 

Enfoque 2: Aplicación de la búsqueda binaria 
 

También podemos aplicar la búsqueda binaria de forma interactiva para encontrar la solución. Esta solución es eficiente en comparación con el enfoque anterior.
 

#include <bits/stdc++.h>
 
using namespace std;
 
int main(int argc, char** argv)
{
    int lower_bound = 2;
    int upper_bound = 10;
 
    while (lower_bound <= upper_bound)
    {
        int mid = (lower_bound + upper_bound) / 2;
        cout << mid << endl;
        int response;
        cin >> response;
 
        if (response == -1)
            lower_bound = mid + 1;
 
        else if (response == 1)
            upper_bound = mid - 1;
         
        else if (response == 0){
            cout << "Number guessed is :" + to_string(mid) << endl;
            break;
        }
    }
    return 0;
}
 
// This code is contributed by geeky01adarsh

import java.util.*;
class GFG {
    public static void main(String[] args)
    {
        Scanner sc1 = new Scanner(System.in);
        int lower_bound = 2;
        int upper_bound = 10;
 
        // Number to be guessed is 9
 
        // Applying Binary Search interactively
        while (lower_bound <= upper_bound) {
            int mid = (lower_bound + upper_bound) / 2;
 
            // Print the guessed number
            System.out.println(mid);
 
            // Input the response from the judge
            int response = sc1.nextInt();
 
            if (response == -1) {
                lower_bound = mid + 1;
            }
            else if (response == 1) {
                upper_bound = mid - 1;
            }
            else if (response == 0) {
                System.out.println("Number guessed is :" + mid);
                break;
            }
        }
    }
}

using System;
class GFG {
  static void Main() {
    int lower_bound = 2;
    int upper_bound = 10;
 
    // Number to be guessed is 9
 
    // Applying Binary Search interactively
    while (lower_bound <= upper_bound) {
        int mid = (lower_bound + upper_bound) / 2;
 
        // Print the guessed number
        Console.WriteLine(mid);
 
        // Input the response from the judge
        int response = Convert.ToInt32(Console.ReadLine());
 
        if (response == -1) {
            lower_bound = mid + 1;
        }
        else if (response == 1) {
            upper_bound = mid - 1;
        }
        else if (response == 0) {
            Console.WriteLine("Number guessed is :" + mid);
            break;
        }
    }
  }
}
 
// This code is contributed by divyesh072019

lower_bound = 2
upper_bound = 10
 
# Number to be guessed is 9
 
# Applying Binary Search interactively
while (lower_bound <= upper_bound) :
    mid = (lower_bound + upper_bound) // 2
 
    # Print guessed number
    print(mid)
 
    # Input the response from the judge
    response = int(input())
 
    if (response == -1) :
        lower_bound = mid + 1
     
    elif (response == 1) :
        upper_bound = mid - 1
     
    elif (response == 0) :
        print("Number guessed is :", mid)
        break

6
Number guessed is :6

Complejidad del tiempo: Paradigma del algoritmo O(logn) 
: divide y vencerás