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.
Submitting an official solution before solving the problem yourself is a bannable offence.
Author:
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