대화형 문제

"대화형 문제"에 대해



이러한 종류의 문제에서 주어진 입력은 미리 결정되지 않을 수 있지만 특별히 솔루션을 위해 구축되었습니다. 심사위원은 출력이 솔루션의 입력으로 리디렉션되고 프로그램의 출력이 전송되도록 특별한 "인터랙터"를 작성합니다. 인터랙터의 입력에.
따라서 대화형 문제를 요약하면 솔루션의 출력에 따라 입력을 제공합니다. 예제를 처리하기 전에 버퍼로 인해 발생하는 일부 버그를 피하기 위해 출력을 플러시하는 데 주의를 기울여야 합니다.
플러시하려면 다음을 사용할 수 있습니다(정수와 줄 끝을 인쇄한 직후).

fflush(stdout) in C++;
System.out.flush() in Java;
stdout.flush() in Python;
flush(output) in Pascal;

다른 언어에 대한 문서를 참조하십시오.
이제 다음 예를 살펴보겠습니다.
Bear and prime 100

사설



문제 설명에서 언급했듯이 소수는 1과 그 자체로만 나눌 수 있다는 것을 알고 있으므로 비밀 번호가 합성인지 소수인지 추측하기 위해 최대 20개의 쿼리를 요청해야 합니다. "즉, 숨겨진 숫자는 출력의 숫자로 나눌 수 있음을 의미합니다."카운트가 2와 같으면 카운트를 증가시키고 숨겨진 숫자가 합성임을 확신하지만 출력하지 않는다는 점에 주의해야 합니다. 1(모든 숫자는 1로 나눌 수 있음) ...우리는 솔루션의 일부를 마쳤습니다. 아직 처리해야 할 몇 가지 특별한 경우가 있습니다. 예를 들어 25가 1과 5로 나눌 수 있는 완벽한 제곱이 있는 경우 우리는 할 수 있습니다. t 출력 1 그래서 우리는 2로 시작하는 최대 20개의 쿼리가 있기 때문에 쿼리로 숫자 5만 가질 것입니다. 이 경우 카운트는 1과 같을 것이고 25는 거짓인 소수로 간주할 것입니다.
이 오답을 피하기 위해 벡터에 50 미만의 모든 소수와 완전제곱수를 저장하면 벡터에 {2,3,5,7,11,13,17,19,23,29, 31,37,41,43,47,4,9,25,49}(숫자 19개) 따라서 최대 19개의 쿼리를 요청할 수 있으며 해당 벡터를 사용하여 모든 특수한 경우를 처리했으며 물론 제수의 개수가 는 2와 같습니다. 우리는 여전히 풀어야 합니다....그게 다야, 문제는 그렇게 어렵지 않고 재미있게 풀 수 있으며 주제를 즐겼기를 바랍니다
문제 링크: Bear and prime 100
코드: Solution
의견과 피드백을 환영합니다

Thank you ;

좋은 웹페이지 즐겨찾기