D. Mahmoud and Ehab and the binary string

Codeforces

IDCF862D

Time2000ms

Memory256MB

Difficulty—

binary searchdivide and conquerinteractive

English · Original

Chinese · Translation

Formal · Original

Mahmoud and Ehab are in the fourth stage now. Dr. Evil has a hidden binary string of length _n_. He guarantees that there is at least one '0' symbol and at least one '1' symbol in it. Now he wants Mahmoud and Ehab to find a position of any '0' symbol and any '1' symbol. In order to do this, Mahmoud and Ehab can ask Dr. Evil up to 15 questions. They tell Dr. Evil some binary string of length _n_, and Dr. Evil tells the Hamming distance between these two strings. Hamming distance between 2 binary strings of the same length is the number of positions in which they have different symbols. You can find the definition of Hamming distance in the notes section below. Help Mahmoud and Ehab find these two positions. You will get _Wrong Answer_ verdict if * Your queries doesn't satisfy interaction protocol described below. * You ask strictly more than 15 questions and your program terminated after exceeding queries limit. Please note, that you can do up to 15 ask queries and one answer query. * Your final answer is not correct. You will get _Idleness Limit Exceeded_ if you don't print anything or if you forget to flush the output, including for the final answer (more info about flushing output below).If you exceed the maximum number of queries, You should terminate with 0, In this case you'll get Wrong Answer, If you don't terminate you may receive any verdict because you'll be reading from a closed stream . ## Input The first line of input will contain a single integer _n_ (2 ≤ _n_ ≤ 1000) — the length of the hidden binary string. ## Output To print the final answer, print "! pos0 pos1" (without quotes), where _pos_0 and _pos_1 are positions of some '0' and some '1' in the string (the string is 1-indexed). **Don't forget to flush the output after printing the answer!** [samples] ## Interaction To ask a question use the format "? s" (without quotes), where _s_ is a query string. **Don't forget to flush the output after printing a query!** After each query you can read a single integer from standard input — the Hamming distance between the hidden string and the query string. To flush the output you can use:- * fflush(stdout) in C++; * System.out.flush() in Java; * stdout.flush() in Python; * flush(output) in Pascal; * See the documentation for other languages . **Hacking.** To hack someone just print one binary string with length up to 1000, containing at least one '0' and at least one '1'. ## Note Hamming distance definition: [https://en.wikipedia.org/wiki/Hamming_distance](https://en.wikipedia.org/wiki/Hamming_distance) In the first test case the hidden binary string is 1**0**1, The first query is 0**0**0, so the Hamming distance is 2. In the second query the hidden string is still 1**01** and query is 0**01**, so the Hamming distance is 1. After some queries you find that symbol at position 2 is '0' and symbol at position 1 is '1', so you print "! 2 1".

Mahmoud 和 Ehab 目前处于第四阶段。 Dr. Evil 有一个长度为 $n$ 的隐藏二进制字符串。他保证该字符串中至少包含一个 '0' 和一个 '1'。现在他希望 Mahmoud 和 Ehab 找到任意一个 '0' 和任意一个 '1' 的位置。为了做到这一点，Mahmoud 和 Ehab 可以向 Dr. Evil 提问最多 $15$ 次。他们告诉 Dr. Evil 一个长度为 $n$ 的二进制字符串，Dr. Evil 会返回这两个字符串之间的汉明距离。两个长度相同的二进制字符串之间的汉明距离是它们在不同位置上的符号数量。你可以在下面的“注释”部分找到汉明距离的定义。帮助 Mahmoud 和 Ehab 找到这两个位置。如果你超出最大查询次数，你应该终止程序并输出 0，此时你会得到 _Wrong Answer_。如果你不终止，你可能会得到任意结果，因为你将从一个已关闭的流中读取数据。输入的第一行包含一个整数 $n$ ($2 ≤ n ≤ 1000$) —— 隐藏二进制字符串的长度。要输出最终答案，请打印 "! pos0 pos1"（不含引号），其中 $pos0$ 和 $pos1$ 是字符串中某个 '0' 和某个 '1' 的位置（字符串为 1-索引）。*打印答案后不要忘记刷新输出！* 要提出一个问题，请使用格式 "? s"（不含引号），其中 $s$ 是查询字符串。*打印查询后不要忘记刷新输出！* 每次查询后，你可以从标准输入读取一个整数 —— 隐藏字符串与查询字符串之间的汉明距离。要刷新输出，你可以使用： - C++ 中的 fflush(stdout) - Java 中的 System.out.flush() - Python 中的 stdout.flush() - Pascal 中的 flush(output) - 其他语言请参阅相应文档。 *黑客攻击*。要攻击某人，只需打印一个长度不超过 $1000$ 的二进制字符串，其中至少包含一个 '0' 和一个 '1'。汉明距离定义：https://en.wikipedia.org/wiki/Hamming_distance 在第一个测试用例中，隐藏的二进制字符串是 1*0*1，第一次查询是 0*0*0，因此汉明距离为 $2$。第二次查询时，隐藏字符串仍是 1*01*，查询是 0*01*，因此汉明距离为 $1$。经过若干次查询后，你发现位置 $2$ 的字符是 '0'，位置 $1$ 的字符是 '1'，因此你打印 "! 2 1"。 ## Input 输入的第一行包含一个整数 $n$ ($2 ≤ n ≤ 1000$) —— 隐藏二进制字符串的长度。 ## Output 要输出最终答案，请打印 "! pos0 pos1"（不含引号），其中 $pos0$ 和 $pos1$ 是字符串中某个 '0' 和某个 '1' 的位置（字符串为 1-索引）。*打印答案后不要忘记刷新输出！* [samples] ## Interaction 要提出一个问题，请使用格式 "? s"（不含引号），其中 $s$ 是查询字符串。*打印查询后不要忘记刷新输出！* 每次查询后，你可以从标准输入读取一个整数 —— 隐藏字符串与查询字符串之间的汉明距离。要刷新输出，你可以使用： - C++ 中的 fflush(stdout) - Java 中的 System.out.flush() - Python 中的 stdout.flush() - Pascal 中的 flush(output) - 其他语言请参阅相应文档。 *黑客攻击*。要攻击某人，只需打印一个长度不超过 $1000$ 的二进制字符串，其中至少包含一个 '0' 和一个 '1'。 ## Note 汉明距离定义：https://en.wikipedia.org/wiki/Hamming_distance 在第一个测试用例中，隐藏的二进制字符串是 1*0*1，第一次查询是 0*0*0，因此汉明距离为 $2$。第二次查询时，隐藏字符串仍是 1*01*，查询是 0*01*，因此汉明距离为 $1$。经过若干次查询后，你发现位置 $2$ 的字符是 '0'，位置 $1$ 的字符是 '1'，因此你打印 "! 2 1"。

**Definitions** Let $ n \in \mathbb{Z} $, $ 2 \leq n \leq 1000 $, be the length of the hidden binary string $ H = (h_1, h_2, \dots, h_n) \in \{0,1\}^n $. Assume $ H $ contains at least one $ 0 $ and at least one $ 1 $. Let $ Q \leq 15 $ be the maximum number of allowed queries. Each query is a binary string $ s = (s_1, s_2, \dots, s_n) \in \{0,1\}^n $, and the response is the Hamming distance: $$ d(H, s) = \sum_{i=1}^n |h_i - s_i| $$ **Constraints** 1. $ 2 \leq n \leq 1000 $ 2. $ H $ contains at least one $ 0 $ and at least one $ 1 $ 3. At most 15 queries allowed **Objective** Find indices $ p_0, p_1 \in \{1, 2, \dots, n\} $ such that $ h_{p_0} = 0 $ and $ h_{p_1} = 1 $. Output: `! p0 p1`

Samples

Input #1

Output #1

API Response (JSON)

{
  "problem": {
    "name": "D. Mahmoud and Ehab and the binary string",
    "description": {
      "content": "Mahmoud and Ehab are in the fourth stage now. Dr. Evil has a hidden binary string of length _n_. He guarantees that there is at least one '0' symbol and at least one '1' symbol in it. Now he wants Ma",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF862D"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Mahmoud and Ehab are in the fourth stage now.\n\nDr. Evil has a hidden binary string of length _n_. He guarantees that there is at least one '0' symbol and at least one '1' symbol in it. Now he wants Ma...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "Mahmoud 和 Ehab 目前处于第四阶段。\n\nDr. Evil 有一个长度为 $n$ 的隐藏二进制字符串。他保证该字符串中至少包含一个 '0' 和一个 '1'。现在他希望 Mahmoud 和 Ehab 找到任意一个 '0' 和任意一个 '1' 的位置。为了做到这一点，Mahmoud 和 Ehab 可以向 Dr. Evil 提问最多 $15$ 次。他们告诉 Dr. Evil 一个长度为 $n$...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n \\in \\mathbb{Z} $, $ 2 \\leq n \\leq 1000 $, be the length of the hidden binary string $ H = (h_1, h_2, \\dots, h_n) \\in \\{0,1\\}^n $.  \nAssume $ H $ contains at least one $ 0 $ a...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments