#P15991. [PA 2026] 矩阵编码 / Kodowanie macierzami
[PA 2026] 矩阵编码 / Kodowanie macierzami
题目描述
Algosia 和 Bajtek 非常忙碌。他们没有时间想出原创的题目,更没有时间互相发送 大小的矩阵——而这正是他们参加今年信息学奥林匹克决赛时不得不做的事情。
Algosia 想要将某个正整数传递给 Bajtek。不幸的是,正如他们最近常遇到的情况一样,隔在他们之间的是一套非常先进的计算机系统。Algosia 可以向计算机输入一个 的二进制矩阵,随后系统会对该矩阵的行和列进行置换,并将其发送给 Bajtek。请编写一个程序,帮助 Algosia 和 Bajtek 进行 次数字的编码与解码。
实现细节
这是一道通信题。你的程序将以两个副本运行——一个代表 Algosia,另一个代表 Bajtek。每次运行在输入的第一行会收到单词 Algosia 或 Bajtek,用以指明该副本负责哪一方的行为。
两个程序在收到各自的单词后,还会立即在输入中获得两个整数 和 (,),分别表示被编码数字的上限以及测试用例的数量。随后进行 次交互。
在第 次交互开始时,Algosia 收到一个整数 ()。她应在输出中打印 10 行,每行包含 10 个字符。每个字符应等于 0 或 1。该矩阵的行和列将被置换后,以相同格式发送至 Bajtek 进程的输入。Bajtek 进程在收到矩阵后,应在输出中打印出 Algosia 所编码的数字 。打印该数字后,下一个测试用例开始。
每次输出片段后,必须刷新输出缓冲区,例如通过调用 cout.flush() 或 fflush(stdout)。
注意事项
- 下面描述的交互对应名为 kod0a.in 的第一个示例测试。
- 两个程序同时启动。程序的运行时间以交互器从启动到结束的实际时间来计量。
- Algosia 只有在 Bajtek 解码出上一个数字之后,才会收到下一个数字。
- Bajtek 的进程在读取 和 之后,无需阻塞等待输入,可以利用 Algosia 进程编码第一个数字期间的时间进行任意计算。在极端情况下,这可以使程序速度提升至两倍。
输入格式
见「实现细节」。
输出格式
见「实现细节」。
提示
示例交互
| 交互器 → Algosia | Algosia → 交互器 | 交互器 → Bajtek | Bajtek → 交互器 | 说明 |
|---|---|---|---|---|
| Algosia | Bajtek | 交互器告知 Algosia 和 Bajtek 的程序副本各自的身份。 | ||
| 双方得知将有两个测试用例,且每个用例中待传递的最大数字不超过 。 | ||||
| Algosia 收到待编码的数字 。 | ||||
| $\texttt{1110000000}\\\texttt{1000000000}\\\texttt{0000000000}\\\texttt{0000000000}\\\texttt{0000000000}\\\texttt{0000000000}\\\texttt{0000000000}\\\texttt{0000000000}\\\texttt{0000000000}\\\texttt{0000000000}$ | Algosia 发送编码数字 的矩阵。 | |||
| $\texttt{0000000000}\\\texttt{0000100000}\\\texttt{0000000000}\\\texttt{0000000000}\\\texttt{0000000000}\\\texttt{0000000000}\\\texttt{0100100001}\\\texttt{0000000000}\\\texttt{0000000000}\\\texttt{0000000000}$ | Bajtek 收到列和行被置换后的矩阵。 | |||
| Bajtek 报告从矩阵中解码出数字 。 | ||||
| Algosia 收到待编码的数字 。 | ||||
| $\texttt{1110000000}\\\texttt{1000000000}\\\texttt{1000000000}\\\texttt{1000000000}\\\texttt{1000000000}\\\texttt{1000000000}\\\texttt{1000000000}\\\texttt{1000000000}\\\texttt{1000000000}\\\texttt{1000000000}$ | Algosia 发送编码数字 的矩阵。 | |||
| $\texttt{0000000100}\\\texttt{0000000100}\\\texttt{1000000101}\\\texttt{0000000100}\\\texttt{0000000100}\\\texttt{0000000100}\\\texttt{0000000100}\\\texttt{0000000100}\\\texttt{0000000100}\\\texttt{0000000100}$ | Bajtek 收到列和行被置换(可能与之前方式不同)后的矩阵。 | |||
| Bajtek 报告从矩阵中解码出数字 。 |
评分
测试数据集由 组组成,每组可得 或 分。各组对 值的限制如下:
| 组号 | |
|---|---|
| 1 | |
| 2 | |
| 3 | |
| 4 | |
| 5 | |
| 6 | |
| 7 | |
| 8 | |
| 9 | |
| 10 |
本地测试
在"文件"部分提供了交互器 kodsoc.cpp。文件中提供的交互器在发送给 Bajtek 之前不会对矩阵进行置换;除此区别外,它与 SIO 上评测提交所用的交互器对选手程序进行完全相同的交互。运行命令如下:
python3 kodrun.py [解答] < [测试]
其中 kodsoc.cpp 和 o1.h 必须位于同一文件夹中。交互器接受的输入格式在 kodsoc.cpp 文件的注释中有所描述。可通过运行命令 python3 kodrun.py -h 了解 kodrun.py 脚本的其他选项。
公平竞赛规则
禁止通过交互流程以外的方式在两个程序之间进行通信,例如通过一个程序延迟发送动作并由另一个程序读取时钟。如果评委发现程序之间存在非法通信的尝试,该提交可能被取消,情节严重者可能被取消参赛者在整个比赛中的资格。