← 返回题目列表

AtCoder · ahc028_a

A. 幸运的话

中文机器翻译题面 查看原题

故事

在日本,新年期间会举办名为“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

显示示例

输入生成

让 \mathrm{rand}(L,U) 是一个生成均匀随机整数的函数 L 和 U,包括在内。

的一代 (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 按字典顺序排列。

工具(输入生成器和可视化工具)

请注意,比赛期间禁止分享可视化结果或讨论解决方案/想法。


示例输入 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