/******************************************************************************
 *  Compilation:  javac QuestionsTwenty.java
 *  Execution:    java QuestionsTwenty
 *  Dependencies  StdIn.java
 *
 *  Think of an integer between 0 and 1000000.
 *  Truthfully answer 'true' or 'false' to each question I ask.
 *
 *  Q1: Is your number <= 500000?
 *  true
 *  Q2: Is your number <= 250000?
 *  true
 *  Q3: Is your number <= 125000?
 *  true
 *  Q4: Is your number <= 62500?
 *  false
 *  Q5: Is your number <= 93750?
 *  true
 *  Q6: Is your number <= 78125?
 *  false
 *  Q7: Is your number <= 85938?
 *  true
 *  Q8: Is your number <= 82032?
 *  true
 *  Q9: Is your number <= 80079?
 *  false
 *  Q10: Is your number <= 81056?
 *  true
 *  Q11: Is your number <= 80568?
 *  true
 *  Q12: Is your number <= 80324?
 *  false
 *  Q13: Is your number <= 80446?
 *  true
 *  Q14: Is your number <= 80385?
 *  true
 *  Q15: Is your number <= 80355?
 *  true
 *  Q16: Is your number <= 80340?
 *  false
 *  Q17: Is your number <= 80348?
 *  true
 *  Q18: Is your number <= 80344?
 *  true
 *  Q19: Is your number <= 80342?
 *  true
 *  Q20: Is your number <= 80341?
 *  false
 *
 *  Your integer is 80342.
 *
 ******************************************************************************/

public class QuestionsTwenty {

    public static void main(String[] args) {
        int lo = 0, hi = 1000000;
        StdOut.println("Think of an integer between " + lo + " and " + hi + ".");
        StdOut.println("Truthfully answer 'true' or 'false' to each question I ask.");
        StdOut.println();

        for (int i = 1; lo < hi; i++) {

            // invariant:  number must be in the interval [lo, hi]
            int mid = lo + (hi - lo) / 2;
            StdOut.print("Q" + i + ": ");
            StdOut.println("Is your number <= " + mid + "?");
            boolean response = StdIn.readBoolean();
            if (response) hi = mid;
            else          lo = mid + 1;
        }

        StdOut.println("Your integer is " + lo + ".");
        StdOut.println();
    }

}