Gcj2011

จาก Theory Wiki
ไปยังการนำทาง ไปยังการค้นหา

Round 3

C. Perpetual Motion

Source: [1]

คุณเคยไปโรงงานเล็มมิ่งของกูเกิ้ลไหม? มันเป็นสถานที่ที่แปลกมาก พื้นของโรงงานจะถูกแบ่งเป็นตารางกริดขนาด R x C ในแต่ละช่องกริด จะมีสายพานที่อาจจะมีทิศทางขึ้นลง ซ้ายขวา หรือในทิศทแยงทั้งสองแบบ สายพานนี้หมุนได้สองแบบในทิศทางที่มันติดตั้งไว้ และนอกจากนี้ คุณยังสามารถเลือกทิศการหมุนของแต่ละสายพานแต่ละเส้นได้อย่างเป็นอิสระต่อกัน

(ดูรูปประกอบจากลิงก์ด้านบน)

เมื่อเริ่มต้น มีเล็มมิ่งอยู่ที่ตรงกลางของทุก ๆ ช่องกริด เมื่อคุณเริ่มให้สายพานทำงาน เล็มมิ่งแต่ละตัวจะเคลื่อนที่ไปในทิศทางของสายพานจนไปอยู่ที่กลางช่องใหม่ในทิศที่สายพานเคลื่อนที่ การเคลื่อนที่นี้เกิดขึ้นพร้อม ๆ กัน และใช้เวลาหนึ่งวินาทีพอดี หลังจากนั้นเล็มมิ่งทุกตัวจะอยู่ที่กลางช่องใหม่ และกระบวนการเคลื่อนที่ก็จะเริ่มอีกครั้งไปเรื่อย ๆ ไม่มีวันสิ้นสุด (หรือจนกระทั่งคุณปิดเครื่อง)

  • เมื่อเล็มมิ่งเข้าไปยังช่องใหม่ เขาจะยังเคลื่อนที่ไปในทิศทางเดิมจนกระทั่งไปถึงกลางช่อง เขาจะไม่ได้รับผลกระทบจากสายพานใหม่จนกระทั่งการเคลื่อนที่ในวินาทีถัดไปเริ่มขึ้น
  • ถ้าเล็มมิ่งเคลื่อนที่ตกขอบของกริด เขาจะโผล่ขึ้นที่ตำแหน่งเดียวกันที่อีกด้านของกริด ยกตัวอย่างเช่น ถ้าเขาเคลื่อนที่ไปในทิศทาง ขึ้น-ซ้าย และทะลุขอบที่กริดชองบนซ้ายสุด เขาจะปรากฏขึ้นที่ขอบล่างของช่องขวาสุด ด้วยความสามารถของวิทยาศาสตร์ เหตุการณ์เคลื่อนที่นี้ก็ยังเกิดขึ้นภายในเวลา 1 วินาทีเช่นเดียวกับการเคลื่อนที่อื่น ๆ
  • เล็มมิ่งจะไม่เดินชนกันและสามารถเดินผ่านเล็มมิ่งอื่น ๆ ได้อย่างไม่มีความลำบากใด ๆ

เป้าหมายของเราก็คือการเลือกทิศทางให้กับสายพาน เพื่อที่จะรับประกันว่าเล็มมิ่งจะเคลื่อนที่ไปตลอดกาลโดยไม่มีเล็มมิ่งสองตัวใด ๆ ที่จะไปอยู่ที่จุดกลางของช่องใด ๆ ในเวลาเดียวกัน สังเกตว่าถ้าเหตุการณ์นั้นเกิดขึ้น เล็มมิ่งทั้งสองจะเคลื่อนที่ติดกันไปตลอดและมันไม่สนุกเลยสำหรับพวกเขา

ด้านล่าง (ดูรูปจากลิงก์) เป็นวิธีสองวิธีในการกำหนดทิศทางให้กับสายพานจากตัวอย่างสายพานในรูปข้างต้น

(ดูรูปที่ลิงก์)

ในทั้งสองกรณี เราหลีกเลี่ยงการส่งเล็มมิ่งสองตัวไปยังจุดกลางของช่องใด ๆ พร้อมกันได้

ให้แผนผังของโรงงาน คำนวณ N ซึ่งเป็นจำนวนวิธีในการเลือกทิศทางให้กับสายพาน เพื่อที่จะรับประกันว่าไม่มีเล็มมิ่งสองตัวใด ๆ ที่จะเคลื่อนที่ไปที่จุดกลางของช่องใด ๆ พร้อมกัน เนื่องจากคำตอบนั้นอาจมีค่ามหาศาล ให้ตอบคำตอบ modulo 1000003