#P18568. [ukiepc2026]Hoptimisation

[ukiepc2026]Hoptimisation

Hoptimisation

题目描述

有一排连续排列的 kk 个格子,物理位置从左到右编号为 1,2,…,k1,2,\ldots,k,相邻两个格子的距离为 11 米。

每个格子都要分配一个互不相同的名字。现在给定一份依次访问的格子名字列表 s1,s2,…,sns_1,s_2,\ldots,s_n。假设名字 ss 被分配到位置 p(s)p(s),则按照列表依次跳跃所需的总距离为

∑i=1n−1∣p(si)−p(si+1)∣.\sum_{i=1}^{n-1}|p(s_i)-p(s_{i+1})|.

你可以决定每个名字应当放置在什么位置。如果输入中出现的不同名字少于 kk 个,可以自行为未使用的格子添加其他合法、互不相同的名字。

请输出一种使总跳跃距离最小的格子命名排列。

图示(重绘示意图)

图 H.1:样例 1 中跳格名称的排列与连续访问产生的跳跃距离。

图 H.1:样例 1 中跳格名称的排列与连续访问产生的跳跃距离。 本图为重绘示意图。

输入格式

第一行输入两个整数 k,nk,n,分别表示格子数和访问列表长度。

第二行输入 nn 个仅由小写英文字母组成的非空字符串 s1,s2,…,sns_1,s_2,\ldots,s_n,表示依次访问的格子名字。

输出格式

输出 kk 个字符串,从左到右依次表示位置 11 到 kk 的格子名字。

输出的名字均应为长度不超过 1010 的小写英文字母串,且彼此不同。所有在输入中出现过的名字都必须出现恰好一次。

若存在多种最优方案,输出任意一种即可。

样例 #1

输入

5 4
hop skip hop jump

输出(答案不唯一)

anything jump hop skip something

样例 #2

输入

9 16
a b c a b c a x y z x y z e f g

输出(答案不唯一)

g f e z y x a c b

数据范围与保证

  • 1≤k≤161\le k\le16;
  • 1≤n≤1061\le n\le10^6;
  • 所有输入名字均由小写英文字母组成,长度为 11 到 1010;
  • 输入中不同名字的数量不超过 kk。