[POI 2023/2024 R1] Satelity

Luogu
IDLGP9924
Time5000ms
Memory512MB
DifficultyP7
POI(波兰)2023Special Judge构造
有 $2n$ 个卫星,$1\sim n$ 属于 A 公司,$n+1\sim 2n$ 属于 B 公司。 两个卫星**应当**能够通信**当且仅当**它们属于同一个公司或者有额外要求。 你需要给每个卫星分配一个等长的**独一无二**的识别码,识别码应当只包含字母 `ABC`,两个卫星**实际**能够通信**当且仅当**识别码有至少一位相同。要求你的识别码方案满足要求。输出你的方案。 ## Input 本题多测,读入直到文件结束。 对于每组数据,第一行三个正整数 $n,p,M$,其中 $M$ 意为你的识别码长度不得超过 $M$。 接下来 $p$ 行,每行两个正整数,表示这两个卫星有额外要求应当能够通信。 ## Output 对于每组数据,第一行一个正整数 $m(1\leq m\leq M)$,表示你的方案的识别码长度。 接下来 $2n$ 行,每行一个长度为 $m$ 的只含 `ABC` 的字符串,识别码。 [samples] ## Background 译自 [XXXI Olimpiada Informatyczna - I etap](https://sio2.mimuw.edu.pl/c/oi31-1/dashboard/) [Satelity](https://sio2.mimuw.edu.pl/c/oi31-1/p/sat/)。 ## Note 单个输入文件不超过 40MB,请使用较快的输入输出方式。 对于所有测试点,$1\leq\sum n\leq 2\times 10^6$,$1\leq\sum n^2\leq10^7$。 对于所有数据,$2\leq n\leq1000$,$1\leq p\leq n^2$。 | 子任务编号 | 附加限制 | 分值 | | :----------: | :----------: | :----------: | | 1 | $n\leq100$,$M=n^2+2n$ | 7 | | 2 | $M=3n$ | 11 | | 3 | $M=n+2\lceil\log_2n\rceil$ | 23 | | 4 | $M=n+2$ | 41 | | 5 | $M=n+1$ | 18 |
Samples
Input #1
3 4 4
1 4
2 6
3 4
3 6
Output #1
3
ABA
AAC
BAA
BBB
CCB
BCC
Input #2
见附件
Output #2
见附件
Input #3
见附件
Output #3
见附件
Input #4
2 1 4
1 4
Output #4
2
AB
AC
BA
BB
API Response (JSON)
{
  "problem": {
    "name": "[POI 2023/2024 R1] Satelity",
    "description": {
      "content": "有 $2n$ 个卫星,$1\\sim n$ 属于 A 公司,$n+1\\sim 2n$ 属于 B 公司。 两个卫星**应当**能够通信**当且仅当**它们属于同一个公司或者有额外要求。 你需要给每个卫星分配一个等长的**独一无二**的识别码,识别码应当只包含字母 `ABC`,两个卫星**实际**能够通信**当且仅当**识别码有至少一位相同。要求你的识别码方案满足要求。输出你的方案。",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 5000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P7"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP9924"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "有 $2n$ 个卫星,$1\\sim n$ 属于 A 公司,$n+1\\sim 2n$ 属于 B 公司。\n\n两个卫星**应当**能够通信**当且仅当**它们属于同一个公司或者有额外要求。\n\n你需要给每个卫星分配一个等长的**独一无二**的识别码,识别码应当只包含字母 `ABC`,两个卫星**实际**能够通信**当且仅当**识别码有至少一位相同。要求你的识别码方案满足要求。输出你的方案。\n\n## Inp...",
      "is_translate": false,
      "language": "English"
    }
  ]
}
Full JSON Raw Segments