问题陈述
鉴于 m 字符串组成
C(t) = min_{x \in \{A, T, G, C, -\}} \left| \{ t[i] \; | \; t[i] \neq x \; (i=1, \ldots, m) \} \right|
C(t) 计算字符数 t 不等于出现在 t 最频繁。例如,当 t=
如果我们可以生成 S 这样的总和 C(S_{*,j}) 对于所有列都变小,预计给定 m 字符串对齐良好。我们将这样的问题称为多重对齐并定义以下分数。
C_{all}(S) = \sum_{j=1}^n C(S_{*,j})
例如,如果我们对齐三个字符串
GGATC GGAT- G-ACC
分数 C_{all}(S) 变为 C(S_{*,1}) + C(S_{*,2})+ C(S_{*,3})+ C(S_{*,4})+ C(S_{*,5}) = 0 + 1 + 0 + 1 + 1 = 3.
鉴于 m 字符串 s_{1}, \ldots, s_{m},输出多重对齐,使得 C_{all}(S) 变得尽可能小。
约束
- s_1,...,s_m 是由以下组成的字符串
A ,C ,G ,T . - 测试用例(小)
- 8 \leq m \leq 10.
- 80 \leq |s_1|, \ldots, |s_m| \leq 100 (长度 x 表示为|x|.)
- 测试用例(大)
- $35 \leq m \leq
- 700 \leq |s_1|, \ldots, |s_m| \leq 750
输入
输入由标准输入按以下格式给出:
m
s_{1}
s_{2}
:
s_{m}
输出
打印输入字符串的多重对齐,使得 C_{all} 变得尽可能小。
插入后
评审系统只能在以下情况下接受用户的输出:
- 每行等于相应的输入行,如果
示例输入 1
10 GGAGGTTATTGCTGTGGAGGTACTGGAGAAGGAGGATGCTAGCGTTGGGTAAACCACGAGCATTTTGACTTGTACTTCGCCTC GGGTTATTGCTGTTGTGAGTACTGGAGACAGGAGGGAGTGTTAGAGTTGGGGTAAACCACAGTAGCTCATGTCACTTGGATAACTCGTCAGCCTC GGTCACTCGCTGTGGAGAGTACTTTGAGACAGGAGGGAGTGCTAGAGTTTGGGGTAAAACCACAGCAGCTCATGCACTTGGATATCTGTGAGCC GAGGTTAGTGCTGTGGAGAGTACTGGAGACAGGAGGGAGTGCTAGAGTTGGGGTAAAGCACAGCACCATTCACTGATAAATGTCAGGCCTAGGGG GAGGTATTGCTGTGGAGGGTACTGGAGACAGGAGGAGTGCTAGAGGTTGGGGTAAAACCACAGCAGCTCATTTACTTGATACTGTCAGGCTCAGG GAGGTTATTTGCTGTGGAGAGTTACTGAGACATGGGGTGCCAAGTTGGGTAGCTACAGCAGCTCATTTCACTTGATACTGCAGGCTCTCAG GAGTTAATTTCGTGGAGAGTACTAGAGCACAGGAGGGAGGCCAGATTGGGGTATACCACAGCAGCTCGTTCACTTTAACTGTCAGGCCCTCA ACAGTTTAATTGATGGGCGGAGAGTACTGGAGACAGGAGGGAGTGCTAGAGTGGGGTAAACCACAGCAGCATCTTTCATTATAACTGTCAG CAAGGTTTTTTCGCTGTGGAGAGTACTGGAGACCGGGGAGTGTAGACTTTGGGGTATCACGTAGCAGCTTATTTCGACTTTGTACTGTAA GAGTTATTTCTGTGGAGAGAACTGGAGACGGAGGGAGTGCTAGAGTTGGGGTAAACACCAGGCAGCCATTTCACTTGATAACTGTCAGGCCTT
示例输出 1
GGAGGTTA-TTGCT--GTGGAG-GTAC-TGGAGA-AGGA-GGA-TGCTAGCG-TT-GGGT-AAACCAC-G-AGC-ATTTTGACTT-G-T-ACT--TC-GCCTC---- --GGGTTA-TTGCT--GTTGTGAGTAC-TGGAGACAGGAGGGAGTGTTAGAG-TTGGGGT-AAACCACAGTAGCTCATGTCACTTGGATAACTCGTCAGCCTC---- ---GGTCACTCGCT--GTGGAGAGTACTTTGAGACAGGAGGGAGTGCTAGAGTTTGGGGTAAAACCACAGCAGCTCATG-CACTTGGATATCT-GTGAG-C-C---- -GAGGTTA-GTGCT--GTGGAGAGTAC-TGGAGACAGGAGGGAGTGCTAGAG-TTGGGGT-AAAGCACAGCA-CCATTCACTGATAAATGTCAGGCCTAGGGG---- --GAGGTA-TTGCT--GTGGAGGGTAC-TGGAGACAGGA-GGAGTGCTAGAGGTTGGGGTAAAACCACAGCAGCTCAT-TTACTT-GAT-ACT-GTCAGGCTC-AGG -GAGGTTATTTGCT--GTGGAGAGTTACT-GAGACA--TGGG-GTGCCA-AG-TT-GGGT--AGCTACAGCAGCTCATTTCACTT-GAT-ACT-G-CAGGCTCTCAG --GAGTTAATTTC---GTGGAGAGTACTAGAGCACAGGAGGGAG-GCCAGA--TTGGGGT-ATACCACAGCAGCTCGT-TCACTT---TAACT-GTCAGGC-CCTCA ACAGTTTAATTGATGGGCGGAGAGTAC-TGGAGACAGGAGGGAGTGCTAGAG--TGGGGT-AAACCACAGCAGCATCTTTCA-TT--ATAACT-GTCAG-------- CAAGGTT-TTTTCGCTGTGGAGAGTAC-TGGAGAC-CG-GGGAGTG-TAGACTTTGGGGT---ATCAC-GTAG--CAGCTTATTTCG--ACTTTGT-A--CT-GTAA --GAGTTA-TTTCT--GTGGAGAGAAC-TGGAGAC-GGAGGGAGTGCTAGAG-TTGGGGT-AAACACCAGGCAGCCATTTCACTT-GATAACT-GTCAGGC-C--TT
积分
提交的程序通过两种测试用例类型进行评估:小型和大型,如约束部分中所示。 Small 包含 2 个案例,Large 包含 8 个案例。分数将给予在时间限制内满足格式的输出。 对于 Small 中测试用例的每个输出,参赛者将获得 \{200 - \lfloor C_{all}(S) * 0.2 \rfloor \} 或 0,以较大者为准。对于大型测试用例,参赛者获得 \{700 - \lfloor C_{all}(S) * 0.1 \rfloor \} 或 0,以较大者为准。例如,如果可以生成两个输出 S_1 和 S_2 限期内格式正确的小型案件,可赚取 max\{200 - \lfloor C_{all}(S_1) * 0.2 \rfloor, 0\} + max\{200 - \lfloor C_{all}(S_2) * 0.2 \rfloor, 0\}.
我们不保证最优解能够达到最高分(6000分)。最终排名由用于生成当前测试用例的相同方法生成的其他数据集决定。
测试用例的生成方法
我们提取子字符串 s 第一步来自人类参考基因组序列的 22 号染色体。 s 被提取,因此它不包括