COVID 검사

Adam의 학교에 COVID 유행이 다시 번지고 있다. 학교는 감염 확산을 막기 위해 항원 검사로 학생 전원을 검사하기로 했다. 검사에는 학생들의 침 샘플을 사용한다.

교사들은 검사 방법을 오래전에 잊어버렸기 때문에, Adam이 검사를 돕는 자원봉사자로 나섰다.

Adam은 $N$명의 학생으로부터 침 샘플을 받았다. 개인정보 보호를 위해 Adam이 알 수 있는 것은 식별자 $0$부터 $N-1$까지뿐이다. 그의 임무는 어떤 샘플이 양성인지 알아내는 것이다. 샘플을 하나씩 검사하면 너무 오래 걸리고 지루하다. 대신 샘플 일부를 섞어서 한 번에 검사할 수 있다. 이 검사로 섞은 샘플이 모두 음성인지, 아니면 하나 이상이 양성인지 알 수 있다. 섞어서 검사하면 필요한 검사 횟수를 줄일 수 있다.

각 샘플에는 충분한 양의 침이 있어서, 같은 샘플을 원하는 만큼 여러 번 검사할 수 있다. 검사는 완벽하게 정확하므로, 같은 샘플에 대해 서로 다른 검사 결과가 나오는 일은 없다.

Adam은 검사 횟수를 가능한 한 적게 쓰고 싶어 한다. 그는 검사로 바쁘므로, 검사 과정을 최적화하는 일은 당신이 맡는다.

지역 통계에 따르면 각 샘플이 양성일 확률은 $P$이다. 한 샘플의 양성 여부는 다른 샘플의 양성 여부에 영향을 받지 않는다. 이 정보를 바탕으로 어떤 검사를 수행할지 정하면 된다.

이 문제의 채점 방식은 적응형이 아니다. 즉, 각 샘플이 양성인지는 프로그램이 실행되기 전에 이미 정해져 있다. 각 샘플의 양성 여부는 공정한 난수 생성기를 사용해 확률 $P$로 독립적으로 정해진다.