以下页面来自日本信息收集官方发布的原题PDF,已完整保存并渲染到本地。


可复制的 PDF 提取文本
Japanese Olympiad In Informatics 2009/2010
Spring Training Camp
March 19 - 25, 2010, Komaba/Yoyogi, Tokyo
Contest day 2 - DNA synthesizer
DNA の合成(DNA synthesizer)
A,T,G,C からなるDNA 鎖が2 本あるとき, 一方の先頭と, 他方の末尾の部分に1 文字以上の連続する共通
部分を持つものをつなげて新しいDNA 鎖を合成する方法が開発された. このとき共通部分は一つにまとめ
られる. たとえば,TTTATGC とATGCAAA は,前者の末尾と後者の先頭に共通部分ATGC を持つので,つ
なげてTTTATGCAAA を合成できる. また,AAA を2 つ用いて,AAAA とAAAAA のどちらも合成するこ
とができる.今,新薬開発のために,研究室にあるいくつかの素DNA 鎖から,あるDNA 鎖を合成したい.
課題(TASK)
研究室にはN 種類の素DNA 鎖がある.上記の方法で素DNA 鎖をつなぎあわせて目的のDNA 鎖を合成
するとき, 最小で何本の素DNA 鎖が必要となるかを求めるプログラムを作成せよ. ただし,素DNA 鎖の備
蓄には余裕があるので,同じ種類の素DNA 鎖を何度でも使うことができる.また,全ての採点データにお
いて,目的のDNA 鎖を得る素DNA 鎖の組み合わせが存在する.
制限(CONSTRAINTS)
素DNA 鎖の種類数N は50,000 以下である.
合成したいDNA 鎖の長さは150,000 以下である.
素DNA 鎖の長さは20 以下である.
入力(INPUT)
標準入力から以下の入力を読み込め.
• 1 行目には整数N が書かれている.
• 2 行目には,A,T,G,C からなる文字列が書かれており, 目的のDNA 鎖を表す.
• 続くN 行は,1 行につき1 つのA,T,G,C からなる文字列が書かれており,それぞれ1 つの素DNA 鎖
を表す.重複する素DNA 鎖は存在しない.
出力(OUTPUT)
標準出力に必要となる素DNA の本数の最小値を表す1 つの整数を出力せよ.
採点基準(GRADING)
30 点分のテストグループにおいて,N と,合成したいDNA 鎖の長さは共に1,000 を超えない.
Page 1 of 2
Japanese Olympiad In Informatics 2009/2010
Spring Training Camp
March 19 - 25, 2010, Komaba/Yoyogi, Tokyo
Contest day 2 - DNA synthesizer
入出力例(EXAMPLE)
入力例(Sample Input) 出力例(Sample Output)
5 4
ATATATGCCCAT
ATAT
ATG
GCCC
GCCCAT
CAT
同じ素DNA 鎖を何度も使って良いことに注意せよ.
入力例(Sample Input) 出力例(Sample Output)
1 5
AAAAAAAAAA
AAA
AAA を2 つ用いて,AAAA とAAAAA のどちらも合成することができる.
入力例(Sample Input) 出力例(Sample Output)
2 5
ATATATATAT
ATA
TAT
Page 2 of 2