SWERC12 - ประวัติรุ่นแก้ไข

Nattee เมื่อ 04:59, 14 พฤษภาคม 2556

2013-05-14T04:59:44Z

Nattee เมื่อ 18:12, 13 พฤษภาคม 2556

2013-05-13T18:12:16Z

125.25.106.174: หน้าที่ถูกสร้างด้วย '== RNA Secondary Structure (Problem D) == Online Judge: [http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=sho...'

2013-05-13T16:28:09Z

หน้าที่ถูกสร้างด้วย '== RNA Secondary Structure (Problem D) == Online Judge: [http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=sho...'

หน้าใหม่

== RNA Secondary Structure (Problem D) ==

Online Judge: [http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=3992]

RNA หรือ Ribonucleic Acid เป็นโครงสร้างพื้นฐานของโมเลกุล ซึ่งประกอบด้วยสายโซ่ของส่วนประกอบที่เรียกว่า nucleotides โดย nucleotide นั้นมีอยู่ 4 แบบ เรียกว่าฐาน ซึ่งเขียนแทนด้วยตัวอักษา A, C, G หรือ U โครงสร้างหลักของ RNA นั้นประกอบด้วยฐานดังกล่าวนี้ เราจะกล่าวถึงโครงสร้างรองของ RNA ซึ่งก็คือการจับคู่ของฐานต่าง ๆ โดยที่ฐาน A สามารถจับคู่ได้กับฐาน U และ ฐาน C จับคู่กับฐาน G ความเสถียรของ RNA นั้นขึ้นอยู่กับจำนวนคู่ฐานที่จับกันได้ โครงสร้างสุดท้ายของ RNA คือ โครงสร้างที่มีการจับคู่มากที่สุด

กำหนดให้โครงสร้างหลักนั้นถูกอธิบายด้วยสายอักขระ ของตัวอักษร ACGU กฎของโครงสร้างของโครงสร้างรองเป็นดังต่อไปนี้

# ฐาน A ใด ๆ สามารถจับกับฐาน U ได้
# ฐาน C ใด ๆ สามารถจับกับฐาน G ได้
# ฐานแต่ละฐานนั้นสามารถจับคู่ได้เพียงคู่เดียว
# กำหนดให้ w < x และ y < z และ w < y ถ้าฐานซึ่งอยู่ ณ ตำแหน่ง w จับคู่กับ ฐาน ณ ตำแหน่ง x และ ฐาน ณ ตำแหน่ง y จับคู่กับฐาน ณ ตำแหน่ง z แล้ว เงื่อนใขหนึ่งในสองข้อต่อไปนี้จะต้องเป็นจริง
## y > x
## z < x
## การจับคู่ระหว่าง C กับ G นั้นไม่สามารถมีได้เกิน K คู่

คุณจะได้รับสายอักขระที่อธิบายถึงโครงสร้างหลักของสิ่งมีชีวิตชนิดหนึ่ง หน้าที่ของคุณคือคำนวณจำนวนการจับคู่ในโครงสร้างสุดท้ายที่ตรงกับเงื่อนไขข้างต้นนี้

โครงสร้างหลักที่มีให้นั้นจะอยู่ในรูปแบบ Run Length Encoding ซึ่งอักขระที่เหมือนกันที่อยู่ติดกันนั้นจะถูกลดรูปเป็นอักขระตามด้วยตัวเลขที่บอกจำนวนตัวที่อยู่ติดกัน ตัวอย่างเช่น “AAAACCGAAUUG” สามารถเขียนได้เป็น “A4C2G1A2U2G1” กล่าวโดยละเอียดคือโครงสร้างหลักนั้นจะอยู่ในรูปแบบ <math><c_1f_1c_2f_2c_3f_3 ... c_nf_n></math> โดยที่ <math>c_i</math> จะเป็น A, C, G หรือ U และ <math>f_i</math> จะเป็นตัวเลขจำนวนเต็มบวก

นอกจากนี้ เรายังทราบว่าสิ่งมีชีวิตที่เรากำลังศึกษาอยู่นั้นมีลักษณะดังต่อไปนี้

# <math>f_1 + f_2 + f_3 + ... f_n <= 10050</math>
# <math>f_1 <= 5000</math>
# <math>f_n <= 5000</math>
# <math>f_2 + f_3 + f_4 + ... + f_{n-1} <= 50</math>

=== ข้อมูลนำเข้า ===
บรรทัดแรกมีค่า T <= 200 ซึ่งระบุจำนวน Test Case ทั้งหมด โดยแต่ละ Test Case เป็นดังต่อไปนี้
* บรรทัดแรกประกอบด้วย run length encoding ของ RNA
* บรรทัดที่สองประกอบด้วยค่า K (0 <= K <= 20) ซึ่งระบุจำนวนคู่ C-G มากสุดที่สามารถมีได้
=== ข้อมูลส่งออก ===
ในแต่ละ Test Case ให้พิมพ์หมายเลขของ Test Case ตามด้วยจำนวนการจับคู่มากสุดที่สามารถทำได้

=== ตัวอย่างและภาพประกอบ ===
ให้ดูจาก http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=3992

@@ แถว 5: / แถว 5: @@
 ผึ้งอยู่ในป่าและผึ้งจะเก็บเกษรจากต้นไม้ในป่านี้ ต้นไม้แต่ละต้นกำกับด้วยหมายเลข 0 ถึง n-1 ผึ้งมีรายการของทางเดิน ซึ่งเป็นเส้นตรงที่เชื่อมต่อระหว่างต้นไม้สองต้น ผึ้งจะไม่บินออกนอกทางเดินเด็ดขาด และทางเดินนี้สามารถใช้เดินทางได้ทั้งสองทิศทาง
-ผึ้งกำลังวางแผนจะสร้างรังผึ้งใหม่ขึ้นมีหลาย ๆ รังบนต้นไม้บางต้น โดยมีเป้าหมายคือผึ้งจะเลือกสร้างรังบนต้นไม้ที่จำเป็นเท่านั้น และผึ้งจะไม่เก็บเกษรจากกต้นไม้ที่ไม่มีรังอยู่ อย่างไรก็ตาม ผึ้งยังคงต้องการเดินทางจากรังต่าง ๆ ไปยังรังต่าง ๆ ดังนั้น ผึ้งต้องการสร้างรังให้ผิ้งสามารถเดินทางไปมาระหว่างรังต่าง ๆ ได้ ถึงแม้ว่าจะมีทางเดิน 1 ทางในรายการทางเดินนั้นใช้งานไม่ได้ขึ้นมา
+ผึ้งกำลังวางแผนจะสร้างรังผึ้งใหม่ขึ้นมีหลาย ๆ รังบนต้นไม้บางต้น โดยมีเป้าหมายคือผึ้งจะเลือกสร้างรังบนต้นไม้ที่จำเป็นเท่านั้น และผึ้งจะไม่เก็บเกษรจากกต้นไม้ที่ไม่มีรังอยู่ ดังนั้น ผึ้งจะลบทางเดินที่มิได้เชื่อมต่อระหว่างต้นไม้ที่มีรังอยู่ทิ้งไปทั้งหมด
 นอกจากนี้ ผึ้งต้องการที่จะสร้างรังอย่างน้อยสองรัง (เพราะรังเดียวไม่พอทำกิน) แต่ก็ไม่ต้องการสร้างรังเกินความจำเป็น จากข้อมูลของต้นไม้และทางเดินที่มีอยู่ จงหาว่า ผึ้งต้องสร้างรังกี่รังจึงจะตรงตามข้อกำหนดดังกล่าว (ในบางกรณี ผึ้งอาจจะไม่สามารถสร้างรังตามเงื่อนไขดังกล่าวได้เช่นกัน)

@@ แถว 1: / แถว 1: @@
 == RNA Secondary Structure (Problem D) ==
@@ แถว 35: / แถว 57: @@
 === ตัวอย่างและภาพประกอบ ===
 ให้ดูจาก  http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=3992