A little boy named Aehaan is playing a game with an AI program. In this game, the program first chooses a secret number and Aehaan has to guess the number. The program follows certain rules based on Aehaan's guesses:

If Aehaan's guess is correct, the program will print correct and the game will end.
If Aehaan's guess is smaller than the secret number, the program will print low.
If Aehaan's guess is greater than the secret number, the program will print high.
Aehaan has a limit of 30 guesses, and if he exceeds this limit, the program will print too many tries and the game will end.

Your task is to help Aehaan by writing a program that can solve the game.

Input

Input starts with an integer n (1 ≤ n ≤ 10⁹) that denotes that the AI program has chosen an integer between 1 and n.

You need to print a series of guesses in standard output each on a single line in format: guess k, where k is the guessed integer.

After a guess is printed, you will receive one line in standard input containing low, high, correct or too many tries as described above. If it's low or high, you should keep guessing. If it's correct or too many tries; indicates the end of the session.

Output

The validator program for this problem reads an integer n and the guessed integer p from the judge input file.

Then for each guess k printed by the user program, it compares k with p and writes a single line with the appropriate status: low, high, correct or too many tries.

Sample

Sample Input	Sample Output
Click to copy 10 7	Click to copy

Sample

Sample Input	Sample Output
Click to copy 100 43	Click to copy

Interactive Search

Problem

This is an easy interactive problem . You will be a value n and you have to find the secret number which is within 1 to n in 30 tries . You will be given a response high or low or correct . If you guess the number in 30 tries you will get AC otherwise WA .

Solution

The maximum value of n is 1e9 so we can't use linear search .

As the number of tries is 30 we can use binary search to find the number because to find a number within a range of 1 to 1e9 it will take binary search maximum log2(1e9) which is okay for our problem.

So we will use binary search to find the number .

 1. We will take the input of `n` and set the `low` as `1` and `high` as `n`. 
 2. Then we will find the mid value and print it as guess .
 3. Then we will take the response as input . 
 5. If the response is `high` then we will set `high` as `mid - 1` .
 6. If the response is `low` then we will set `low` as `mid + 1` .
 7. If the response is `correct` then we will return . 
 8. If the count is greater than `30` then we will print `too many tries` and return .

You can learn more about binary search from

 Time Complexity : O(log(n))
 Space Complexity : O(1)

CPP


#include <bits/stdc++.h>

using namespace std;

int main()
{

    int low = 1, high = 100000;
    // Taking the value of n as input and setting it as high as it will be the maximum value
    cin >> high;


    // To keep track of the number of tries
    int count = 0;

    // Binary search
    while (low <= high)
    {
        // Finding the mid value
        int mid = (low + high) >> 1;
        // Printing the guess
        cout << "guess " << mid << endl;


        // Taking the response as input
        string response;
        cin >> response;

        // Checking the response
        if (response == "correct")
            return 0;
        else if (response == "high")
            high = mid - 1;
        else if (response == "low")
            low = mid + 1;

        // Increasing the count
        count++;

        // If the count is greater than 30 then printing too many tries and returning
        if (count >= 30)
        {
            cout << "too many tries" << endl;
            return 0;
        }
    }

    return 0;
}

Tutorial source

Input

Output

Sample

Sample

Total Submissions

Users Tried

Users Solved

Interactive Search

Problem

Solution

CPP