1101 : KRUSKA
Problem type : Batch
Time limit : 1.0 second(s)
Memory limit : 64 megabyte(s)
Problem type : Batch
Time limit : 1.0 second(s)
Memory limit : 64 megabyte(s)
Aladdin รู้สึกเบื่อกับชีวิตในวัง เขามีการงานที่มั่นคง มีภรรยาชื่อ Jasmine และคงกำลังจะมีลูกในเร็ว ๆ นี้ ชีวิตของเขากำลังจะน่าเบื่อหน่ายและเพื่อเตรียมตัวให้พร้อมกับสิ่งเหล่านี้ เขาจึงตัดสินใจที่จะเริ่มต้นการผจญภัยอีกครั้งก่อนที่จะลงหลักปักฐานที่นี่
เขาจึงตัดสินใจที่จะหาลูกแพร์ทองคำ วัตถุที่มีค่ามากมายมหาศาลในตำนานซึ่งยังไม่มีใครค้นพบเลย
ทะเลทรายที่ Aladdin จะต้องไปค้นหา สามารถจำลองแบบเป็นกริดของเซลล์ขนาด N*N กริด แถวและคอลัมน์ต่าง ๆ จะถูกนับจำนวนจาก 1 ถึง N ซึ่งนับจากบนลงล่างและจากซ้ายไปขวา และเซลล์บางส่วนในทะเลทรายจะมีพ่อมดที่ช่วยให้ Aladdin เดาทางที่แตกต่างไปจากเดิมด้วย
Aladdin เริ่มต้นการเดาของเขาจากมุมบนซ้ายของทะเลทรายในวันจันทร์ โดยหันหน้าไปทางขวา การเคลื่อนที่ของเขาจะเป็นการทำขั้นตอนเหล่านี้ซ้ำ ๆ กัน ดังนี้
มีคำทำนายเก่าแก่ได้กล่าวไว้ว่า หลังจากการเปลี่ยนแปลงทิศทาง 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 ก็ทำตามนั้นและพบขอบของทะเลทราย เขาจึงหันหลังกลับและพบลูกแพร์ในที่สุด
ความช่วยเหลือ: ไม่มีคำใบ้สำหรับปัญหานี้
เขาจึงตัดสินใจที่จะหาลูกแพร์ทองคำ วัตถุที่มีค่ามากมายมหาศาลในตำนานซึ่งยังไม่มีใครค้นพบเลย
ทะเลทรายที่ Aladdin จะต้องไปค้นหา สามารถจำลองแบบเป็นกริดของเซลล์ขนาด N*N กริด แถวและคอลัมน์ต่าง ๆ จะถูกนับจำนวนจาก 1 ถึง N ซึ่งนับจากบนลงล่างและจากซ้ายไปขวา และเซลล์บางส่วนในทะเลทรายจะมีพ่อมดที่ช่วยให้ Aladdin เดาทางที่แตกต่างไปจากเดิมด้วย
Aladdin เริ่มต้นการเดาของเขาจากมุมบนซ้ายของทะเลทรายในวันจันทร์ โดยหันหน้าไปทางขวา การเคลื่อนที่ของเขาจะเป็นการทำขั้นตอนเหล่านี้ซ้ำ ๆ กัน ดังนี้
- ถ้าเซลล์ปัจจุบัน มีพ่อมดที่ตื่นแล้ว ให้ Aladdin หมุนตัวไปทางซ้ายหรือขวา 90 องศาขึ้นกับสิ่งที่พ่อมดบอก
- ถ้าการเคลื่อนที่ตรงไปข้างหน้าแล้วจะทำให้ Aladdin ออกไปจากทะเลทราย ให้เขาหมุนตัวกลับ 180 องศา
- การเคลื่อนที่ไปข้างหน้า 1 เซลล์ของ Aladdin จะใช้เวลา 1 วันเต็ม
มีคำทำนายเก่าแก่ได้กล่าวไว้ว่า หลังจากการเปลี่ยนแปลงทิศทาง 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 |
ความช่วยเหลือ: ไม่มีคำใบ้สำหรับปัญหานี้
กำลังออนไลน์: 18 ผู้เยี่ยมชมและ 0 สมาชิก (0 บอท)