{"problem":{"name":"[EGOI 2022] Toy Design / 玩具设计","description":{"content":"**本题是一道 Grader 交互题。** 你在一个设计玩具的公司工作。一个将被制作的玩具如下：有 $n$ 个大头针，编号从 $1$ 到 $n$，从盒子中伸出。几对大头针被铁丝在盒子中相连。（换句话说，大头针和铁丝组成了一个无向图，其中大头针是节点、铁丝是边。）铁丝无法从盒子外部看到，唯一获得关于他们的信息的方法是对大头针使用一个**检测器**：我们选择两个大头针 $i,j$（$i\\ne j$）","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":262144},"difficulty":{"LuoguStyle":"P5"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9323"},"statements":[{"statement_type":"Markdown","content":"**本题是一道 Grader 交互题。**\n\n你在一个设计玩具的公司工作。一个将被制作的玩具如下：有 $n$ 个大头针，编号从 $1$ 到 $n$，从盒子中伸出。几对大头针被铁丝在盒子中相连。（换句话说，大头针和铁丝组成了一个无向图，其中大头针是节点、铁丝是边。）铁丝无法从盒子外部看到，唯一获得关于他们的信息的方法是对大头针使用一个**检测器**：我们选择两个大头针 $i,j$（$i\\ne j$），检测器会告诉你这两个大头针是否连通，包括直接和间接。（因此，检测器告诉你图中这两个大头针之间是否有一条路径。）\n\n我们称一组连接方式为玩具的**设计方案**。\n\n你正在使用一个专用的软件来查询和进行设计。软件工作方式如下：从某个称为“$0$ 号方案”的设计方案开始。他不会告诉你盒子内部的铁丝是什么样的。你需要重复进行以下的三步操作：\n\n1. 选择一个设计方案 $a$ 和两个大头针 $i,j$（$i\\ne j$）。\n2. 软件告诉你对这两个大头针使用检测器的结果。换句话说，它告诉你在设计方案 $a$ 中 $i$ 与 $j$ 是否（直接或间接地）连通。\n3. 同时，如果这两个大头针在设计方案 $a$ 中没有被直接或间接地连接，它会创建一个新的设计方案，包含设计方案 $a$ 中的所有铁丝，同时添加一个直接连接 $i,j$ 的铁丝。这个设计方案的编号为下一个可用的编号。（所以，第一个创建的设计方案是 $1$ 号方案，然后是 $2$ 号，以此类推。）请注意这不会修改设计方案 $a$，只会新建一个设计方案包含新的铁丝。\n\n你的目标是使用这种操作获取尽可能多的 $0$ 号方案的信息。\n\n请注意并不总是可能求出 $0$ 号方案的准确的铁丝连接方式，因为无法区分直接和间接的连接。例如，考虑如下的两种 $n=3$ 的设计方案：\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/7vwojkw8.png)\n\n检测器会认为两种方案中任意一对大头针都连通，所以我们无法利用上述软件区分它们。\n\n你的目标是求出任何一种设计方案，使得它与 $0$ 号方案等价。两种设计方案**等价**当且仅当对于任意一对大头针，检测器在两种方案中都返回相同结果。\n\n## Output\n\n**交互方式**\n\n你需要实现一个函数：\n\n```cpp\nvoid ToyDesign(int n, int max_ops);\n```\n\n作用是给出一种与 $0$ 号方案*等价*的设计方案。你可以调用以下两个函数来实现这一点。你可以调用的第一个函数为：\n\n```cpp\nint Connected(int a, int i, int j);\n```\n\n其中 $1\\le i,j\\le n$，$i\\ne j$，$a\\ge 0$，且 $a$ 不能超过目前已有的设计方案数。如果在设计方案 $a$ 中，大头针 $i,j$ 是（直接或间接地）连通的，它的返回值是 $a$。否则，它的返回值是已有的设计方案数加一，就是包含 $a$ 的所有铁丝以及一根连接 $i,j$ 的铁丝的新的设计方案的编号。函数 `Connected` 可以被调用最多 `max_ops` 次。\n\n当你的程序完成了需要的 `Connected` 调用，它应该描述一种等价于 $0$ 号方案的设计方案。为了描述一个方案，程序应当调用：\n\n```cpp\nvoid DescribeDesign(std::vector<std::pair<int, int>> result);\n```\n\n参数 `result` 是整数对的向量，描述大头针之间的直接铁丝连接。每对数描述一根铁丝，包含被连接的两个大头针的编号。在任意一对（无序的）大头针对之间必须只有至多一根铁丝，且不能有铁丝连接一个大头针和它自己。一旦调用这个函数，你的程序将被终止。\n\n[samples]\n\n## Background\n\nDay 2 Problem C.\n\n题面译自 [EGOI2022 toydesign](https://stats.egoi.org/media/task_description/2022_toydesign_en.pdf)。\n\n[![CC BY-SA 3.0](https://licensebuttons.net/l/by-sa/3.0/80x15.png)](https://creativecommons.org/licenses/by-sa/3.0/)\n\n## Note\n\n**样例交互过程**\n\n|选手程序|Grader|解释|\n|:-|:-|:-|\n||`ToyDesign(4, 20)`|玩具中有 $4$ 个大头针。你需要在 $20$ 次 `Connected` 调用内，给出任何一种等价于 $0$ 号方案的设计方案。|\n|`Connected(0, 1, 2)`|返回 $1$。|大头针 $1,2$ 在 $0$ 号方案中不直接或间接地连通。新的设计方案是 $1$ 号。|\n|`Connected(1, 3, 2)`|返回 $2$。|大头针 $3,2$ 在 $1$ 号方案中不直接或间接地连通。新的设计方案是 $2$ 号。|\n|`Connected(0, 3, 4)`|返回 $0$。|大头针 $3,4$ 在 $0$ 号方案中直接或间接地连通。没有新的设计方案。|\n|`DescribeDesign({{3, 4}})`||描述一个只有一根铁丝的设计方案：连接大头针 $3,4$。|\n\n---\n\n**数据范围**\n\n对于全部数据，$2\\le n\\le 200$。\n\n- 子任务一（$10$ 分）：$n\\le 200$，`max_ops` 为 $20000$。\n- 子任务二（$20$ 分）：$n\\le 8$，`max_ops` 为 $20$。\n- 子任务三（$35$ 分）：$n\\le 200$，`max_ops` 为 $2000$。\n- 子任务四（$35$ 分）：$n\\le 200$，`max_ops` 为 $1350$。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9323","tags":["2022","交互题","Special Judge","O2优化","EGOI（欧洲/女生）"],"sample_group":[],"created_at":"2026-03-03 11:09:25"}}