B. A Map of the Cat

Codeforces

IDCF952B

Time1000ms

Memory256MB

Difficulty—

brute forceinteractive

English · Original

Chinese · Translation

Formal · Original

If you have ever interacted with a cat, you have probably noticed that they are quite particular about how to pet them. Here is an approximate map of a normal cat. <center>![image](https://espresso.codeforces.com/6687e403b1becb2aa254a2594961a3baac90e23a.png)</center>However, some cats won't tolerate this nonsense from the humans. Here is a map of a grumpy cat. <center>![image](https://espresso.codeforces.com/6a3ca5f84ac1f7ac1394c2701772f4601c5b2252.png)</center>You have met a cat. Can you figure out whether it's normal or grumpy? ## Interaction This is an interactive problem. Initially you're not given any information about the cat. Instead, the cat is divided into ten areas, indexed from 0 to 9. In one query you can choose which area you'll pet and print the corresponding index to standard out. You will get the cat's response, as depicted on the corresponding map, via standard in. For simplicity all responses are written in lowercase. Once you're certain what type of cat you're dealing with, output "normal" or "grumpy" to standard out. [samples] ## Note Please make sure to use the stream flushing operation after each query in order not to leave part of your output in some buffer.

如果你曾经接触过猫，你可能注意到它们对如何抚摸它们非常挑剔。以下是普通猫的大概分布图。然而，有些猫无法忍受人类的这种胡闹。以下是暴躁猫的分布图。你遇到了一只猫。你能判断出它是普通猫还是暴躁猫吗？这是一个交互式问题。最初你不会获得任何关于这只猫的信息。相反，这只猫被划分为十个区域，编号从 0 到 9。在一次查询中，你可以选择抚摸哪个区域，并将对应的编号输出到标准输出。你会通过标准输入获得猫的反应，反应内容如对应图中所示。为简化起见，所有反应均以小写字母形式给出。一旦你确定了你面对的是哪种猫，请向标准输出输出 "normal" 或 "grumpy"。请确保在每次查询后执行流刷新操作，以避免部分输出滞留在缓冲区中。 ## Interaction 这是一个交互式问题。最初你不会获得任何关于这只猫的信息。相反，这只猫被划分为十个区域，编号从 0 到 9。在一次查询中，你可以选择抚摸哪个区域，并将对应的编号输出到标准输出。你会通过标准输入获得猫的反应，反应内容如对应图中所示。为简化起见，所有反应均以小写字母形式给出。一旦你确定了你面对的是哪种猫，请向标准输出输出 "normal" 或 "grumpy"。 [samples] ## Note 请确保在每次查询后执行流刷新操作，以避免部分输出滞留在缓冲区中。

Let the cat's type be an unknown binary variable $ c \in \{ \text{normal}, \text{grumpy} \} $. There are 10 discrete areas indexed by $ i \in \{0, 1, \dots, 9\} $. For each area $ i $, define a response function $ r_i: \{ \text{normal}, \text{grumpy} \} \to \{ \text{response}_{\text{normal}}, \text{response}_{\text{grumpy}} \} $, where each response is a known lowercase string (from the given maps). Given: - For each $ i $, the response $ r_i(\text{normal}) $ and $ r_i(\text{grumpy}) $ are distinct and fixed (i.e., for every $ i $, $ r_i(\text{normal}) \ne r_i(\text{grumpy}) $). Goal: Determine $ c $ using the minimum number of adaptive queries. In each query, select an index $ i $, receive $ r_i(c) $, and based on the accumulated responses, deduce $ c $. Output: $ c \in \{ \text{normal}, \text{grumpy} \} $ once uniquely determined.

API Response (JSON)

{
  "problem": {
    "name": "B. A Map of the Cat",
    "description": {
      "content": "If you have ever interacted with a cat, you have probably noticed that they are quite particular about how to pet them. Here is an approximate map of a normal cat. <center>![image](https://espresso.c",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF952B"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "If you have ever interacted with a cat, you have probably noticed that they are quite particular about how to pet them. Here is an approximate map of a normal cat.\n\n<center>![image](https://espresso.c...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "如果你曾经接触过猫，你可能注意到它们对如何抚摸它们非常挑剔。以下是普通猫的大概分布图。\n\n然而，有些猫无法忍受人类的这种胡闹。以下是暴躁猫的分布图。\n\n你遇到了一只猫。你能判断出它是普通猫还是暴躁猫吗？\n\n这是一个交互式问题。最初你不会获得任何关于这只猫的信息。相反，这只猫被划分为十个区域，编号从 0 到 9。\n\n在一次查询中，你可以选择抚摸哪个区域，并将对应的编号输出到标准输出。你会通过标准输入...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "Let the cat's type be an unknown binary variable $ c \\in \\{ \\text{normal}, \\text{grumpy} \\} $.  \nThere are 10 discrete areas indexed by $ i \\in \\{0, 1, \\dots, 9\\} $.  \nFor each area $ i $, define a re...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments