Gcj2011
Round 3
C. Perpetual Motion
Source: [1]
คุณเคยไปโรงงานเล็มมิ่งของกูเกิ้ลไหม? มันเป็นสถานที่ที่แปลกมาก พื้นของโรงงานจะถูกแบ่งเป็นตารางกริดขนาด R x C ในแต่ละช่องกริด จะมีสายพานที่อาจจะมีทิศทางขึ้นลง ซ้ายขวา หรือในทิศทแยงทั้งสองแบบ สายพานนี้หมุนได้สองแบบในทิศทางที่มันติดตั้งไว้ และนอกจากนี้ คุณยังสามารถเลือกทิศการหมุนของแต่ละสายพานแต่ละเส้นได้อย่างเป็นอิสระต่อกัน
(ดูรูปประกอบจากลิงก์ด้านบน)
เมื่อเริ่มต้น มีเล็มมิ่งอยู่ที่ตรงกลางของทุก ๆ ช่องกริด เมื่อคุณเริ่มให้สายพานทำงาน เล็มมิ่งแต่ละตัวจะเคลื่อนที่ไปในทิศทางของสายพานจนไปอยู่ที่กลางช่องใหม่ในทิศที่สายพานเคลื่อนที่ การเคลื่อนที่นี้เกิดขึ้นพร้อม ๆ กัน และใช้เวลาหนึ่งวินาทีพอดี หลังจากนั้นเล็มมิ่งทุกตัวจะอยู่ที่กลางช่องใหม่ และกระบวนการเคลื่อนที่ก็จะเริ่มอีกครั้งไปเรื่อย ๆ ไม่มีวันสิ้นสุด (หรือจนกระทั่งคุณปิดเครื่อง)
- เมื่อเล็มมิ่งเข้าไปยังช่องใหม่ เขาจะยังเคลื่อนที่ไปในทิศทางเดิมจนกระทั่งไปถึงกลางช่อง เขาจะไม่ได้รับผลกระทบจากสายพานใหม่จนกระทั่งการเคลื่อนที่ในวินาทีถัดไปเริ่มขึ้น
- ถ้าเล็มมิ่งเคลื่อนที่ตกขอบของกริด เขาจะโผล่ขึ้นที่ตำแหน่งเดียวกันที่อีกด้านของกริด ยกตัวอย่างเช่น ถ้าเขาเคลื่อนที่ไปในทิศทาง ขึ้น-ซ้าย และทะลุขอบที่กริดชองบนซ้ายสุด เขาจะปรากฏขึ้นที่ขอบล่างของช่องขวาสุด ด้วยความสามารถของวิทยาศาสตร์ เหตุการณ์เคลื่อนที่นี้ก็ยังเกิดขึ้นภายในเวลา 1 วินาทีเช่นเดียวกับการเคลื่อนที่อื่น ๆ
- เล็มมิ่งจะไม่เดินชนกันและสามารถเดินผ่านเล็มมิ่งอื่น ๆ ได้อย่างไม่มีความลำบากใด ๆ
เป้าหมายของเราก็คือการเลือกทิศทางให้กับสายพาน เพื่อที่จะรับประกันว่าเล็มมิ่งจะเคลื่อนที่ไปตลอดกาลโดยไม่มีเล็มมิ่งสองตัวใด ๆ ที่จะไปอยู่ที่จุดกลางของช่องใด ๆ ในเวลาเดียวกัน สังเกตว่าถ้าเหตุการณ์นั้นเกิดขึ้น เล็มมิ่งทั้งสองจะเคลื่อนที่ติดกันไปตลอดและมันไม่สนุกเลยสำหรับพวกเขา
ด้านล่าง (ดูรูปจากลิงก์) เป็นวิธีสองวิธีในการกำหนดทิศทางให้กับสายพานจากตัวอย่างสายพานในรูปข้างต้น
(ดูรูปที่ลิงก์)
ในทั้งสองกรณี เราหลีกเลี่ยงการส่งเล็มมิ่งสองตัวไปยังจุดกลางของช่องใด ๆ พร้อมกันได้
ให้แผนผังของโรงงาน คำนวณ N ซึ่งเป็นจำนวนวิธีในการเลือกทิศทางให้กับสายพาน เพื่อที่จะรับประกันว่าไม่มีเล็มมิ่งสองตัวใด ๆ ที่จะเคลื่อนที่ไปที่จุดกลางของช่องใด ๆ พร้อมกัน เนื่องจากคำตอบนั้นอาจมีค่ามหาศาล ให้ตอบคำตอบ modulo 1000003
