Editorial for Guess the Number.


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: Marco_Escandon

Este es un problema clásico de búsqueda binaria, lo más complicado para algunos podría ser la interacción. A continuación, se muestran varios ejemplos de solución en C++.

Solución #1:

#include <bits/stdc++.h>
using namespace std;
int main() {
    long long h = 2000000000;
    long long l = 1;
    long long m = (l + h) / 2;
    cout << m << '\n';
    cout.flush();
    string status;
    cin >> status;
    while (status != "=") {
        if (status == ">") {
            h = m - 1;
            m = (l + h) / 2;
        } else if (status == "<") {
            l = m + 1;
            m = (l + h) / 2;
        }
        cout << m << '\n';
        cout.flush();
        cin >> status;
    }
    return 0;
}

Solución #2:

Para esta solución usaremos endl, este casi siempre es más lento en los problemas normales entre otras cosas porque hace flush en la salida por tanto si lo usamos no es necesario volver a hacer flush:

#include <bits/stdc++.h>
using namespace std;
int main() {
    long long h = 2000000000;
    long long l = 1;
    long long m = (l + h) / 2;
    cout << m << endl;
    string status;
    cin >> status;
    while (status != "=") {
        if (status == ">") {
            h = m - 1;
            m = (l + h) / 2;
        } else if (status == "<") {
            l = m + 1;
            m = (l + h) / 2;
        }
        cout << m << endl;
        cin >> status;
    }
    return 0;
}

Solución #3:

En el caso de este problema el grader esta diseñado para que no sea necesario hacer flush en la salida por tanto la siguiente solución también será aceptada.

#include <bits/stdc++.h>
using namespace std;
int main() {
    long long h = 2000000000;
    long long l = 1;
    long long m = (l + h) / 2;
    cout << m << '\n';
    string status;
    cin >> status;
    while (status != "=") {
        if (status == ">") {
            h = m - 1;
            m = (l + h) / 2;
        } else if (status == "<") {
            l = m + 1;
            m = (l + h) / 2;
        }
        cout << m << '\n';
        cin >> status;
    }
    return 0;
}

Comments

There are no comments at the moment.