Codeforces Round #415 (Div. 2) D. Glad to see you! 이분

3360 단어 codeforces2점상호 작용
제목 링크: Glad to see you!
제목의 대의.
n개의 요리, 번호는 1-n이고 그 중에서 k개의 요리가 주문되었다. 너는 매번 x, y 두 개의 숫자를 맞출 수 있다. 만약|x-a|<=|y-b| 상호작용기가 되돌아온다"TAK". 그렇지 않으면 되돌아온다"NIE". 그 중에서 a는 x에서 가장 가까운 요리의 번호이고 a는 x와 같다. b는 60번 안에 임의의 두 개의 주문된 요리n<=1e5를 맞출 수 있도록 요구한다.
사고의 방향
60회 이내에 맞히면 분명히logn급의 복잡도, 즉 이분 상호작용기가 되돌아오는 답은 x와 y가 그들이 최근에 주문한 요리의 거리 중 어느 것이 더 작은지만 판단할 수 있다. 그러면 두 개의 인접한 숫자,mid와mid+1을 출력한다. 만약mid의 거리가 더 가깝다면 [1,mid]는 주문한 요리가 있을 것이다. 반대로 [mid+1,n]는 주문한 요리가 있을 것이다.이렇게 2분의 사상으로 계속 나누면 반드시 한 위치로 갈 수 있다. x는 주문받은 요리가 두 개 이상 있기 때문에 [1,x-1], [x+1,n] 이 두 구간에 적어도 한 개의 요리가 있다. 같은 방법으로 다른 요리를 찾는다.
코드
#include 

using namespace std;


const int MANX = 1E5 + 100;
int n, k;
char s[100];

bool query(int x, int y)
{
    printf("1 %d %d
", x, y);
    cout.flush();
    scanf("%s", s);
    return s[0] == 'T';
}

int bs(int l, int r)
{
    if(l>r) return -1;
    int mid;
    while(l < r)
    {
        mid = (l+r)/2;
        if(query(mid, mid+1)) r = mid;
        else l = mid+1;
    }
    return l;
}

int main()
{
    scanf("%d%d", &n, &k);
    int x = bs(1, n), y;
    if(x==1) y = bs(x+1, n);
    else if(x==n) y = bs(1, x-1);
    else
    {
        y = bs(1, x-1);
        if(!query(y, x)) y = bs(x+1, n);
    }
    printf("2 %d %d
", x, y);

    return 0;
}
js 콜, apply, bid, instanceof 방법 을 수 동 으로 실현 합 니 다.
js 브 라 우 저의 각종 속성 가 져 오기.

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage