Challenge: The Guessing Game

Lab Java Beginner 10 points

A secret number is between 1 and n. You always guess the middle: (lo + hi) / 2 (rounded down), and are told “higher” or “lower” until you hit it. Print every guess on one line, then the number of guesses.

Input

One line: n secret (1 ≤ secret ≤ n ≤ 10⁹).

Output

Line 1: the guesses separated by spaces. Line 2: <k> guesses.

Example

Input

100 37

Output

50 25 37
3 guesses

Sample input available Sample output available

Editor

Java

Hints

Start with lo = 1 and hi = n.

Use long: lo + hi can pass 2 billion when n is 10⁹.

Solution explanation

Even for a billion numbers you never need more than 30 guesses – that's O(log n).

Show solution

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long n = sc.nextLong(), secret = sc.nextLong();
        long lo = 1, hi = n;
        int count = 0;
        StringBuilder sb = new StringBuilder();
        while (true) {
            long guess = (lo + hi) / 2;
            count++;
            if (count > 1) sb.append(' ');
            sb.append(guess);
            if (guess == secret) break;
            if (guess < secret) lo = guess + 1;
            else hi = guess - 1;
        }
        System.out.println(sb);
        System.out.println(count + " guesses");
    }
}

Output

Answer