심사위원단은 $[1, n]$ 구간에서 어떤 정수 $x$를 선택했습니다. 당신의 임무는 이 수를 맞히는 것입니다. 완전히 무작위로 추측하지 않아도 되도록, 당신은 질의를 할 수 있습니다. 각 질의에서 당신은 $[0, c]$ 구간의 정수 $y$를 제시할 수 있으며, 그에 대한 응답으로 $x + y$의 약수의 개수를 알려줍니다.
문제를 조금 더 어렵게 만들기 위해, 프로그램이 한 번 실행되는 동안 $t$개의 테스트 케이스를 해결해야 합니다. 이 케이스들에서 당신이 할 수 있는 총 질의 횟수는 $q$로 제한됩니다.
인터랙션
이 문제는 인터랙티브 문제입니다. 제공된 라이브러리를 사용하여 심사위원단과 통신하는 프로그램을 작성해야 합니다. 라이브러리를 사용하려면 프로그램에 다음을 포함해야 합니다.
- C++:
#include "dzilib.h" - Python:
from dzilib import GetT, GetN, GetQ, GetC, Ask, Answer
라이브러리는 다음 함수들을 제공합니다.
GetT()– 해결해야 할 테스트 케이스의 수인 매개변수 $t$를 반환합니다.GetN()– 숨겨진 값 $x$에 대한 상한인 매개변수 $n$을 반환합니다.GetQ()– 모든 $t$개의 테스트 케이스에서 당신이 할 수 있는 총 질의 횟수의 제한인 매개변수 $q$를 반환합니다.GetC()– 당신이 제시할 수 있는 값 $y$에 대한 상한인 매개변수 $c$를 반환합니다.Ask(y)– 숨겨진 수 $x$에 $y$를 더한 값의 양의 약수 개수를 반환합니다. $0 \le y \le c$를 만족해야 합니다.Answer(z)– 숨겨진 값 $x$가 $z$라고 라이브러리에 알립니다. 아무것도 반환하지 않습니다(C++에서는void타입).
Python에서 모든 라이브러리 함수의 매개변수와 반환값은 정수형입니다. C++에서 함수가 받아들이고 반환하는 타입은 제공된 예제 라이브러리와 동일하며, 자세한 내용은 '실험' 섹션을 참조하십시오.
프로그램이 실행되는 동안(종료 직전 제외) 항상 하나의 테스트 케이스가 활성화되어 있습니다. 첫 번째 테스트 케이스는 프로그램이 시작되자마자 활성화됩니다. 테스트 케이스가 활성화되어 있는 동안 Ask 함수를 사용하여 질의할 수 있습니다. 숨겨진 값 $x$를 알아냈다고 판단되면 Answer 함수를 사용하여 제출할 수 있으며, 라이브러리가 이를 검증합니다. 만약 제출한 값이 틀리면 라이브러리는 "잘못된 답변(błędna odpowiedź)" 판정과 함께 프로그램을 종료합니다. 제출한 값이 올바르면 함수가 종료되며, 아직 해결하지 않은 테스트 케이스가 남아있다면 다음 케이스가 즉시 활성화됩니다. 마지막 테스트 케이스에 대한 답변을 제출한 후에는 프로그램을 종료해야 합니다. 그렇지 않고 Ask나 Answer 함수를 다시 호출하려고 하면 "잘못된 답변" 판정을 받게 됩니다.
GetT, GetN, GetQ, GetC 함수는 프로그램 실행 중 언제든지 사용할 수 있으며, 반환되는 값은 변하지 않습니다. 이 함수들은 질의 횟수 제한에 포함되지 않지만, CPU 시간을 소모합니다. $q$ 값은 Ask 함수의 호출 횟수만을 제한합니다. 총 허용 질의 횟수를 초과하는 순간 라이브러리는 프로그램을 종료하고 "잘못된 답변" 판정을 내립니다.
표준 입력에서 데이터를 읽거나 표준 출력에 아무것도 출력하지 마십시오. 평가 라이브러리의 내부 동작에 의도적으로 영향을 주려는 시도는 금지됩니다.
라이브러리
모든 테스트에서 숨겨진 값 $x$와 그 순서는 미리 정해져 있습니다. 즉, 당신의 프로그램과 통신하는 라이브러리는 악의적이지 않으며 당신의 프로그램 동작에 맞춰 행동을 조정하지 않습니다.
문제에 명시된 제한은 당신의 프로그램이 사용하는 시간과 메모리에만 적용됩니다. 라이브러리의 실행 시간과 메모리 사용량은 테스트 케이스와 당신 프로그램의 정확한 동작에 따라 달라질 수 있습니다. 따라서 SIO2의 시간 및 메모리 제한은 문제에 명시된 것보다 약간 더 큽니다.
예제
예제 테스트에서는 $t = 2, n = 10^6, q = 10^4, c = 10^{15}$이며, 숨겨진 값은 순서대로 $1000$과 $1$입니다. 라이브러리와의 예시 통신은 다음과 같습니다.
| 호출된 함수 | 결과 | 설명 |
|---|---|---|
GetT() |
$2$ | $t = 2$. |
GetN() |
$1\,000\,000$ | $n = 10^6$. |
GetQ() |
$10\,000$ | $q = 10^4$. |
GetC() |
$1\,000\,000\,000\,000\,000$ | $c = 10^{15}$. |
Ask(1) |
$8$ | $x + 1$의 약수는 8개: 1, 7, 11, 13, 77, 91, 143, 1001. |
Ask(24) |
$11$ | $x + 24$의 약수는 11개: 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024. |
Answer(1000) |
– | 올바른 답변, 다음 테스트 케이스가 시작됨. |
GetT() |
$2$ | 허용된 질의 – 반환값은 변하지 않음. |
Answer(1) |
– | 마지막 테스트 케이스에 대한 올바른 답변. 답변 후 프로그램을 종료해야 함. |
총 2번의 Ask 질의를 수행했으며, 이는 10,000번의 제한 내에 있습니다. 모든 테스트 케이스에 대한 총 질의 횟수가 계산된다는 점을 기억하십시오.
서브태스크
테스트 그룹 내의 모든 테스트는 아래 표에 제시된 동일한 $t, n, q, c$ 값을 가집니다.
| 그룹 번호 | $t$ | $n$ | $q$ | $c$ |
|---|---|---|---|---|
| 1 | 50 | $10^5$ | 50\,000 | $10^{12}$ |
| 2 | 50 | $10^6$ | 5\,000 | $10^{12}$ |
| 3 | 10 | $10^9$ | 50\,000 | $10^{12}$ |
| 4 | 10 | $10^{14}$ | 5\,000 | $10^{17}$ |
| 5 | 10 | $10^{14}$ | 2\,000 | $10^{17}$ |
| 6 | 10 | $10^{14}$ | 1\,300 | $10^{17}$ |
| 7 | 10 | $10^{14}$ | 950 | $10^{17}$ |
| 8 | 10 | $10^{14}$ | 820 | $10^{17}$ |
| 9 | 10 | $10^{14}$ | 750 | $10^{17}$ |
| 10 | 10 | $10^{14}$ | 720 | $10^{17}$ |
예제 테스트는 어떤 그룹에도 속하지 않습니다. 이 테스트를 해결할 수 있지만, 이를 해결하지 않고도 만점을 받을 수 있다는 점에 유의하십시오.
구현 세부사항
잘못된 예시 솔루션과 C++ 및 Python용 예제 라이브러리는 SIO2의 '파일(Pliki)' 섹션에 있는 아카이브에서 찾을 수 있습니다. 이 솔루션과 라이브러리는 모든 함수가 반환하고 받아들이는 타입을 보여줍니다. 예제 라이브러리는 실제 평가에 사용될 라이브러리와 동작이 다를 수 있으며, 문제의 가정을 충족하지 않을 수도 있습니다. 이는 단지 프로그램과의 상호작용 방식을 보여주기 위한 것입니다.
C++ 언어의 dzi.cpp 솔루션은 다음과 같이 컴파일할 수 있습니다.
g++ -O3 -static -o dzi dzi.cpp dzilib.cpp -std=c++20
dzilib.h와 dzilib.cpp 파일이 솔루션과 같은 폴더에 있는지 확인하십시오.
dzi.py 솔루션은 다음 명령어로 실행할 수 있습니다.
python dzi.py
dzilib.py 파일이 솔루션과 같은 폴더에 있는지 확인하십시오.
실행 시, 프로그램 시작 직후 라이브러리는 표준 입력으로 $t, n, q, c$ 값을 순서대로 읽고, 이어서 숨겨진 값 $x$들을 읽습니다. 예제 테스트에 해당하는 입력 파일은 두 아카이브 모두에 dzi0.in이라는 이름으로 포함되어 있습니다.