시간 제한메모리 제한제출정답맞힌 사람정답 비율
6 초 (추가 시간 없음) 1024 MB72266.667%

문제

You are rocking the latest breakthrough in Computer Science: animated fonts. Suddenly, all of your colleagues' code looks amazing, and you are finally motivated to review it. Unfortunately, due to the constant rotations, it is hard to distinguish between the $+$ (plus) and the $\times$ (multiply) operators (all the other characters are still readable). The function you are reviewing takes as input $n+1$ integers $a_0, a_1, \ldots, a_n$ and returns the value $$\bigg(\ldots\Big(\big((a_0 \,\operatorname{op}_1\, a_1) \,\operatorname{op}_2\, a_2\big) \,\operatorname{op}_3\, a_3\Big) \ldots \,\operatorname{op}_n\, a_n\bigg)\quad \bmod 10^9+7,$$ where the $n$ operators $\operatorname{op}_1,\, \operatorname{op}_2,\, \ldots,\, \operatorname{op}_n$ are either $+$ or $\times$. For example when given input $(a_0,a_1,a_2) = (1,1,2)$ with hidden operators $(\operatorname{op}_1,\operatorname{op}_2)=(+,\times)$, then the function returns $((1+1)\times2)=4 \bmod 10^9+7$.

You can still execute the function a few times on some input and read the returned value. Use this to recover the operators.

인터랙션

This is an interactive problem. Your submission will be run against an interactor, which reads the standard output of your submission and writes to the standard input of your submission. This interaction needs to follow a specific protocol:

The interactor first sends one line containing one integer $n$ ($1 \leq n \leq 4000$), the number of hidden operators.

Then, your program should make at most $275$ queries to determine the operators. Each query is made by printing one line of the form "? $a_0\  a_1\  \ldots\  a_n$" ($0 \leq a_i < 10^9+7$). The interactor will respond by printing one line with an integer, the value of $$\bigg(\ldots\Big(\big((a_0 \,\operatorname{op}_1\, a_1) \,\operatorname{op}_2\, a_2\big) \,\operatorname{op}_3\, a_3\Big) \ldots \,\operatorname{op}_n\, a_n\bigg)\quad \bmod 10^9+7.$$ Make sure you flush the buffer after each write.

When you have determined the operators, print a single line of the form "! $s$", where $s$ is a string consisting of exactly $n$ characters, which are all "+" (plus) or "x" (multiply)1. The $i$th character of this string should be $\operatorname{op}_i$. This line does not count as one of your queries.

Using more than $275$ queries will result in a wrong answer verdict.

A testing tool is provided to help you develop your solution.

1This is the lowercase letter "x", not the Unicode "$\times$" symbol.

예제 입력 1

2

4

6

예제 출력 1


? 1 1 2

? 1 1 3

! +x

예제 입력 2

10

5

6224

640750

예제 출력 2


? 1 1 1 1 1 1 1 1 1 1 1

? 0 4 2 4 2 4 2 4 2 4 2

? 1 2 3 4 5 6 7 8 9 10 11

! ++xxx+x+xx

출처

ICPC > Regionals > Europe > Northwestern European Regional Contest > Benelux Algorithm Programming Contest > BAPC 2021 G번

  • 문제를 만든 사람: Reinier Schmiermann

채점 및 기타 정보

  • 예제는 채점하지 않는다.