만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

토너먼트 조작

면접 대비

시간 제한1초메모리 제한1024 MB

요약
2^n개 팀이 참가하는 단판 토너먼트에서 우리 팀의 순위 r과 n이 주어질 때, 매 라운드 대진을 자유롭게 정하면 우리 팀이 도달할 수 있는 가장 늦은 라운드를 구합니다.
난이도

보통10점 중 5점

유형
수학, 그리디
정답자
아직 제출이 없습니다

문제

가장 흔한 토너먼트 형식은 라운드로 진행되는 단판 토너먼트다. 토너먼트를 운영하려면 처음 참가하는 팀 수가 2의 거듭제곱이어야 한다. 예를 들어 16(242^4)팀으로 시작하면 1라운드에는 8경기가 열려 8팀이 이기고 8팀이 진다. 2라운드에서는 1라운드에서 이긴 8팀이 4경기로 짝지어진다. 이렇게 승자끼리 짝을 짓는 과정이 두 팀만 남을 때까지 계속되고, 마지막 두 팀이 우승을 놓고 겨룬다.

이 문제에서는 다음을 가정한다.

  • 팀은 양의 정수 n에 대해 1부터 2n2^n까지 순위가 매겨진다.
  • 가장 강한 팀의 순위는 1이고, 가장 약한 팀의 순위는 2n2^n이다. (이를 "1기반 순위"라고 한다)
  • 순위가 더 높은(번호가 작은) 팀이 낮은 팀과 경기하면, 순위가 높은 팀이 항상 이긴다.

대진은 정해져 있지 않다. 토너먼트 소프트웨어에 접근했다고 하자. 각 라운드에서 남은 팀들을 원하는 대로 짝지을 수 있다. 응원하는 팀이 도달할 수 있는 가장 높은 라운드를 구하라.

입력

한 줄에 두 정수가 주어진다. n(2≤n≤202 \le n \le 20)은 토너먼트의 라운드 수이고, r(1≤r≤2n1 \le r \le 2^n)은 응원하는 팀의 1기반 순위이다.

출력

응원하는 팀이 도달할 수 있는 가장 높은 라운드 번호를 한 줄에 출력한다.

예제3

  1. 예제 1

    입력
    4 13
    
    예상 출력
    3
    
  2. 예제 2

    입력
    6 64
    
    예상 출력
    1
    
  3. 예제 3

    입력
    20 2
    
    예상 출력
    20