Lazy Sorting

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

요약
상자끼리의 비교 결과만 주어질 때, 처음 M명의 학생에게 상자를 나눠주기 위해 필요한 최소 저울질 횟수를 구한다.
난이도

보통10점 중 6점

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

문제

Teacher Laur organized a programming contest for his NN students and now wants to award them prizes according to their results. The prizes were lined up on a shelf in correct order, but then Toots toppled the shelf with his horseplay. As the prizes are in identical boxes, the teacher put them back on the shelf in a random order.

The prizes have different weights and the teacher has balance scales that he can use to compare two boxes and find out which is intended for the student with the better result. However, each weighing takes time and the first MM students have already lined up behind his door to receive their prizes...

To minimize the total time that students spend waiting for their prizes, the teacher wants to give each student their prize with as few weighings as possible. Write a program to help the teacher do that.

예제1

  1. 예제 1

    입력
    3 2
1

>

<

3

>
    예상 출력
    

? 1 2

? 2 3

! 2

? 1 3

! 1