เป็นเรื่องที่น่าสนใจมากที่เราสามารถนำคอมพิวเตอร์มาใช้ในการวิเคราะห์ข้อมูลทางชีววิทยา เช่น ข้อมูลของลำดับ DNA ได้ สาย DNA ประกอบด้วยนิวคลีโอไทด์ (Nucleotide) สี่ชนิดคืออะดีนีน (Adenine), ไซโตซีน (Cytosine), กัวนีน (Guanine) และ ไทมีน (Thymine) ซึ่งนีวคลีโอไทด์ทั้งสี่ชนิดนี้สามารถแทนด้วยตัวอักขระ A, C, G, และ T ตามลำดับ ดังนั้นข้อมูลของสาย DNA จะ สามารถแทนได้ด้วยสายอักขระที่ประกอบด้วยอักขระทั้งสี่ตัวนี้ เราจะเรียกสายอักขระนี้ว่า ลำดับ DNA

                มีความเป็นไปได้ที่นักชีววิทยาไม่สามารถที่จะระบุชนิดของนีวคลีโอไทด์บางตัวในสาย DNA ในกรณีดังกล่าวนักชีววิทยาจะใช้ตัวอักขระ N เพื่อแทน DNA ที่ไม่สามารถระบุชนิดได้ หรือกล่าวอีกนัยหนึ่งว่าอักขระ N เป็นอักขระตัวแทนที่ใช้แทนอักขระตัวใดก็ได้จาก A, C, G หรือ T เราเรียกลำดับ DNA ที่ประกอบด้วยตัวอักขระ N ตั้งแต่หนึ่งตัวขึ้นไปว่า ลำดับไม่สมบูรณ์ ในทางกลับกันเราจะเรียกลำดับ DNA ที่ไม่มีตัวอักขระ N อยู่เลยว่า ลำดับสมบูรณ์ และเราจะเรียกลำดับสมบูรณ์ตัวหนึ่งว่า เข้ากันได้ กับลำดับไม่สมบูรณ์อีกตัวหนึ่งถ้าเราสามารถสร้างลำดับสมบูรณ์ตัวนั้นจากการแทนที่ตัวอักขระ N ในลำดับไม่สมบูรณ์ด้วยตัวอักขระ แทนนีวคลีโอไทด์ตัวใดตัวหนึ่งจากทั้งสี่ชนิด ตัวอย่างเช่น ACCCT เข้ากันได้กับ ACNNT แต่ AGGAT เข้ากันไม่ได้

                นักวิจัยจะเรียงลำดับนิวคลีโอไทด์ทั้งสี่ตามลำดับของตัวอักษรภาษาอังกฤษ นั่นคือ A มาก่อน C, C มาก่อน G และ G มาก่อน T ลำดับ DNA จะถูกจัดประเภทเป็น รูปแบบ-1 ถ้าทุกนิวคลีโอไทด์ในลำดับนั้นเป็นตัวเดียวกับนิวคลีโอไทด์ที่ติดกันทางขวาหรือ เป็นตัวที่มีลำดับมาก่อน ตัวอย่างเช่น AACCGT เป็นลำดับรูปแบบ-1 แต่ AACGTC ไม่เป็น

                ในกรณีทั่วไปลำดับ DNA จะเรียกว่า รูปแบบ-j สำหรับ j > 1 ถ้าลำดับนั้นเป็นลำดับรูปแบบ-(j − 1) หรือ เกิดจากลำดับรูปแบบ-(j − 1) ต่อกับลำดับรูปแบบ-1 ตัวอย่างเช่น AACCC, ACACC, และ ACACA เป็นลำดับรูปแบบ-3 แต่ GCACAC และ ACACACA ไม่ใช่

                เช่นเดียวกันนักวิจัยเรียงลำดับ DNA ตามลำดับของคำในพจนานุกรมภาษาอังกฤษ ดังนั้นลำดับ DNA ตัวแรกในรูปแบบ-3 ที่มีความยาว 5 คือAAAAA และ ลำดับตัวสุดท้ายคือ TTTTT ตัวอย่างอีกอันหนึ่งของลำดับเจ็ดตัวแรกของลำดับสมบูรณ์รูปแบบ-3 ที่เข้ากันได้กับลำดับไม่สมูบรณ์ ACANNCNNG คือ:

ACAAACAAG

ACAAACACG

ACAAACAGG

ACAAACCAG

ACAAACCCG

ACAAACCGG

ACAAACCTG

งานของคุณ

เขียนโปรแกรมเพื่อหาลำดับในรูปแบบ-K ตัวที่ R ที่เข้ากันได้กับลำดับไม่สมบูรณ์ที่มีความยาว M ที่กำหนดให้

ข้อมูลนำเข้า

บรรทัดแรก ประกอบด้วยตัวเลขจำนวนเต็มสามตัว M (1 ≤ M ≤ 50, 000), K (1 ≤ K ≤ 10), และ R  (1 ≤ R ≤ 2 × 10¹²) แยกจากกันด้วยช่องว่างหนึ่งช่อง

บรรทัดที่สอง ประกอบด้วยสายอักขระความยาว M ซึ่งเป็นลำดับไม่สมูบรณ์ เรารับประกันว่า ลำดับรูปแบบ-K ที่เข้ากันได้กับลำดับไม่สมบูรณ์จะมีจำนวนไม่เกิน 4 × 10¹⁸ ดังนั้นตัวเลขดังกล่าวจะสามารถแทนได้ด้วย long long ในภาษา C และ ภาษา C++ หรือ Int64 ในภาษาปาสคาล นอกจากนี้ R จะมีค่าไม่เกินจำนวนของลำดับรูปแบบ-K ที่เข้ากันได้กับลำดับไม่สมบูรณ์ที่กำหนดให้

ข้อมูลส่งออก

ให้พิมพ์ข้อมูลเพียงบรรทัดเดียวที่แสดงถึงลำดับในรูปแบบ-K ตัวที่ R ที่เข้ากันได้กับลำดับไม่สมบูรณ์ที่มีความยาว M ที่กำหนดให้

ข้อแนะนำในการเขียนโปรแกรม

ในภาษา C และ ภาษา C++ คุณควรประกาศชนิดข้อมูลเป็น long long ชุดคำสั่งต่อไปนี้แสดงตัวอย่างการอ่านและพิมพ์ค่าของข้อมูลชนิด long long จาก standard input/output

                long long a;

                scanf("%lld",&a);

                printf("%lld\n",a);

ในภาษาปาสคาล คุณควรประกาศชนิดข้อมูลเป็น Int64 ซึ่งไม่จำเป็นต้องใช้ชุดคำสั่งเฉพาะในการจัดการกับข้อมูลชนิดนี้

การให้คะแนน

ในแต่ละชุดข้อมูลทดสอบคุณจะได้ 100% ถ้าผลลัพธ์ถูกต้องในชุดข้อมูลนั้น และจะได้ 0% ในกรณีที่ตอบผิด

ในกรณีของชุดทดสอบที่มีค่า 20 คะแนน M จะมีค่าไม่เกิน 10

ที่มา: Asia-Pacific Informatics Olympiad 2008