AtCoderのABC    次のABCの問題へ    前のABCの問題へ

ABC299-D Find by Query


問題へのリンク


C#のソース

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static void Main()
    {
        int N = int.Parse(Console.ReadLine());

        int StaPos = 1;
        int EndPos = N;

        while (true) {
            if (StaPos + 1 == EndPos) {
                Console.WriteLine("! {0}", StaPos);
                break;
            }
            int MidPos = (StaPos + EndPos) / 2;
            Console.WriteLine("? {0}", MidPos);

            int GetVal = int.Parse(Console.ReadLine());
            if (GetVal == 0) {
                StaPos = MidPos;
            }
            else {
                EndPos = MidPos;
            }
        }
    }
}


解説

先頭が0で最後が1なので、
必ず0から1に変化する箇所が存在します。

後は二分法の要領で、中央が0か1かを見れば良いです。