← 返回题目列表

AtCoder · joisc2010_dna

dna. DNA合成(DNA合成仪)

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

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

DNAの合成 (DNA Synthesizer) - 原题 PDF 第 1 页
原题PDF第3页
DNAの合成 (DNA Synthesizer) - 原题 PDF 第 2 页
原题PDF第4页
可复制的 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