재미있는 수

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

요약
K와 M이 주어질 때, 1부터 N까지의 수를 사전순으로 나열했을 때 K가 M번째에 오는 가장 작은 N을 구한다.
난이도

보통10점 중 7점

유형
수학, 이분 탐색, 구현, 트라이
정답자
아직 제출이 없습니다

문제

1부터 N까지의 정수를 생각하자. 이 수들을 사전식 순서(사전에 실리는 순서)로 정렬한다. 예를 들어 N = 11일 때 순서는 다음과 같다.

1, 10, 11, 2, 3, 4, 5, 6, 7, 8, 9.

이 정렬에서 수 K의 위치(1부터 셈)를 QN,KQ_{N,K}라고 하자. 예를 들어 Q11,2=4Q_{11,2} = 4이다.

두 수 K와 M이 주어질 때, QN,K=MQ_{N,K} = M을 만족하는 가장 작은 N을 구하여라.

입력

두 정수 K와 M이 공백으로 구분되어 한 줄에 주어진다 (1≤K,M≤1091 \le K, M \le 10^9).

출력

QN,K=MQ_{N,K} = M을 만족하는 N이 존재하면 그중 가장 작은 값을 출력하고, 존재하지 않으면 0을 출력한다.

예제4

  1. 예제 1

    입력
    2 4
    
    예상 출력
    11
    
  2. 예제 2

    입력
    2 1
    
    예상 출력
    0
    
  3. 예제 3

    입력
    100000001 1000000000
    
    예상 출력
    100000000888888879
    
  4. 예제 4

    입력
    1000000000 11
    
    예상 출력
    0