cho.sh이발소 대기열
절삭 시간이 다른 B명의 이발사 중 N번째 손님을 맡는 이발사 번호를 번호가 작은 순이라는 동점 규칙에 따라 구합니다.
보통5이분 탐색수학면접 대비아직 제출이 없습니다시간 제한5초메모리 제한512 MB문제
유행하는 이발소 앞에 손님이 길게 줄을 서 있다. 이발소에는 이발사가 B명 있고, 번호는 1번부터 B번까지다. k번 이발사는 손님 한 명의 머리를 자르는 데 항상 정확히 Mk분이 걸리며, 동시에 두 명을 맡지는 못한다. 한 손님의 머리를 다 자른 이발사는 곧바로 다음 손님을 받는다.
줄 맨 앞에 선 손님은 비어 있는 이발사 중에서 번호가 가장 작은 이발사에게 간다. 비어 있는 이발사가 한 명도 없으면 누군가 빌 때까지 기다린다.
당신은 줄에서 N번째이고, 이발소는 방금 문을 열었다. 당신의 머리를 자를 이발사의 번호를 구하시오.
입력
첫째 줄에 테스트 케이스의 개수 T가 주어진다. 이어서 테스트 케이스가 T개 주어지고, 각 테스트 케이스는 두 줄로 이루어진다.
첫째 줄에는 이발사의 수 B와 줄에서 당신의 순번 N이 공백으로 구분되어 주어진다. 맨 앞의 손님이 1번, 그 다음 손님이 2번이며, 뒤로 갈수록 번호가 하나씩 커진다. 둘째 줄에는 M1,M2,…,MB가 공백으로 구분되어 주어진다.
제한
- 1≤T≤100
- 1≤B≤1000
- 1≤N≤109
- 1≤Mk≤100000
출력
각 테스트 케이스마다 Case #x: y 형식으로 한 줄씩 출력한다. x는 1부터 시작하는 테스트 케이스 번호이고, y는 당신의 머리를 자를 이발사의 번호다.
설명
첫 번째 예제 케이스를 보자. 당신은 네 번째 손님이고, 1번 이발사는 10분, 2번 이발사는 5분이 걸린다. 문을 연 순간 첫 손님은 1번과 2번 중에서 고를 수 있으므로 번호가 작은 1번에게 간다. 두 번째 손님은 곧바로 2번에게 간다. 세 번째 손님은 빈 이발사가 없어서 기다린다. 5분이 지나면 2번이 두 번째 손님을 끝내고 세 번째 손님을 받는다. 10분이 지나면 1번과 2번이 동시에 비고, 다음 차례인 당신은 두 이발사 중 1번을 고른다.