故事
在日本,新年期间会举办名为“Kakizome Taikai”的传统书法比赛。 AtCoder 的 Kakizome Taikai 活动中,每位员工不再用毛笔书写,而是在具有特殊按键布局的键盘上打字,并将他/她最喜欢的字符串输出到 PC 屏幕上进行演示。
通过算命得知今年的许多幸运字后,首席执行官高桥决定输出一个包含所有幸运字的字符串作为(连续的)子字符串(称为 幸运串)。
例如,如果幸运的话是 AC, WA,和 CE,那么 WHITESPACE 不是 幸运串 因为它不包含 WA 作为子字符串,但是 FACEWASH 是 幸运串 因为它包含所有幸运字作为子字符串。
在键盘上移动和键入手指所需的时间取决于按键之间的距离。 因为高桥在演示顺序中排在第一位,所以他想输入一个 幸运串 尽快。 请帮助他创建一个程序来确定如何移动他的手指。
问题陈述
您将获得一个以 N \times N 网格。 让 (0, 0) 是左上角正方形的坐标,并且 (i, j) 是所在正方形的坐标 i 向下平方并 j 方块。 每个方格包含一个大写英文字母 A_{i,j},最初,手指放在正方形上 (s_i, s_j).
你被给予 M 字符串 t_1,\cdots,t_M 由大写英文字母组成。 包含所有的字符串 t_k as(连续)子字符串被定义为 幸运串。 以空字符串开头 S,目标是使 S a 幸运串 通过执行以下操作不超过 5000 次。
- 指定正方形 (i, j),将手指移至该方块,然后追加 A_{i, j} 到结束 S。如果操作前手指所在的方格坐标为 (i', j'),此操作的成本为 |i-i'|+|j-j'|+1。方块 (i, j) 和 (i', j') 可以相同,在这种情况下,产生的成本为 1.
找到一个操作序列,使得 S a 幸运串 以尽可能低的成本。
评分
让 K 是数量 t_k 包含在 S 作为(连续)子字符串,以及 T 是运营总成本。 然后你将获得以下分数。
- If K\lt M, \mathrm{round}(1000 \times (K+1)/M).
- If K=M, \mathrm{max}(10000-T, 1001).
如果操作次数超过 5000,或者如果在 指定了 N\times N 网格,则判断为 WA.
共有150个测试用例,提交的分数是每个测试用例的总分。 如果您的提交产生非法输出或超出某些测试用例的时间限制,则提交本身将被判断为 WA or TLE ,提交的分数将为零。 比赛期间获得的最高分将决定最终排名,比赛结束后不进行系统测试。 如果超过一名参赛者获得相同分数,则无论提交时间如何,他们都将排名在同一位置。
输入
输入由标准输入按以下格式给出:
N M
s_i s_j
A_{0,0}A_{0,1}\cdotsA_{0,N-1}
A_{1,0}A_{1,1}\cdotsA_{1,N-1}
\vdots
A_{N-1,0}A_{N-1,1}\cdotsA_{N-1,N-1}
t_1
\vdots
t_M
- N=15
- M=200
- 0\le s_i,s_j\le N-1
- A_{i,0}A_{i,1}\cdots A_{i,N-1} 是一个长度为的字符串 N 由大写英文字母组成。
- t_k 是一个长度为的字符串 5 由大写英文字母组成。
- t_k\ne t_{k'} (k\ne k')
- 对于每个大写字母 c,保证至少存在一个坐标 (i,j) 这样 A_{i,j}=c.
输出
让 L 是操作次数并且 (i_l, j_l) (0\le i_l, j_l\le N-1) 是在 l-第次操作。 然后,按以下格式输出到标准输出。
i_1 j_1 \vdots i_L j_L
输入生成
的一代 (s_i,s_j)
生成 s_i=\mathrm{rand}(0, N-1) 和 s_j=\mathrm{rand}(0, N-1).
的一代 A_{i,j}
对于每个 (i, j),生成 A_{i,j} 统一从大写英文字母中随机抽取。 如果存在未包含在任何大写字母中的大写字母 A_{i,j},重新生成所有 A_{i,j}.
的一代 t_k
对于每个 k,生成字符串 t_k 长度 5 通过随机生成大写英文字母 5 次。 如果已经有生成的 t_{k'} 与 t_k=t_{k'},再生 t_k。 最后,排序 t_1, t_2, \cdots, t_M 按字典顺序排列。
工具(输入生成器和可视化工具)
- 网页版:这个比本地版本更强大,可以显示动画。
- 本地版本: 你需要一个编译环境 Rust 语言.
- Windows 预编译二进制文件:如果你不熟悉Rust语言环境,请使用这个。
请注意,比赛期间禁止分享可视化结果或讨论解决方案/想法。
示例输入 1
15 200 0 14 AWVECXNGDCNGBMQ URGNCIDJOVTHSOB KIGBCYVNJUYVRWC EIXOMNZZLEBHWOX DLPDTIFGWMQOMAQ YSUDWSIOQRTBURH DKTQGUCVOJIYSPP SVLNHOOCDLDAMNF JLFXHXINKYBVCGU ESYKRPBSPYJIWZU LRGACNSZRPKESVK HDMSMPEBCXCTZTX KMIXHCXJFZICBJX TEGKFZOGIQLONVD LVBIWLIHLAGARHI ABYNP AOTLX ARZVJ ASPBI AXFSO AZPGI BCPZL BENRS BOVIS BUBNT BYUJQ CBYSK CINAP CNCBN COOUV COPDO CQQZD DADKB DGXFM DLQFC DQNCL DRGYV DSDUU DWIZI DZMWP EBYAI EKKOD EKYQJ EMLYM EQLUL ERGRD ERWVW ESLTA FBGKH FBPWX FCTHA FOIOY FTPWX FVJEJ FYZVJ GCSZE GEBGT GEPUH GVLGE GWTIL GYEZT HCGWP HEQWH HFXXC HGWEW HIPKG HKHVZ HUCSQ HWNQT HXIOS IEOTI IFMJA IKFLQ IKOTA ILQFS IQTXL IRNAB IXTRT IZFIV JBWWJ JDYNL JHWXZ JKIRA JNPBO JODMD JOWSW JRMIO JXUSI JYCOD JYKWU KASYC KDZPV KRJKE KVINZ KZKQA LEZYS LHICS LMLSY LNUCX MBPRA MEAPP MFJNA MFRNF MLXDV MNQSF MUSXF MXRFN MYGLL NJGES NQZTU NRKRQ NTAPK NYOWZ OAUQD OKRRY OMIAK ONPWH OUFYF OXASM OXSMM PBAMY PEJQR PJFGR PJXXR PMQAC PMXFC POLAM PPPAD PRSKX PSGLI PUORC PUUUP PVNSO PXUII PZEPP QDMII QDXYM QHHZU QLNRU QNDEH QNWKI QPCPS QULFB QVVVG RGHTR RGQWY RHYGF RIELA RMAKH ROVKG RSSYP RSULP RWBAX SICZS SJBBE SNCZK SUMHS SXEZH SYXFA TANTF TDVIQ TGMCV THIWA TLUET TMAYP TQCSB TXYKE UAQKR UGHLN UJKSD ULGYC UNUSS UWNUQ VBUYH VCUMT VIRUK VMXTJ VNVCN VPBGX WBWLB WCNUF WHAXY WKAKT WNMDP WPHPJ WULBH WVFWE WVYTO WWCBS WWUFL XESTB XHYES XKDGD XKHYZ XMOJJ XPCQR XQEHC XSOKS XTGPA XTLCE XXSWV XXVDA YAPDH YBDJA YCNGF YLDQD YLFGP YNBDS YQGBT YVJLV YYPIT ZBGGI ZORJO ZQMBO ZYYVG
示例输出 1
1 13 2 14 4 10 5 8 3 7 4 3 6 1 7 3 9 4 8 8 5 9 4 10 8 11 8 11 10 13 14 10 13 10 10 9 9 14 8 14 9 14 6 13