2007 : Writing
Problem type : Batch
Time limit : 3.0 second(s)
Memory limit : 32 megabyte(s)
Problem type : Batch
Time limit : 3.0 second(s)
Memory limit : 32 megabyte(s)
การถอดรหัสข้อความภาษามายันนั้นยากลำบากกว่าที่นักบุกเบิกยุคแรกๆ คิดไว้ หลังการค้นคว้าเกือบสองร้อยปี ภาษานี้ก็ยังเป็นที่เข้าใจได้น้อยมาก ความก้าวหน้าที่แท้จริงเพิ่งจะเกิดขึ้นเมื่อสามทศวรรษที่ผ่านมานี้เอง
ในการเขียนภาษามายันนั้นจะใช้กลุ่มสัญลักษณ์ที่เรียกว่า “กลิฟ” (glyph) ซึ่งจะแทนเสียงต่างๆ คำในภาษามายันจะเขียนโดยใช้กลิฟหลายๆ ตัวนำมาเขียนต่อกันในตำแหน่งต่างๆ
ปัญหาหนึ่งในการถอดรหัสข้อความมายันเกี่ยวข้องกับลำดับของการอ่าน ในการเขียนกลิฟหลายๆ ตัว เพื่อประกอบเป็นคำหนึ่งคำขึ้นมานั้น นักเขียนชาวมายันสามารถเลือกตำแหน่งในการเขียนตามอารมณ์สุนทรีย์ของตนโดยไม่จำเป็นต้องคำนึงถึงกฎเกณฑ์ใด ๆ การขาดกฏเกณฑ์นี้สร้างปัญหาแก่นักโบราณคดีโดยทำให้เกิดความสับสนในการอ่านคำที่เขียนออกมาทั้งๆ ที่ทราบวิธีการออกเสียงกลิฟต่างๆ แล้ว
นักโบราณคดีต้องการค้นหาคำพิเศษ W เขาทราบกลุ่มของกลิฟที่ประกอบเป็นคำนี้ แต่ว่าไม่ทราบวิธีการเรียงต่อกันทั้งหมดที่เป็นไปได้ เนื่องจากเขาทราบว่าคุณมาแข่ง IOI’06 เขาจึงขอร้องให้คุณช่วย เขาจะให้กลิฟ g ตัวของคำ W และลำดับ S ของกลิฟทั้งหมดตามลำดับที่ปรากฏในแผ่นบันทึกที่เขากำลังศึกษา ให้คุณช่วยเขาโดยการนับจำนวนครั้งของการปรากฏที่เป็นไปได้ของคำ W
งานของคุณ
เขียนโปรแกรมที่รับกลิฟของ W และลำดับ S ของกลิฟในแผ่นบันทึก จากนั้นจงนับจำนวนการปรากฏที่เป็นไปได้ทั้งหมดของ W ใน S นั่นคือให้นับทุก ๆ ลำดับที่ต่อเนื่องกันของกลิฟ g ตัวใน S ที่เป็นการเรียงสับเปลี่ยน (permutation) ของ กลิฟใน W
เงื่อนไข
1 ≤ g ≤ 3000 จำนวนกลิฟใน W
g ≤ |S| ≤ 3 000 000 โดยที่ |S| แทนจำนวนกลิฟในลำดับ S
ข้อมูลนำเข้า
บรรทัดที่ 1: มีจำนวนเต็มสองจำนวนที่คั่นด้วยช่องว่าง แทน g และ |S|
บรรทัดที่ 2: มีอักขระ g ตัวติดต่อกันแทนกลิฟใน W อักขระที่เป็นไปได้คือ ‘a’-‘z’ และ ‘A’-‘Z’ อักขระพิมพ์ใหญ่และอักขระพิมพ์เล็กจะถือว่าแตกต่างกัน
บรรทัดที่ 3: มีอักขระ |S| ตัวติดต่อกันที่แสดงกลิฟในแผ่นบันทึก อักขระที่เป็นไปได้คือ ‘a’-‘z’ และ ‘A’-‘Z’ อักขระพิมพ์ใหญ่และอักขระพิมพ์เล็กจะถือว่าแตกต่างกัน
ข้อมูลส่งออก
บรรทัดที่ 1: จะต้องมีจำนวนครั้งที่เป็นไปได้ที่ W ปรากฏใน S
ที่มา: International Olympiad in Informatics 2006 Maxico
ความช่วยเหลือ: Hint[1]
ในการเขียนภาษามายันนั้นจะใช้กลุ่มสัญลักษณ์ที่เรียกว่า “กลิฟ” (glyph) ซึ่งจะแทนเสียงต่างๆ คำในภาษามายันจะเขียนโดยใช้กลิฟหลายๆ ตัวนำมาเขียนต่อกันในตำแหน่งต่างๆ
ปัญหาหนึ่งในการถอดรหัสข้อความมายันเกี่ยวข้องกับลำดับของการอ่าน ในการเขียนกลิฟหลายๆ ตัว เพื่อประกอบเป็นคำหนึ่งคำขึ้นมานั้น นักเขียนชาวมายันสามารถเลือกตำแหน่งในการเขียนตามอารมณ์สุนทรีย์ของตนโดยไม่จำเป็นต้องคำนึงถึงกฎเกณฑ์ใด ๆ การขาดกฏเกณฑ์นี้สร้างปัญหาแก่นักโบราณคดีโดยทำให้เกิดความสับสนในการอ่านคำที่เขียนออกมาทั้งๆ ที่ทราบวิธีการออกเสียงกลิฟต่างๆ แล้ว
นักโบราณคดีต้องการค้นหาคำพิเศษ W เขาทราบกลุ่มของกลิฟที่ประกอบเป็นคำนี้ แต่ว่าไม่ทราบวิธีการเรียงต่อกันทั้งหมดที่เป็นไปได้ เนื่องจากเขาทราบว่าคุณมาแข่ง IOI’06 เขาจึงขอร้องให้คุณช่วย เขาจะให้กลิฟ g ตัวของคำ W และลำดับ S ของกลิฟทั้งหมดตามลำดับที่ปรากฏในแผ่นบันทึกที่เขากำลังศึกษา ให้คุณช่วยเขาโดยการนับจำนวนครั้งของการปรากฏที่เป็นไปได้ของคำ W
งานของคุณ
เขียนโปรแกรมที่รับกลิฟของ W และลำดับ S ของกลิฟในแผ่นบันทึก จากนั้นจงนับจำนวนการปรากฏที่เป็นไปได้ทั้งหมดของ W ใน S นั่นคือให้นับทุก ๆ ลำดับที่ต่อเนื่องกันของกลิฟ g ตัวใน S ที่เป็นการเรียงสับเปลี่ยน (permutation) ของ กลิฟใน W
เงื่อนไข
1 ≤ g ≤ 3000 จำนวนกลิฟใน W
g ≤ |S| ≤ 3 000 000 โดยที่ |S| แทนจำนวนกลิฟในลำดับ S
ข้อมูลนำเข้า
บรรทัดที่ 1: มีจำนวนเต็มสองจำนวนที่คั่นด้วยช่องว่าง แทน g และ |S|
บรรทัดที่ 2: มีอักขระ g ตัวติดต่อกันแทนกลิฟใน W อักขระที่เป็นไปได้คือ ‘a’-‘z’ และ ‘A’-‘Z’ อักขระพิมพ์ใหญ่และอักขระพิมพ์เล็กจะถือว่าแตกต่างกัน
บรรทัดที่ 3: มีอักขระ |S| ตัวติดต่อกันที่แสดงกลิฟในแผ่นบันทึก อักขระที่เป็นไปได้คือ ‘a’-‘z’ และ ‘A’-‘Z’ อักขระพิมพ์ใหญ่และอักขระพิมพ์เล็กจะถือว่าแตกต่างกัน
ข้อมูลส่งออก
บรรทัดที่ 1: จะต้องมีจำนวนครั้งที่เป็นไปได้ที่ W ปรากฏใน S
ที่มา: International Olympiad in Informatics 2006 Maxico
| ตัวอย่างข้อมูลนำเข้า | ตัวอย่างข้อมูลส่งออก |
| 4 11 cAda AbrAcadAbRa | 2 |
ความช่วยเหลือ: Hint[1]
กำลังออนไลน์: 22 ผู้เยี่ยมชมและ 0 สมาชิก (0 บอท)