English · Original
Chinese · Translation
Formal · Original
_The only difference from the previous problem is the constraint on the number of requests. In this problem your program should guess the answer doing at most 7 requests._
This problem is a little bit unusual. Here you are to implement an interaction with a testing system. That means that you can make queries and get responses in the online mode. Please be sure to use the stream flushing operation after each query's output in order not to leave part of your output in some buffer. For example, in C++ you've got to use the _fflush(stdout)_ function, in Java — call _System.out.flush()_, and in Pascal — _flush(output)_.
Bulls and Cows (also known as Cows and Bulls or Pigs and Bulls or Bulls and Cleots) is an old code-breaking paper and pencil game for two players, predating the similar commercially marketed board game Mastermind.
On a sheet of paper, the first player thinks a secret string. This string consists only of digits and has the length 4. The digits in the string **must** be all different, no two or more equal digits are allowed.
Then the second player tries to guess his opponent's string. For every guess the first player gives the number of matches. If the matching digits are on their right positions, they are "bulls", if on different positions, they are "cows". Thus a response is a pair of numbers — the number of "bulls" and the number of "cows". A try can contain equal digits.
More formally, let's the secret string is _s_ and the second player are trying to guess it with a string _x_. The number of "bulls" is a number of such positions _i_ (1 ≤ _i_ ≤ 4) where _s_\[_i_\] = _x_\[_i_\]. The number of "cows" is a number of such digits _c_ that _s_ contains _c_ in the position _i_ (i.e. _s_\[_i_\] = _c_), _x_ contains _c_, but _x_\[_i_\] ≠ _c_.
For example, the secret string is "_0427_", the opponent's try is "_0724_", then the answer is 2 bulls and 2 cows (the bulls are "0" and "2", the cows are "4" and "7"). If the secret string is "_0123_", the opponent's try is "_0330_", then the answer is 1 bull and 1 cow.
In this problem you are to guess the string _s_ that the system has chosen. You only know that the chosen string consists of 4 distinct digits.
You can make queries to the testing system, each query is the output of a single 4\-digit string. The answer to the query is the number of bulls and number of cows. If the system's response equals "4 0", that means the interaction with your problem is over and the program must terminate. That is possible for two reasons — the program either guessed the number _x_ or made an invalid action (for example, printed letters instead of digits).
**Your program is allowed to do at most 7 queries.**
You can hack solutions of other participants providing a 4-digit string containing distinct digits — the secret string.
## Input
To read answers to the queries, the program must use the standard input.
The program will receive pairs of non-negative integers in the input, one pair per line. The first number in a pair is a number of bulls and the second one is a number of cows of the string _s_ and the string _x__i_ printed by your program. If the system response equals "4 0", then your solution should terminate.
The testing system will let your program read the _i_\-th pair of integers from the input only after your program displays the corresponding system query in the output: prints value _x__i_ in a single line and executes operation _flush_.
## Output
The program must use the standard output to print queries.
Your program must output requests — 4\-digit strings _x_1, _x_2, ..., one per line. After the output of each line the program must execute _flush_ operation. The program should read the answer to the query from the standard input.
**Your program is allowed to do at most 7 queries.**
[samples]
## Note
The secret string _s_ in the example is "_0123_".
与上一题的唯一区别在于请求数量的限制。在本题中，你的程序最多只能进行 7 次请求来猜出答案。
本题较为特殊，你需要与测试系统进行交互。这意味着你可以发起查询并在线获取响应。请确保在每次查询输出后执行流刷新操作，以免输出内容滞留在缓冲区中。例如，在 C++ 中需使用 _fflush(stdout)_ 函数，在 Java 中调用 _System.out.flush()_，在 Pascal 中使用 _flush(output)_。
猜数字游戏（也称作 Cows and Bulls 或 Pigs and Bulls 或 Bulls and Cleots）是一种古老的纸笔密码破解游戏，早于类似的商业板游 Mastermind。
在一张纸上，第一位玩家构思一个秘密字符串。该字符串仅由数字组成，长度为 #cf_span[4]。字符串中的数字 *必须* 全部不同，不允许出现两个或更多相同的数字。
接着，第二位玩家尝试猜测对手的字符串。对于每一次猜测，第一位玩家会给出匹配数字的数量。如果匹配的数字位置正确，则称为“bulls”（公牛）；如果数字存在但位置错误，则称为“cows”（母牛）。因此，响应是一个由两个数字组成的对——“bulls”的数量和“cows”的数量。一次猜测中可以包含重复数字。
更正式地，设秘密字符串为 #cf_span[s]，第二位玩家猜测的字符串为 #cf_span[x]。"bulls" 的数量是满足 #cf_span[1 ≤ i ≤ 4] 且 #cf_span[s[i] = x[i]] 的位置 #cf_span[i] 的个数。"cows" 的数量是满足以下条件的数字 #cf_span[c] 的个数：#cf_span[s] 在某个位置 #cf_span[i] 包含 #cf_span[c]（即 #cf_span[s[i] = c]），#cf_span[x] 也包含 #cf_span[c]，但 #cf_span[x[i] ≠ c]。
例如，秘密字符串为 "_0427_"，对手的猜测为 "_0724_"，则答案为 #cf_span[2] 个 bulls 和 #cf_span[2] 个 cows（bulls 是 "0" 和 "2"，cows 是 "4" 和 "7"）。若秘密字符串为 "_0123_"，对手的猜测为 "_0330_"，则答案为 #cf_span[1] 个 bull 和 #cf_span[1] 个 cow。
在本题中，你需要猜出系统选择的字符串 #cf_span[s]。你只知道所选字符串由 #cf_span[4] 个互不相同的数字组成。
你可以向测试系统发起查询，每次查询为输出一个 #cf_span[4] 位的字符串。查询的答案是 bulls 和 cows 的数量。如果系统返回 "4 0"，则表示与你的程序的交互结束，程序必须终止。这可能由两种原因导致：程序要么猜中了数字 #cf_span[x]，要么执行了无效操作（例如，打印了字母而非数字）。
*你的程序最多允许进行 #cf_span[7] 次查询。*
你可以通过提供一个包含互不相同数字的 4 位字符串（即秘密字符串）来 hack 其他选手的解决方案。
为了读取查询的答案，程序必须使用标准输入。
程序将从输入中接收一系列非负整数对，每行一对。每对中的第一个数是 bulls 的数量，第二个数是 cows 的数量，对应于系统秘密字符串 #cf_span[s] 和你的程序输出的字符串 #cf_span[xi]。如果系统响应为 "4 0"，则你的解决方案应终止。
测试系统仅在你的程序在输出中显示对应的查询后，才允许你的程序从输入中读取第 #cf_span[i] 对整数：即你的程序在单独一行打印值 #cf_span[xi] 并执行 _flush_ 操作后。
程序必须使用标准输出打印查询。
你的程序必须输出请求——#cf_span[4] 位的字符串 #cf_span[x1, x2, ...]，每行一个。在每行输出后，程序必须执行 _flush_ 操作。程序应从标准输入读取查询的答案。
*你的程序最多允许进行 #cf_span[7] 次查询。*
示例中的秘密字符串 #cf_span[s] 为 "_0123_"。
## Input
为了读取查询的答案，程序必须使用标准输入。程序将从输入中接收一系列非负整数对，每行一对。每对中的第一个数是 bulls 的数量，第二个数是 cows 的数量，对应于系统秘密字符串 #cf_span[s] 和你的程序输出的字符串 #cf_span[xi]。如果系统响应为 "4 0"，则你的解决方案应终止。测试系统仅在你的程序在输出中显示对应的查询后，才允许你的程序从输入中读取第 #cf_span[i] 对整数：即你的程序在单独一行打印值 #cf_span[xi] 并执行 _flush_ 操作后。
## Output
程序必须使用标准输出打印查询。你的程序必须输出请求——#cf_span[4] 位的字符串 #cf_span[x1, x2, ...]，每行一个。在每行输出后，程序必须执行 _flush_ 操作。程序应从标准输入读取查询的答案。*你的程序最多允许进行 #cf_span[7] 次查询。*
[samples]
## Note
示例中的秘密字符串 #cf_span[s] 为 "_0123_"。
**Definitions**
Let $ s \in D^4 $ be the secret string, where $ D = \{0,1,2,3,4,5,6,7,8,9\} $, and all digits in $ s $ are distinct.
Let $ x^{(k)} \in D^4 $ be the $ k $-th query string made by the program.
Let $ b_k \in \{0,1,2,3,4\} $ and $ c_k \in \{0,1,2,3\} $ be the number of bulls and cows, respectively, in response to $ x^{(k)} $, defined as:
- $ b_k = \left| \left\{ i \in \{1,2,3,4\} \mid s[i] = x^{(k)}[i] \right\} \right| $,
- $ c_k = \left| \left\{ d \in D \mid \text{freq}_s(d) = \text{freq}_{x^{(k)}}(d) > 0, \text{ and } \text{match}_s^d \neq \text{match}_{x^{(k)}}^d \right\} \right| $,
where $ \text{match}_s^d $ is the set of positions where digit $ d $ appears in $ s $, and similarly for $ x^{(k)} $, and $ \text{match}_s^d \neq \text{match}_{x^{(k)}}^d $ means the positions differ.
**Constraints**
1. $ s $ has exactly 4 distinct digits.
2. The program may make at most 7 queries: $ k \leq 7 $.
3. The interaction terminates upon receiving response $ (4, 0) $.
4. Each query $ x^{(k)} $ must be a 4-digit string (digits in $ D $).
**Objective**
Find $ s $ using at most 7 queries, such that for some $ k \leq 7 $, $ x^{(k)} = s $, resulting in response $ (4, 0) $.
API Response (JSON)
{
"problem": {
"name": "C. Interactive Bulls and Cows (Hard)",
"description": {
"content": "_The only difference from the previous problem is the constraint on the number of requests. In this problem your program should guess the answer doing at most 7 requests._ This problem is a little bi",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 2000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF753C"
},
"statements": [
{
"statement_type": "Markdown",
"content": "_The only difference from the previous problem is the constraint on the number of requests. In this problem your program should guess the answer doing at most 7 requests._\n\nThis problem is a little bi...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "与上一题的唯一区别在于请求数量的限制。在本题中，你的程序最多只能进行 7 次请求来猜出答案。\n\n本题较为特殊，你需要与测试系统进行交互。这意味着你可以发起查询并在线获取响应。请确保在每次查询输出后执行流刷新操作，以免输出内容滞留在缓冲区中。例如，在 C++ 中需使用 _fflush(stdout)_ 函数，在 Java 中调用 _System.out.flush()_，在 Pascal 中使用 _...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions** \nLet $ s \\in D^4 $ be the secret string, where $ D = \\{0,1,2,3,4,5,6,7,8,9\\} $, and all digits in $ s $ are distinct. \nLet $ x^{(k)} \\in D^4 $ be the $ k $-th query string made by th...",
"is_translate": false,
"language": "Formal"
}
]
}