1101 : KRUSKA
Problem type : Batch
Time limit : 1.0 second(s)
Memory limit : 64 megabyte(s)
Aladdin รู้สึกเบื่อกับชีวิตในวัง เขามีการงานที่มั่นคง มีภรรยาชื่อ Jasmine และคงกำลังจะมีลูกในเร็ว ๆ นี้ ชีวิตของเขากำลังจะน่าเบื่อหน่ายและเพื่อเตรียมตัวให้พร้อมกับสิ่งเหล่านี้ เขาจึงตัดสินใจที่จะเริ่มต้นการผจญภัยอีกครั้งก่อนที่จะลงหลักปักฐานที่นี่
เขาจึงตัดสินใจที่จะหาลูกแพร์ทองคำ วัตถุที่มีค่ามากมายมหาศาลในตำนานซึ่งยังไม่มีใครค้นพบเลย
ทะเลทรายที่ Aladdin จะต้องไปค้นหา สามารถจำลองแบบเป็นกริดของเซลล์ขนาด N*N กริด แถวและคอลัมน์ต่าง ๆ จะถูกนับจำนวนจาก 1 ถึง N ซึ่งนับจากบนลงล่างและจากซ้ายไปขวา และเซลล์บางส่วนในทะเลทรายจะมีพ่อมดที่ช่วยให้ Aladdin เดาทางที่แตกต่างไปจากเดิมด้วย
Aladdin เริ่มต้นการเดาของเขาจากมุมบนซ้ายของทะเลทรายในวันจันทร์ โดยหันหน้าไปทางขวา การเคลื่อนที่ของเขาจะเป็นการทำขั้นตอนเหล่านี้ซ้ำ ๆ กัน ดังนี้
  1. ถ้าเซลล์ปัจจุบัน มีพ่อมดที่ตื่นแล้ว ให้ Aladdin หมุนตัวไปทางซ้ายหรือขวา 90 องศาขึ้นกับสิ่งที่พ่อมดบอก
  2. ถ้าการเคลื่อนที่ตรงไปข้างหน้าแล้วจะทำให้ Aladdin ออกไปจากทะเลทราย ให้เขาหมุนตัวกลับ 180 องศา
  3. การเคลื่อนที่ไปข้างหน้า 1 เซลล์ของ Aladdin จะใช้เวลา 1 วันเต็ม
สำหรับพ่อมดแต่ละคน เราจะรู้ตำแหน่งที่อยู่และกำหนดการกิจกรรมของเขาในแต่ละวันของสัปดาห์ โดยกำหนดการจะเป็นสายอักขระของตัวอักษร ‘L’, ‘R’ หรือ ‘S’ ทั้งหมด 7 ตัวอักษร แต่ละอักขระจะบอกเราในสิ่งที่พ่อมดกระทำในแต่ละวันของสัปดาห์นั้น ๆ โดยเริ่มต้นจากวันจันทร์ ตัวอักษร L หมายถึง Aladdin จะถูกบอกให้หมุนตัวไปทางซ้าย ตัวอักษร R หมายถึง Aladdin จะถูกบอกให้หมุนตัวไปทางขวา และตัวอักษร S หมายถึง พ่อมดนอนหลับตลอดทั้งวันนั้น
มีคำทำนายเก่าแก่ได้กล่าวไว้ว่า หลังจากการเปลี่ยนแปลงทิศทาง K ครั้ง (ในขั้นตอนที่ 1 และ/หรือ 2) Aladdin จะค้นพบลูกแพร์นั้น

งานของคุณ

จงเขียนโปรแกรมเพื่อคำนวณหาจำนวนวันทั้งหมดที่การค้นหาจะสิ้นสุด ตามคำทำนายเก่าแก่

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

ในบรรทัดแรก ประกอบด้วยเลขจำนวนเต็มของขนาดของทะเลทราย (N) และจำนวนครั้งของการเปลี่ยนแปลงทิศทางในคำทำนายเก่าแก่ (K) ซึ่งจำนวนทั้งสองมีค่า ดังนี้ 2 ≤ N ≤ 200 และ 1 ≤ K ≤ 1000000000
บรรทัดที่สอง คือ เลขจำนวนเต็มของจำนวนพ่อมด (M) ซึ่งมีค่า 0 ≤ M ≤ 10000
ในแต่ละ M บรรทัดถัดมา คือ เลขจำนวนเต็มแสดงแถว (R) และคอลัมน์ (C) ของตำแหน่งที่พ่อมดอยู่ ซึ่งมีค่าดังนี้ 1 ≤ R, C ≤ N และตามด้วยสายอักขระแสดงกำหนดการกิจกรรมของพ่อมดซึ่งจะประกอบด้วยสายอักขระของตัวอักษร ‘L’, ‘R’ และ ‘S’ ทั้งหมด 7 ตัวอักษร
ไม่มีพ่อมดอยู่ในเซลล์เดียวกันถึง 2 คนและไม่มีพ่อมดคนไหนอยู่ในเซลล์ (1, 1)

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

ให้แสดงผลระยะเวลาที่ใช้ในการค้นหา หน่วยเป็นวัน

การให้คะแนน

ในกรณีทดสอบ จะได้รับคะแนนเป็นครึ่งหนึ่งของคะแนนทั้งหมด ถ้า K มีค่ามากที่สุดที่ 1000

ที่มา: COCI 2008/2009, Contest #5 – February 7, 2009

ในตัวอย่างที่ 1 Aladdin เคลื่อนที่ 2 ครั้งจะพบขอบของทะเลทราย ดังนั้น เขาจึงหมุนตัวไป 180 องศาและพบลูกแพร์
ในตัวอย่างที่ 2 Aladdin พบพ่อมดคนแรกในวันที่ 3 แต่พ่อมดกำลังนอนหลับอยู่ ดังนั้น Aladdin จึงยังคงเดินต่อไปในทิศทางเดิม หลังจากนั้นอีก 2 วัน เขาพบพ่อมดอีกคนที่บอกให้เขาหมุนตัวไปทางซ้าย และ Aladdin ก็ทำตามนั้นและพบขอบของทะเลทราย เขาจึงหันหลังกลับและพบลูกแพร์ในที่สุด

ตัวอย่างข้อมูลนำเข้า ตัวอย่างข้อมูลส่งออก
3 1
0
2
5 2
2
1 3 RRSRRRR
1 5 RRRRLRR
4
5 5
3
1 3 SSRSSSS
3 3 SSSLSSS
4 3 SSRSSLS
10

ความช่วยเหลือ: ไม่มีคำใบ้สำหรับปัญหานี้

กำลังออนไลน์: 22 ผู้เยี่ยมชมและ 0 สมาชิก (1 บอท)