Misdelivered letters

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

요약
N개의 편지가 N개의 집에 하나씩 잘못 배달됐고 그중 적어도 하나는 제자리에 있다. 어떤 집이 제자리인지 찾아내야 하며, 질의 횟수를 줄이는 것이 목표다.
난이도

보통10점 중 7점

유형
완전 탐색, 구현, 수학, 확률
정답자
아직 제출이 없습니다

문제

Dan's career as a postman isn't going very well. Yesterday, he was tasked with delivering electricity bills to each of the NN houses in Brno. However, he somehow managed to mix up the order of the bills yet again and ended up delivering most of them to the wrong houses. Nevertheless, he is sure that he delivered at least one letter correctly. Can you help him find it?

The houses in Brno are numbered from 11 to NN. There are NN bills, each addressed to a different house. Every house received exactly one bill. Dan can go to any house, ring the bell and ask the residents which houses letter they ended up with. Dan doesn't want to disturb too many people, so he would like to minimize the number of houses he checks.

제한

  • N=1000N = 1000
  • T=1000T = 1000
  • At least one letter was delivered to the correct house.

예제

이 문제는 공개된 예제가 없습니다.