33492번 - 멀티버스를 여행하는 한별이를 위한 안내서 서브태스크다국어인터랙티브
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 166 | 40 | 35 | 23.810% |
문제
멀티버스 여행을 하다 공간이동 스킬을 잃어버린 한별이는 어느새 은하의 수중에 공간이동 스킬이 있는 것을 발견했다! 한별이는 공간이동 스킬을 돌려받기 위해 은하와 아래와 같은 내기를 하기로 했다.
은하만 알고 있는 $1$ 이상 $10^8$ 미만의 두 정수 $N$, $K$가 준비되어 있다. 한별이는 은하에게 아래와 같은 질문을 최대 $Q$번 할 수 있다.
?$x$ $y$: $N\times K^x \equiv N\times K^y \pmod{10^8}$인가?
한별이는 $N\times K^a \equiv N\times K^b \pmod{10^8}$를 만족하는 두 개의 서로 다른 음이 아닌 정수 $a$, $b$ 중에서, $a$를 최소화하는 가장 작은 $b$의 값을 구해야 한다. 은하는 공정한 내기를 위해 항상 그러한 $b$가 존재하도록 $N$, $K$를 선택한다. 한별이는 이 내기에서 이길 수 있게끔 당신에게 프로그램을 작성해 줄 것을 부탁했다.
인터랙션
당신의 프로그램은 아래의 과정을 통해 표준입력과 표준출력으로 인터랙터와 상호작용해야 한다.
입력은 하나 이상의 테스트 케이스로 이루어져 있다. 먼저, 첫 번째 줄에 테스트 케이스의 개수 $T$가 주어진다. 각 테스트 케이스에 대해서 아래와 같이 상호작용해야 한다
아래 쿼리를 출력하면, 다음 줄에 쿼리의 답이 참이라면 YES가, 거짓이라면 NO가 주어진다. 이 쿼리는 하나의 테스트 케이스에서 최대 $Q$번만 사용할 수 있다.
?$x$ $y$ㅤ(단, $0 \leq x, y \leq 10^9;$ $x$, $y$는 정수)
아래 쿼리를 출력해서 답을 제출할 수 있다. 이 쿼리는 질문한 것으로 세지 않으며, 출력한 직후 해당 테스트 케이스에 대한 인터랙션은 종료된다.
!$b$
마지막이 아닌 테스트 케이스에 대한 상호 작용이 종료되었다면 즉시 다음 테스트 케이스에 대한 상호 작용으로 넘어가야 하고, 마지막 테스트 케이스에 대한 상호 작용이 종료되었다면 즉시 프로그램을 종료해야 한다.
각 채점 데이터에 대하여, 모든 테스트 케이스에서 제출한 답이 정답이라면 맞았습니다!!, 적어도 하나의 테스트 케이스에서 제출한 답이 오답이라면 틀렸습니다 결과를 받는다. 단, 문제의 제한 안에 올바른 상호작용을 통해 답을 출력하지 못하면 예상치 못한 채점 결과를 받을 수 있다.
제한
- $1\leq T\leq 100$
서브태스크
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 35 | $Q = 35$ |
| 2 | 65 | $Q = 10$ |
예제 입력 1
2 NO YES NO
예제 출력 1
? 1 2 ? 8 24 ! 24 ? 123 456 ! 631
첫 번째 테스트 케이스에서 $N=21;$ $K=15$이다.
두 번째 테���트 케이스에서 $N=33\, 413\, 900;$ $K=34\, 653\, 426$이다.
힌트
당신의 프로그램은 무언가를 출력한 후 즉시 출력 버퍼를 비워야 한다. 다음은 언어별 출력 버퍼를 비우는 방법이다.
- C —
fflush(stdout) - C++ —
std::cout.flush() - Python —
sys.stdout.flush() - Java —
System.out.flush() - 그 외의 언어는 각 언어의 Documentation을 참고한다.
또한, 예제의 빈 줄은 입출력이 어떤 방식으로 이루어지는지 이해를 돕기 위해 의도적으로 추가된 것이며, 실제 입출력에는 빈 줄이 나타나지 않는다.
출처
School > 한국과학영재학교 > 2025 KSA Automata Winter Contest F번
- 문제를 만든 사람: davidkim0, flakepowders
- 문제를 검수한 사람: ai4youej, kwoncycle, mythofys, parkky, raehwan0418, sjhi00, utilforever
채점 및 기타 정보
- 예제는 채점하지 않는다.
© 2026 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호