故事
人类遗传信息记录在具有双螺旋结构的DNA中,并由由四个字符组成的很长的字符串表示, A, G, C,和 T。
最近,在一块陨石中发现了外星细胞。
研究结果发现,这个外星人的基因信息记录在一个 环面形状的材料并表示为 N\times N 由八个字符组成的矩阵, A, B, C, D, E, F, G,和 H。
现有的设备无法直接读取这个矩阵,但它们已经成功地读取了许多垂直或水平连续的一维子序列。
请根据此信息估计矩阵。
问题陈述
我们定义一维序列 矩阵的 b=(b_0, \ldots, b_{k-1}) 是 子序列 字符串 $$$y$$$ 的 矩阵的 a=(a_{i,j})_{0\leq i,j\leq N-1} 当且仅当存在 (i, j) 至少满足以下两个条件之一:
- 对于所有人 p=0,\ldots,k-1, b_p=a_{i,(j+p)\bmod N} 成立。 (水平匹配)
- 对于所有人 p=0,\ldots,k-1, b_p=a_{(i+p)\bmod N,j} 成立。 (垂直匹配)
请注意,如果索引大于或等于 N,我们将余数除以 N (换句话说, a 在左右两端、上下两端连接)。
鉴于 M 字符串 s_1, \ldots, s_M 由八个字符组成, A, B, \ldots, H,你的目标是找到一个 N\times N 由字符组成的矩阵 A, B, \ldots, H,或 . 其中包含尽可能多的给定字符串的子序列。
在这里, . 表示空。
评分
让 c (\leq M) 是数量 i是这样的 s_i 是输出矩阵的子序列,令
输出中包含 d (\leq N^2) 是数量 . 。
然后,您将获得以下分数。
- If c<M, \mathrm{round}(10^8\times \frac{c}{M}).
- If c=M, \mathrm{round}(10^8\times \frac{2 N^2}{2 N^2-d}).
如果输出非法(不是 N\times N 矩阵,或包含除 A, B, \ldots, H, .),判断为 WA。
有100个测试用例,提交的分数是每个测试用例的总分。
如果您得到的结果不是 AC 对于一个或多个测试用例,提交的分数将为零。比赛时间内获得的最高分将决定最终排名,比赛结束后不进行系统测试。
如果超过一名参赛者获得相同分数,则排名将根据获得该分数的提交作品的提交时间来确定。
输入
输入由标准输入按以下格式给出:
N M s_1 \vdots s_M
- N 在所有测试用例中固定为 20。
- M 是满足以下条件的整数 400\leq M\leq 800.
- 每个 s_i 是由字符组成的字符串
A,B, \ldots,H,其长度最小为 2,最大为 12。
输出
输出 N 行,每行包含一个长度完全相同的字符串 N 由字符组成 A, B, \ldots, H,或 ..
输入生成
让 \mathrm{rand}(L,U) 是一个生成均匀随机整数的函数 L 和 U,包括在内。
我们首先生成一个 N\times N 矩阵 a=(a_{i,j})_{0\leq i,j\leq N-1} 通过均匀随机地生成每个元素 A, B, \ldots, H。
然后我们生成一个参数 L=\mathrm{rand}(4, 10),决定字符串的平均长度,以及字符串的数量 M=\mathrm{rand}(400, 800)。
我们生成 M 字符串 s_1,\ldots,s_M 重复以下过程 M 次。
我们生成两个整数 i=\mathrm{rand}(0, N-1) 和 j=\mathrm{rand}(0, N-1) 代表起点,整数 d=\mathrm{rand}(0,1) 代表方向,整数 k=\mathrm{rand}(L-2, L+2) 表示字符串的长度。
- If d=0,我们选择水平子序列 (a_{i,j},a_{i,(j+1)\bmod N},\ldots,a_{i,(j+k-1)\bmod N}).
- If d=1,我们选择一个垂直子序列 (a_{i,j},a_{(i+1)\bmod N,j},\ldots,a_{(i+k-1)\bmod N,j}).
工具
- 输入:用于本地测试的一组 100 个输入(种子 0-99),包括样本输入(种子 0)。这些输入与实际测试用例不同。
- 网络上的可视化工具
- 输入生成器和可视化工具:如果您想使用更多输入,或者如果您想在本地可视化输出,则可以使用此程序。你需要一个编译环境 Rust 语言.
样本输入 1
20 742 AFHCGEH HDBCHG EAHC ABHDG DGAHHG GAHHGB DHBBEB GEAD GCEBD GHGFGA BHC BAGCCB CAF HBGGC AHEBA FBGEB GHGFGA CFA FEHB GDCEFBE BACEGGG CBA GEHDC CFACHAF ACGBA CEE AADDCCH GGDHHHC EDAEE ECA EBEED BGCAH AEAH GFCGEH CGAGHE HAGEA FEA CEDHAG EEH AGHECFC EFGDDA DCCHGD ADDHB FCGF BAGE CFA HBCE CGFG CEFECCB BADEBDD AGACG DCAGGCE HEHHDB DDHDB HCFFAB HEBDADD DGFCGFG AFFFBCG FCEAC EGGG DADDC EDH BHCAACH GCE HAHGB BFFDAHE CFAEAHC ACCHE BFH CHDC CFHDCB DED GACG HECFCFE FEAFEH CADFGE GCHD BEEHEG GDH FBEHHB FHAG BGCAHDC DCCCE GDH CCBA GEH EDEHH HHDBCH HGB EHD CFFABFC DGG DBHEC GEAGCFE CCGAGHE DHAGAC CCCGHH CBBFFDA EFA DFGD HDCAADD HDCFC GHECFCF CCDDE AFC CCE DAHD FAGFCB FEC DHAGG EGEFAG CGDD AACCHE FFC HED FBCFFHD BAGE HEBD GBBE DHBCEFG CAAAEAA DBFG GHCC DEGGE BCGCHD EEA BEE ECG DHHHCCA CHD GCDECG FFCCFAE HGH EGFB CFFEGE GEADHAG GBGDCHD EFGC BEHHB DBECC DCFF CFE DCADDHG ADHAGGB ABD DAEEGF DEG CHFFHGH CGAGH FCCB FHGHD EBGCAHD CFHDC FEHB FHC CHGDHBB EDBECCD DCF GBADEB AAHF CEFECC DCGA HAFHFE HDCAAD GDH CEF DCBDFDE GDHHHCC FCCC GAGHE CHFEE GDD HEDEHHD BDD HCAHC EEH GBG HEDEG GAFAHB BBFHB DGF BCHGFCC GCCFACH FAGAE DBFGDC GHDD GGE FFFBCG EGGGE CCCEE GABCHED EDHA EFAGA FHDCAD GGGD DHBGGCC DHAGACG GECCH FABFCD GCC CCE EADHAG EEHEG FDAD DFH AFC DCCCE CGE EBDCCC GBDGEAB CAHCBH CGCHD FGAEDDB FAGAFAH HEEFBDC HAGGBAH DCCEFEC ADH CHEDE DAFHCG BCFA GDCBDF HDC FFGEH EAEFHC DDCHCA GHGD HGGGD EGFCF CADF GGCCGA CGDDAA DDAACC DDHDGG GDHEDA HEBDAD DCGHG EFHG BHDGAA ADDCCHG FBGEBG GFEGHE CFAA CFDE FCBBG BDCC GBBEAFD GDFCA GHEDG BDGEABH ADCFGAE HHGBCF AAHAFHF EDA CHGDH DDDFHEH HDCA CDCF FCFH CDGAH CHEDEHH CCBHEBD FBC HHDBC CEE FGCFA CEBDCCC BEAFDEF HHDB AEGECE HHCCA HDDHBCE GEH HBADFFB BECC GCAHDCA DBAEEHD DGAACA EEH EAFEHDC FFHGHDD BFEHB AHDCAA BADFF CHCEDH CGHAHG CCCGHH AEEGFED DFGDDEF GDDAAC GEC CDAC GBDGEAB HGCBFEH CFA CEBE BHDGA FHEHHD BFHB AGCDE AFCDEDD GGAA FACAA EDA CCG EHFBCF HGBBEA AGFCB EAADBA CFAEAH AAHFCEA EEG DGBGD GDHHH HHCCAC EAGDDHD ECCHFE GDBC DCC EFHDFEA BBFF FGBGF HDBBEFD FCC EBGBG ADDH EBDCCCE EGG EDH DEFHGB DHCDE DCH HGBGE BAAHFC DGGAAF DGFC AEFHCCF EAFDE HFBCF DEEBEAD FDE CCD FCGFGB EGGE EDE GCDECGD EBF EGGGEB HEDAE CEBE GDHBB DABDEA HGCBFE HDCADD DEGFBAG DFBEEH GBDGEA GCEGGGE ADHAGG GDDADA FGBG HBCE AGFCEEA DCF BEHHBG DFGEA DCHDABD ADCFG BEHHB DHBGGC ADFGEAD DDH BEBGC BFEH GHH FFBCG BDDB HDCADD AHF GGD FFDAHE EGBEEHE BBGDEE EFCF CGFGB GCFE CEEF HFBG CCGA FFDAHEE GBGE GBGDCHD FGDC GCEBDC FGBGFCE EFBDCG AACC CBHCAAC GDDAD AAHA GAFF CBAAHFC GAF GAFAHBE CCGAG DHA CEA BCEFGCF CEDCAGG HFB AGHGCB AADD BCGC EDCA GCF BEADECD AHDBEA FBCG GHCCE EBDC DCAD AGCD FHFEDB FCE FEAADDH BGC GGEBD EABGF AGE CGDBC FEAFEHD CGH DABDEA CAHCB EDFGDDE DAA EAGAFF DAH AFAHBE DCBA DCB BGC FFHDC FAGFCB ECFCF CFAAFFF HGHDDCH BGCB AHDB BACE FCCD ACEDDHD CEF BFEH EGBFEA GEHFBC GBDGA HGCEG DBCFHA ADE CGHG GDHHHCC GFG DHEDAE ECEEA BHCHCE HAF FCEE CCBAG CEGGGE DDCHCAH EFHC AED FGBGFCE HEG AEE BGEBGBG ADDHBG GFGABC GDEC BGEBGB EAEF BBG GBGDH FCGEH BEEHEG EACBCEG GEAB GBFE HDAB EEDAF ACBCEG FEGHEDG HCAAC HFBGEBG HGCBF GEBGBG BAAHA EBEED CCEFAGA BAD FHBGDEG AACAAA EGF AEF ECEG AGGCEBD CEBDCCC DCCEF FGAB HGDFCAA AACGBD AAGFC AHC FEBCC EDE BBGDEED AACC CAAC EGDCE DCFFGEH BCEG CEDHAG GHE AFCD BGCBBFH DHBCEF BGBGD DECGDDA HDBAGEC HGCBFEH HHDBCHG AGDDHD EECGHA DDF DHB EEB HEBDA DEDDH EEFFAG HCHCED DDAAC EEHAGEA EFA HCC CCFDEE FCFHDC GHED DFBE EADHAGG GGEB AGHGC HBBEBG AHDCAA CCGAG HGBGEE FEEF EECGHA CCHED ECGHAHG EEDAFH FBAGCDE HAGACG FAGA DBH HEBDA HHCCACE BEBGCAH HDDH FFECHD HDAB DACAF AEEHAGE GFCG HDDDF HHDBA HGFGA HDF CCHGD AGGBA DBAGE GGAAFF GDBC CHDABD FFB DHBB BDAH DDH HDF GAED EADECDC DDBA AAGFCEE EGFBAGC DDCCEF GFC CGF HDFE BDCCCE HGD EEFB CCACED EAFDEF HDCFCE BBEF FAG HBEGBE EDAEE FHE CGH FGDEC AEA CAAD DCF DDBH GBGDCH AAGFC DCB DEBAA BEFDADC ECEBE GHGD EDEGFBA DBCFH AFA FGC DABD DDCC AAHAFH FCFEA DBHCH BBEB AGDD CCGA DGACG EBCCED FEGHE DBA GFCEEAG FFHDCA HDCG FBCGC FFGEHDC CFEA FDEBA EADCBA CCBAGC FHCGEH ADEBFCB DCFFGEH CEDD HECFC GGCEBD GGG EBGCA FGEHD DDCH EGECEDC CHD FACH EGEFA GFEDHFB FFEG ECCB DBAGEC EEFG AGE CHCAH AHEB GBD AHE GAGHEC CEACBCE DBCFHAG FCEA DAH CACED CCHFEE ACEDD CBFEHBA CBC BFCDG EGHCCE DDFBE EAGCF FFE AFFECHD AHH HAF HHB HFBGEBG CDDEG CCCEEA CCFFE ABFCDGA CGCHDD EEAADBA ACEDDHD BACEG FEB FECHDC FCEEF FHG AEFH HFEDB AFFE GFG EGFBA BEEHEG AACCH AEDDB EAFD DBAC GBGDHED FHB BHDG HDCG EDGB EDDHDBA FCB CFHAGH GFED FCCDBF ABG CHFEE DBBEFD FAEEHAG EBFC FGDECE CDGAH DAC GEHDC BEFDADC GBGF EECG CEEAAD EHHBGC GAEDFCC HAFH EAAGF CAFC EHH
示例输出 1
FFGAEEABCE.CBAEBH.C. EHBFHCGHFGA.G.AE.AAC .GBAED.ACHBDG.GDGG.C DDFADEGGBDEFFACBB.FA .EFBFGEEDGHBCGCEDEEB HAAHBDAGBCCE.CCADAFH GAFFE.G.CBEG.F.DDCEE ACE.F.GDAAGH.DHECDBA DAFB.HHFBABHEBBBD.CE EGFFHDGEHFBAB.DECADA DEAHCFGG..CG.BGDBBEC .CBAGCAFCDEBGACEHF.D GG.CGFA.GHGHG.GG.EHH CECG.G.DGBCCAACFCDH. FB.DH.F.CEHEH.CGGHFB ADHCH.HCCBFGBADFBACE CE.EHC.AAGADC.FAAEFB ED.F..HGEACAHACFGAGG AADAABC.CA.GF.CADCAF CFAHEFGCA.CFGFGECBCH