Number Guessing
Code Jam
Problem
This problem is a well-known classic; we present it primarily as an opportunity for you to try out the interactive judging system.
Input and Output
This problem is interactive, which means that the concept of input and output are different than in standard problems. You will interact with a separate process that both provides you with information and evaluates your responses. All information comes into your program via standard input; anything that you need to communicate should be sent via standard output.
Remember that many programming languages buffer the output by default, so make sure that your output actually goes out (for instance, by flushing the buffer) before blocking to wait for a response. Anything your program sends through standard error is ignored, but it might consume some memory and be counted against your memory limit, so do not overflow it. To help you debug, a local testing tool script (in Python) is provided at the very end of the problem statement.
Initially, your program should read a single line containing a single integer T indicating the number of test cases. Then, you need to process T test cases.
For each test case, your program will read a single line with two integers A and B, representing the exclusive lower bound and inclusive upper bound, as described above. In the next line, you will read a single integer N, representing the maximum number of guesses you can make. Your program will process up to N exchanges with our judge.
For each exchange, your program needs to use standard output to send a single line with one integer Q: your guess. In response to your guess, the judge will print a single line with one word to your input stream, which your program must read through standard input. The word will be CORRECT if your guess is correct, TOO_SMALL if your guess is lesser than the correct answer, and TOO_BIG if your guess is greater than the correct answer. Then, you can start another exchange.
If your program gets something wrong (e.g., wrong output format, or out-of-bounds values), the judge will send WRONG_ANSWER to your input stream and it will not send any other output after that. If your program continues to wait for the judge after receiving WRONG_ANSWER, your program will time out, resulting in a Time Limit Exceeded error. Notice that it is your responsibility to have your program exit in time to receive the appropriate verdict (Wrong Answer, Runtime Error, etc.) instead of a Time Exceeded error. As usual, if the total time or memory is exceeded, or your program gets a runtime error, you will receive the appropriate verdict.
If your test case is solved within N tries, you will receive the CORRECT message from the
judge, as mentioned above, and then continue to get input (a new line with two integers A and B, etc.) for the next test case. After N tries, if the test case is not solved, the judge will print WRONG_ANSWER and then stop sending output to your input stream.
You should not send additional information to the judge after solving all test cases. In other words, if your program keeps printing to standard output after receiving CORRECT for the last test case, you will get a Wrong Answer judgment.
Limits
Time limit: 10 seconds per test set.
Memory limit: 1GB.
Test set 1 (Visible)
Test set 2 (Hidden)
Sample Interaction
t = readline_int() // reads 3 into t a, b = readline_two_int() // reads 0 into a and 30 into b; note that 0 30 is one line n = readline_int() // reads 30 into n printline 30 to stdout // guesses 30 flush stdout string s = readline() // because 30 > 9, reads TOO_BIG into s printline 5 to stdout // guesses 5 flush stdout s = readline() // reads TOO_SMALL into s since 5 < 9 printline 10 to stdout // guesses 10 flush stdout s = readline() // reads TOO_BIG into s since 10 > 9 printline 9 to stdout // guesses 9 flush stdout s = readline() // reads CORRECT into s
a, b = readline_two_int() // reads 0 into a and 30 into b; note that 0 30 is one line n = readline_int() // reads 30 into n printline 31 to stdout // guesses 31 flush stdout string s = readline() // reads WRONG_ANSWER a, b = readline_two_int() // tries to read for the third test case but hangs since // judge has stopped sending info to stdin
a, b = readline_two_int() // reads 0 into a and 30 into b; note that 0 30 is one line n = readline_int() // reads 30 into n printline 31 to stdout // guesses 31 flush stdout string s = readline() // reads WRONG_ANSWER exit // receives a Wrong Answer judgment
"""Number Guessing interactive judge.""" # Usage: `testing_tool.py test_number`, where the argument test_number is # either 0 (first test set) or 1 (second test set). from __future__ import print_function import random import sys # Use raw_input in Python2. try: input = raw_input except NameError: pass _ERROR_MSG_EXTRA_NEW_LINES = "Input has extra newline characters." _ERROR_MSG_INCORRECT_ARG_NUM = "Input does not have exactly 1 token." _ERROR_MSG_INVALID_TOKEN = "Input has invalid token." _ERROR_MSG_OUT_OF_RANGE = "Input is out of range." _ERROR_MSG_READ_FAILURE = "Read for input fails." _CORRECT_MSG = "CORRECT" _QUERY_LIMIT_EXCEEDED_MSG = "Query Limit Exceeded." _TOO_BIG_MSG = "TOO_BIG" _TOO_SMALL_MSG = "TOO_SMALL" _WRONG_ANSWER_MSG = "WRONG_ANSWER" CASES = ([1, 30], [1, 42, 10**9]) # fill in your own cases B_VALUE = (30, 10**9) def Output(line): print(line) sys.stdout.flush() class JudgeSingleCase: def __init__(self, answer, lo, hi, max_num_tries): self.__answer = answer # the number that is being guessed self.__lo = lo # answer > lo self.__hi = hi # answer <= hi self.__max_num_tries = max_num_tries # max number of tries def ReadValues(self, response): """Parses contestant's input. Parse contestant's input which should be one integer, within (lo, hi]. Args: response: (str) one-line input given by the contestant. Returns: (int, string): the integer guess sent by the contestant, and the error string in case of error. If the parsing succeeds, the return value should be (int, None). If the parsing fails, the return value should be (None, str). """ if ("\n" in response) or ("\r" in response): return (self.__lo, _ERROR_MSG_EXTRA_NEW_LINES) tokens = response.split() if len(tokens) != 1: return (self.__lo, _ERROR_MSG_INCORRECT_ARG_NUM) token = tokens[0] if len(token) > len(str(self.__hi)): return (self.__lo, _ERROR_MSG_INVALID_TOKEN) try: guess = int(token) except Exception: return (self.__lo, _ERROR_MSG_INVALID_TOKEN) if (guess <= self.__lo) or (guess > self.__hi): return (self.__lo, _ERROR_MSG_OUT_OF_RANGE) return (guess, None) def Judge(self): """Judge one single case; should only be called once per test case. Returns: An error string, or None if the attempt was correct. """ for _ in range(self.__max_num_tries): try: contestant_input = input() except Exception: return _ERROR_MSG_READ_FAILURE guess, err = self.ReadValues(contestant_input) if err is not None: return err if guess == self.__answer: Output(_CORRECT_MSG) return None elif guess < self.__answer: Output(_TOO_SMALL_MSG) else: Output(_TOO_BIG_MSG) return _QUERY_LIMIT_EXCEEDED_MSG def RunCases(B, cases): """Sends input to contestant and judges contestant output. Returns: An error string, or None if the attempt was correct. """ A = 0 N = 30 T = len(cases) Output(T) for case_number, answer in enumerate(cases, 1): Output("{} {}".format(A, B)) Output(N) single_case = JudgeSingleCase(answer, A, B, N) err = single_case.Judge() if err is not None: return "Case #{} ({}) failed:\n{}".format(case_number, answer, err) # Ensure there is no additional output beyond the testcases. try: response = input() except EOFError: return None except Exception: # pylint: disable=broad-except return "Exception raised while reading input after all cases finish." return "Additional input after all cases finish: {}".format(response[:1000]) def main(): random.seed(30) assert len(sys.argv) == 2 index = int(sys.argv[1]) cases = CASES[index] random.shuffle(cases) b = B_VALUE[index] result = RunCases(b, cases) if result is not None: print(result, file=sys.stderr) Output(_WRONG_ANSWER_MSG) sys.exit(1) if __name__ == "__main__": main()
CORRECT. CORRECT is received.read t
for p in $(seq 1 $t); do
read -a line
a=${line[0]}
b=${line[1]}
read n
head=$(( a+1 ))
tail=$b
while true; do
mid=$(( (head+tail)/2 ))
echo $mid
read s
if [[ "$s" == "CORRECT" ]]; then
break
elif [[ "$s" == "TOO_BIG" ]]; then
tail=$(( mid - 1 ))
elif [[ "$s" == "TOO_SMALL" ]]; then
head=$(( mid + 1 ))
else
# Wrong answer; exit to receive Wrong Answer judgment
exit 0
fi
done
done
#include <stdio.h> #include <string.h> int main() { int T; scanf("%d", &T); for (int id = 1; id <= T; ++id) { int A, B, N, done = 0; scanf("%d %d %d", &A, &B, &N); for (++A; !done;) { int mid = A + B >> 1; char result[32]; printf("%d\n", mid); fflush(stdout); scanf("%s", result); if (!strcmp(result, "CORRECT")) done = 1; else if (!strcmp(result, "TOO_SMALL")) A = mid + 1; else B = mid - 1; } } return 0; }
using System; public class Solution { static public void Main () { int num_test_cases = Convert.ToInt32(Console.ReadLine()); for (int i = 0; i < num_test_cases; ++i) { string[] lo_hi_s = Console.ReadLine().Split(' '); int[] lo_hi = Array.ConvertAll(lo_hi_s, int.Parse); int num_tries = Convert.ToInt32(Console.ReadLine()); int head = lo_hi[0] + 1, tail = lo_hi[1]; while (true) { int m = (head + tail) / 2; Console.WriteLine (m); string s = Console.ReadLine(); if (s == "CORRECT") break; if (s == "TOO_SMALL") { head = m + 1; } else { tail = m - 1; } } } } }
#include <iostream> #include <string> int main() { int num_test_cases; std::cin >> num_test_cases; for (int i = 0; i < num_test_cases; ++i) { int lo, hi; std::cin >> lo >> hi; int num_tries; std::cin >> num_tries; int head = lo + 1, tail = hi; while (true) { int m = (head + tail) / 2; std::cout << m << std::endl; std::string s; std::cin >> s; if (s == "CORRECT") break; if (s == "TOO_SMALL") head = m + 1; else tail = m - 1; } } return 0; }
package main import ( "fmt" "strings" ) func main() { var t int fmt.Scanf("%d", &t) for i := 1; i <= t; i++ { var a, b, n int fmt.Scanf("%d %d", &a, &b) a = a + 1 fmt.Scanf("%d", &n) for { m := (a + b) / 2 fmt.Println(m) var str string fmt.Scanf("%s", &str) if strings.EqualFold(str, "CORRECT") { break } else if strings.EqualFold(str, "TOO_SMALL") { a = m + 1 } else if strings.EqualFold(str, "TOO_BIG") { b = m - 1 } } } }
import System.IO getNum :: IO Int getNum = do x <- getLine let n = read x :: Int return n bisect :: Int -> Int -> Int -> String -> IO () bisect a b m "CORRECT" = return () bisect a b m "TOO_SMALL" = singleCase (m+1) b bisect a b m "TOO_BIG" = singleCase a (m-1) query :: Int -> IO String query m = do putStrLn ( show m ) hFlush stdout x <- getLine return x singleCase :: Int -> Int -> IO () singleCase a b = do let m = (a+b) `div` 2 response <- query m bisect a b m response return () solve :: Int -> IO () solve 0 = return () solve n = do [a, b] <- fmap(map read.words)getLine _ <- getNum singleCase (a+1) b solve (n-1) main = do hSetBuffering stdout NoBuffering t <- getNum solve t
import java.util.Scanner; public class Solution { public static void solve(Scanner input, int a, int b) { int m = (a + b) / 2; System.out.println(m); String s = input.next(); if (s.equals("CORRECT")) { return; } else if (s.equals("TOO_SMALL")) { solve(input, m + 1, b); } else { solve(input, a, m - 1); } } public static void main(String args[]) { Scanner input = new Scanner(System.in); int T = input.nextInt(); for (int ks = 1; ks <= T; ks++) { int a = input.nextInt(); int b = input.nextInt(); int n = input.nextInt(); solve(input, a + 1, b); } } }
var readline = require('readline'); var rl = readline.createInterface(process.stdin, process.stdout); expect = 'begin'; rl.on('line', function(line) { if (expect === 'begin') { num_test_cases = parseInt(line); expect = 'lo_hi'; case_counter = 0; } else if (expect === 'lo_hi') { lo_hi = line.split(' '); head = parseInt(lo_hi[0]) + 1; tail = parseInt(lo_hi[1]); expect = 'num_tries'; } else if (expect === 'num_tries') { num_tries = line; // not used. expect = 'solve'; mid = parseInt((head + tail) / 2); console.log(mid); } else if (expect === 'solve') { if (line === 'CORRECT') { ++case_counter === num_test_cases ? rl.close() : 0; expect = 'lo_hi'; } else { line === 'TOO_SMALL' ? head = mid + 1 : tail = mid - 1; mid = parseInt((head + tail) / 2); console.log(mid); } } }).on('close',function(){ process.exit(0); });
<?php function solve($a, $b) { $m = ($a + $b) / 2; printf("%d\n", $m); fscanf(STDIN, "%s", $s); if (strcmp($s, "CORRECT") == 0) { return; } else if (strcmp($s, "TOO_SMALL") == 0) { $a = $m + 1; } else { $b = $m - 1; } solve($a, $b); } fscanf(STDIN, "%d", $t); for ($ks = 0; $ks < $t; $ks++) { fscanf(STDIN, "%d %d", $a, $b); fscanf(STDIN, "%d", $n); solve($a + 1, $b); } ?>
import sys def solve(a, b): m = (a + b) / 2 print m sys.stdout.flush() s = raw_input() if s == "CORRECT": return elif s == "TOO_SMALL": a = m + 1 else: b = m - 1 solve(a, b) T = input() for _ in xrange(T): a, b = map(int, raw_input().split()) _ = input() solve(a + 1, b)
import sys def solve(a, b): m = (a + b) // 2 print(m) sys.stdout.flush() s = input() if s == "CORRECT": return elif s == "TOO_SMALL": a = m + 1 else: b = m - 1 solve(a, b) T = int(input()) for _ in range(T): a, b = map(int, input().split()) _ = int(input()) solve(a + 1, b)
$stdout.sync = true def solve(a, b) m = (a + b) / 2 puts m $stdout.flush s = STDIN.gets.chomp if s.eql? "CORRECT" return elsif s.eql? "TOO_SMALL" solve(m + 1, b) else solve(a, m - 1) end end t = STDIN.gets.chomp.to_i ks = 1 while ks <= t a, b = STDIN.gets.split.map &:to_i; n = STDIN.gets.chomp.to_i solve(a + 1, b) ks = ks + 1 end
#include <stdio.h> #include <string.h> void cases(int casenum){ int N,A,B,M; char reply[100]; scanf("%d %d", &A, &B); scanf("%d",&N); A++; while (N>0){ M=(A+B)/2; printf("%d\n",M); fflush(stdout); scanf("%s",reply); if (!strcmp(reply,"CORRECT")) break; if (!strcmp(reply,"WRONG_ANSWER")) break; N--; if (!strcmp(reply,"TOO_BIG")) B=M-1; if (!strcmp(reply,"TOO_SMALL")) A=M+1; } } int main(int argc, char **argv){ int T,i; scanf("%d",&T); for (i=1;i<=T;i++) cases(i); return 0; }
//Published by PKJCODERSusing System; namespace GoogleCodeJamPractice{ class Program{ static void Main(string[] args){ int t = int.Parse(Console.ReadLine()); for (int i=0;i<t;i++){ string[] inpStr = Console.ReadLine().Split(' '); int a = int.Parse(inpStr[0])-1; int b = int.Parse(inpStr[1])+1; int n = int.Parse(Console.ReadLine()); do{ int tryToGuess = b - (b - a)/2; Console.WriteLine(tryToGuess); string resp = Console.ReadLine(); if (resp == "CORRECT"){ break; } if (resp == "TOO_BIG"){ b = tryToGuess; } else if (resp == "TOO_SMALL"){ a = tryToGuess; } else{ return; } }while (true); } } } }
//Published by PKJCODERS#include <bits/stdc++.h> using namespace std; int main(){ int t; scanf("%d",&t); for(int i=1;i<=t;++i){ int r,n; scanf("%d%d%d",&r,&r,&n); int l=1,m,res; char s[32]; while(l<=r){ m=(l+r)/2; printf("%d\n",m); fflush(0); scanf("%s",s); if(s[0]=='C') break; if(s[4]=='S') l=m+1; else r=m-1; } } return 0; }
//Published by PKJCODERSpackage main import "fmt" func main(){ var T int fmt.Scanln(&T) Assert(1 <= T && T <= 20) for t := 0; t < T; t++ { var A, B, N int fmt.Scanln(&A, &B) fmt.Scanln(&N) Assert(A == 0 && A < B && B <= 1e9 && N == 30) A++ for done := false; !done; { mid := (A + B) / 2 fmt.Println(mid) var ans string fmt.Scanln(&ans) switch ans { case "CORRECT": done = true case "TOO_SMALL": A = mid + 1 case "TOO_BIG": B = mid - 1 default: panic("bug") } } } } func Assert(condition bool){ if !condition{ panic("assertion failed") } }
//Published by PKJCODERSimport Control.Monad import System.IO binarySearch :: Int -> Int -> IO () binarySearch a b = do let c = (a+b+1)`div`2 print c >> hFlush stdout response <- getLine case response of "CORRECT" -> return () "TOO_SMALL" -> binarySearch c b "TOO_BIG" -> binarySearch a (c-1) main :: IO () main = do tc <- readLn replicateM_ tc $ do [a,b] <- map read . words <$> getLine getLine binarySearch a b
--Published by PKJCODERSimport java.awt.*; import java.awt.geom.*; import java.io.*; import java.math.*; import java.text.*; import java.util.*; public class Solution { private static BufferedReader br; private static StringTokenizer st; private static PrintWriter pw; public static void main(String[] args) throws Exception { br = new BufferedReader(new InputStreamReader(System.in)); pw = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out))); //int qq = 1; //int qq = Integer.MAX_VALUE; int qq = readInt(); for(int casenum = 1; casenum <= qq; casenum++) { int a = readInt(); int b = readInt(); int n = readInt(); while(a <= b) { int mid = (a+b+1)/2; System.out.println(mid); System.out.flush(); String ret = nextLine(); if(ret.equals("CORRECT")) { break; } if(ret.equals("TOO_SMALL")) { a = mid+1; } else { b = mid-1; } } } pw.close(); } private static void exitImmediately() { pw.close(); System.exit(0); } private static long readLong() throws IOException { return Long.parseLong(nextToken()); } private static double readDouble() throws IOException { return Double.parseDouble(nextToken()); } private static int readInt() throws IOException { return Integer.parseInt(nextToken()); } private static String nextLine() throws IOException { String s = br.readLine(); if(s == null) { exitImmediately(); } st = null; return s; } private static String nextToken() throws IOException { while(st == null || !st.hasMoreTokens()) { st = new StringTokenizer(nextLine().trim()); } return st.nextToken(); } }
//Published by PKJCODERSimport sys t = int(raw_input()) for _ in range(t): a, b = map(int, raw_input().split()) n = raw_input() while 1: mid = (a + b + 1)//2 print(mid) sys.stdout.flush() ans = raw_input() if ans == 'TOO_SMALL': a = mid elif ans == 'TOO_BIG': b = mid - 1 else: break
# Published by PKJCODERSfor _ in range(int(input())): a, b = (int(x) for x in input().split()) _ = input() a += 1 while True: q = (a+b)//2 print(q) s = input() if s == 'TOO_SMALL': a = q+1 elif s == 'TOO_BIG': b = q-1 else: break
#Published by PKJCODERS
Comments