(23306) binary는 호남선

https://www.acmicpc.net/problem/23306

단계별로 풀어보기

41단계(인터랙티브와 투 스텝 1) 6번째

 

 

 

중간값 정리와 비슷한 개념을 생각하면 되는 문제.

저지대에서 시작해 고지대에서 끝난다면 항상 내리막 구간보다 하나 더 많은 오르막 구간이 있다.

반대도 마찬가지고, 시작과 끝의 높이가 같다면 항상 내리막 구간과 오르막 구간의 수는 같다.

따라서 2번의 질문으로 끝낼 수 있다. 질문 횟수를 log N으로 제한하여 이분 탐색인 것처럼 함정을 판 문제.

 

 

 

#include <iostream>
using namespace std;

int main() 
{
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  
  int n, a, b;
  
  cin >> n;
  cout << "? 1" << endl;
  cin >> a;
  cout << "? " << n << endl;
  cin >> b;
  
  if(a==1 && b==0) cout << "! -1";
  else if(a==0 && b==1) cout << "! 1";
  else  cout << "! 0";
  
  return 0;
}