#E. [POI 2023/2024 R1] Satelity

    Type: RemoteJudge 5000ms 512MiB

[POI 2023/2024 R1] Satelity

You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

译自 XXXI Olimpiada Informatyczna - I etap Satelity

题目描述

2n2n 个卫星,1n1\sim n 属于 A 公司,n+12nn+1\sim 2n 属于 B 公司。

两个卫星应当能够通信当且仅当它们属于同一个公司或者有额外要求。

你需要给每个卫星分配一个等长的独一无二的识别码,识别码应当只包含字母 ABC,两个卫星实际能够通信当且仅当识别码有至少一位相同。要求你的识别码方案满足要求。输出你的方案。

输入格式

本题多测,读入直到文件结束。

对于每组数据,第一行三个正整数 n,p,Mn,p,M,其中 MM 意为你的识别码长度不得超过 MM

接下来 pp 行,每行两个正整数,表示这两个卫星有额外要求应当能够通信。

输出格式

对于每组数据,第一行一个正整数 m(1mM)m(1\leq m\leq M),表示你的方案的识别码长度。

接下来 2n2n 行,每行一个长度为 mm 的只含 ABC 的字符串,识别码。

3 4 4
1 4
2 6
3 4
3 6

3
ABA
AAC
BAA
BBB
CCB
BCC

见附件
见附件
见附件
见附件
2 1 4
1 4

2
AB
AC
BA
BB

提示

单个输入文件不超过 40MB,请使用较快的输入输出方式。

对于所有测试点,1n2×1061\leq\sum n\leq 2\times 10^61n21071\leq\sum n^2\leq10^7

对于所有数据,2n10002\leq n\leq10001pn21\leq p\leq n^2

子任务编号 附加限制 分值
1 n100n\leq100M=n2+2nM=n^2+2n 7
2 M=3nM=3n 11
3 M=n+2log2nM=n+2\lceil\log_2n\rceil 23
4 M=n+2M=n+2 41
5 M=n+1M=n+1 18

周四下午训练

Not Attended
Status
Done
Rule
IOI
Problem
5
Start at
2025-2-20 8:00
End at
2025-2-20 17:00
Duration
9 hour(s)
Host
Partic.
6