31435번 - 기숙사 비밀번호 구하기 서브태스크다국어인터랙티브
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 1024 MB | 592 | 131 | 101 | 26.031% |
문제
이 문제는 인터랙티브 문제이다.
한별이와 우빈이는 같은 기숙사 방을 배정받게 되었다. 그런데 한별이와 같은 방을 쓰기 부끄러웠던 우빈이는 한별이가 들어오기 전 문에다가 비밀번호 장치를 설치해 버렸다. 장치를 풀기 위해선 $0 \leq x_{i} < 998\,244\,353$를 만족하는 $N$개의 정수 $x_{1},x_{2},\cdots,x_{N}$를 알아내야 한다. 그러나 츤데레인 우빈이는 한별이의 프로그래밍 실력이 뛰어난지 알아보기 위하여 다음의 함수를 제공하였다. 한별이는 $N$개의 원하는 정수 $a_{1},a_{2},\cdots,a_{N}$을 골라 그 함숫값 $f(a_{1},a_{2},\cdots,a_{N})$을 알아낼 수 있다.
$0$ 이상 $998\,244\,353$ 미만의 정수들의 집합을 $\mathbb{M}$이라고 할 때, 함수 $f: {\overbrace{\mathbb M \times \mathbb M \times \cdots \times \mathbb M}^{N\text{ times}}} \rightarrow \mathbb{M}$은 다음과 같이 정의된다: $$f(a_{1},a_{2},\cdots,a_{N})=(a_{1}x_{1}+a_{2}x_{2}+\cdots+a_{N}x_{N}) \bmod 998\,244\,353$$
단, 함수는 최대 $N$번만 사용할 수 있으며, 모든 함수 사용을 통틀어서 $a_{1}, a_{2}, \ldots, a_{N}$는 전부 달라야 한다. 즉, 함수를 $k$번 사용했다면 $kN$개의 인자가 모두 달라야 한다.
이제 비밀번호를 구하여 우빈이를 놀래켜 보자.
인터랙션
당신의 프로그램은 아래의 과정을 통해 표준입력과 표준출력으로 인터랙터와 상호작용해야 한다.
먼저, 입력의 첫 번째 줄에 정수 $N$이 주어진다.
아래 쿼리를 출력하면 다음 줄에 $f(a_{1},\cdots,a_{N})$의 값이 주어진다. 이 쿼리는 최대 $N$번만 사용할 수 있다.
?$a_1$
아래 쿼리를 출력해서 비밀번호를 제출할 수 있다. 이 쿼리를 출력한 직후 프로그램을 종료해야 한다.
!$x_1$
각 채점 데이터에 대하여, 제출한 비밀번호가 정답이라면 맞았습니다!!, 오답이라면 틀렸습니다 결과를 받는다. 단, 문제의 제한 안에 올바른 상호작용을 통해 답을 출력하지 못하면 예상치 못한 채점 결과를 받을 수 있다.
제한
- $2 \leq N \leq 2500$
서브태스크
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 10 | $N \leq 100$ |
| 2 | 90 | 추가 제약 조건 없음 |
예제 입력 1
2 4 6
예제 출력 1
? 1 3 ? 2 4 ! 1 1
노트
당신의 프로그램은 무언가를 출력한 후 즉시 출력 버퍼를 비워야 한다. 다음은 언어별 출력 버퍼를 비우는 방법이다.
- C —
fflush(stdout) - C++ —
std::cout.flush() - Python —
sys.stdout.flush() - Java —
System.out.flush() - 그 외의 언어는 각 언어의 Documentation을 참고한다.
또한, 예제의 빈 줄은 입출력이 어떤 방식으로 이루어지는지 이해를 돕기 위해 의도적으로 추가된 것이며, 실제 입출력에는 빈 줄이 나타나지 않는다.
출처
School > 한국과학영재학교 > 2024 KSA Automata Winter Contest D번
- 문제를 만든 사람: davidkim0
- 문제를 검수한 사람: hjroh0315, wizardrabbit, vkdldjvkdnj, utilforever, shiftpsh, parkky, naeby, mickeyjung, kiwiyou, jyheo98, aaron0526, gs22059, gs20036, flakepowders, eric00513, edward3378, anchor, ai4youej
채점 및 기타 정보
- 예제는 채점하지 않는다.