Hướng dẫn cho Google Code Jam 2018 - Number Guessing

Chỉ sử dụng khi thực sự cần thiết như một cách tôn trọng tác giả và người viết hướng dẫn này.

Chép code từ bài hướng dẫn để nộp bài là hành vi có thể dẫn đến khóa tài khoản.

Test Set 1

Vì \(A=0\), \(B=30\) và mỗi test cho \(N=30\) lượt, chỉ cần đoán lần lượt mọi số từ 1 đến 30 cho đến khi bộ chấm trả về CORRECT.

Test Set 2: tìm kiếm nhị phân

Đáp án có thể nằm ở bất kỳ đâu trong \([1,10^9]\) nhưng vẫn chỉ có 30 lượt, nên dùng tìm kiếm nhị phân. Ban đầu đoán điểm giữa

\[ \frac{1+10^9}{2}=5\times10^8. \]

Nếu nhận TOO_SMALL, \(P\) nằm ở nửa trên; nếu nhận TOO_BIG, \(P\) nằm ở nửa dưới; nếu nhận CORRECT, ta đã xong. Tiếp tục đoán số giữa của miền còn lại và lặp lại.

Một cách cài đặt rõ ràng là giữ miền nguyên đóng [lo, hi], ban đầu lo=A+1, hi=B, rồi đoán \(m=\lfloor(lo+hi)/2\rfloor\). Với TOO_SMALL, đặt lo=m+1; với TOO_BIG, đặt hi=m-1. Mỗi dự đoán sai làm miền kế tiếp không quá nửa miền trước. Vì

\[ \log_2(10^9)=29.897353\ldots<30, \]

ta luôn đoán đúng trong giới hạn. Sau mỗi dự đoán phải flush, và phải thoát nếu nhận bất kỳ phản hồi lỗi nào.

Các lời giải mẫu chính thức

Bài này nhằm giúp thí sinh làm quen với bộ chấm tương tác. Dưới đây là lời giải mẫu bằng tất cả ngôn ngữ mà Code Jam hỗ trợ tại thời điểm đó. Các chương trình đều thực hiện cùng phép tìm kiếm nhị phân; mã được giữ nguyên như tài liệu chính thức.

Bash

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

C

#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;
}

C

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;
        }
      }
    }
  }
}

C++

#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;
}

Go

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
      }
    }
  }
}

Haskell

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

Java

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);
    }
  }
}

JavaScript

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

<?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);
}
?>

Python 2

Python

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)

Python 3

Python

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)

Ruby

$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

Dựa trên phân tích chính thức của Google Code Jam 2018, Vòng luyện tập, bài Number Guessing.

Bình luận

Tải bình luận...

Không có bình luận nào.