QOJ.ac

QOJ

Limite de temps : 1 s Limite de mémoire : 512 MB Points totaux : 10 Difficulté: [afficher]

#2119. 干扰 [C]

Statistiques

在网络通信中,使用能够确保发送方发送的数据与接收方接收的数据一致的协议至关重要。如果忽视这一点,可能会导致接收方难以正确读取消息。Bajtek 和 Bitek 就遇到了这样的情况……

Bajtek 想通过互联网向 Bitek 发送一个包含 $n$ 个小写英文字母的字符串。为此,Bajtek 的计算机将该字符串中的每个字母依次转换为其 8 位 ASCII 编码表示:

字母 ASCII 码 字母 ASCII 码
a 01100001 n 01101110
b 01100010 o 01101111
c 01100011 p 01110000
d 01100100 q 01110001
e 01100101 r 01110010
f 01100110 s 01110011
g 01100111 t 01110100
h 01101000 u 01110101
i 01101001 v 01110110
j 01101010 w 01110111
k 01101011 x 01111000
l 01101100 y 01111001
m 01101101 z 01111010

不难发现,第 $i$ 个小写英文字母($1 \le i \le 26$)的 ASCII 码即为数字 $96 + i$ 的二进制表示。

随后,Bajtek 的计算机将 $n$ 个 8 位二进制串拼接成一个长度为 $8n$ 的长二进制串,即 Bajtek 的 $n$ 个字符字符串的表示。最后,Bajtek 的计算机通过互联网将该表示发送给 Bitek 的计算机。不幸的是,每个比特都是在单独的网络数据包中发送的,因此比特到达 Bitek 时,顺序可能与原始顺序完全不同!

被打乱的比特序列最终到达了 Bitek。显然,这样的比特序列现在不一定代表任何由 $n$ 个小写英文字母组成的字符串。尽管比特序列中不包含关于其正确顺序的任何额外信息,但 Bitek 决定不放弃。他认为,他可以尝试恢复出任何一个由 $n$ 个小写英文字母组成的字符串,其 $8n$ 位的表示形式可能以这种方式到达 Bitek。请帮助他找到这样一个示例字符串,或者指出它不存在!

输入格式

第一行包含一个整数 $n$($1 \le n \le 10^5$)。 第二行包含一个长度为 $8n$ 的二进制字符串,表示 Bitek 收到的比特序列。

输出格式

如果 Bitek 收到的序列不对应任何由 $n$ 个小写英文字母组成的字符串,则输出单个单词 NIE。 否则,输出任意一个由 $n$ 个小写英文字母组成的字符串,该字符串在经过 Bajtek 的计算机编码并通过网络传输后,可能以输入中给出的比特序列形式到达。如果存在多个合法的字符串,你可以输出其中任意一个。

样例

样例输入 1

2
1100000011110111

样例输出 1

ao

样例输入 2

8
1011111010101100011011011010001010100011111111110001001001011010

样例输出 2

potyczki

样例输入 3

1
00011000

样例输出 3

NIE

说明

字母 a 的 ASCII 码为 01100001,字母 o 的 ASCII 码为 01101111。字符串 ao 发送给 Bitek 后被转换为 0110000101101111。因此,消息的比特位到达 Bitek 时顺序可能为 1100000011110111

子任务

在某些组别中,答案总是存在的。此外,在这些组别中,比特在从 Bajtek 到 Bitek 的传输过程中,仅在其所属的 ASCII 码内部改变了顺序。换句话说,没有任何比特超出了其原始字母所占的 8 个位置。尽管如此,在恢复字符串时,你仍然可以自由地交换比特的位置。

Editorials

IDTypeStatusTitlePosted ByLast UpdatedActions
EditorialOpen Official EditorialQingyu- Download

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.