ผลต่างระหว่างรุ่นของ "Gcj2011"
Jittat (คุย | มีส่วนร่วม) (หน้าที่ถูกสร้างด้วย '== Round 3 == === C. Perpetual Motion === Source: [https://code.google.com/codejam/contest/1158485/dashboard#s=p2&a=2] คุณเ...') |
Jittat (คุย | มีส่วนร่วม) |
||
| แถว 5: | แถว 5: | ||
Source: [https://code.google.com/codejam/contest/1158485/dashboard#s=p2&a=2] | Source: [https://code.google.com/codejam/contest/1158485/dashboard#s=p2&a=2] | ||
| − | คุณเคยไปโรงงานเล็มมิ่งของกูเกิ้ลไหม? มันเป็นสถานที่ที่แปลกมาก พื้นของโรงงานจะถูกแบ่งเป็นตารางกริดขนาด R x C ในแต่ละช่องกริด จะมีสายพานที่อาจจะมีทิศทางขึ้นลง ซ้ายขวา หรือในทิศทแยงทั้งสองแบบ สายพานนี้หมุนได้สองแบบในทิศทางที่มันติดตั้งไว้ และนอกจากนี้ คุณยังสามารถเลือกทิศการหมุนของแต่ละสายพานแต่ละเส้นได้อย่างเป็นอิสระต่อกัน | + | คุณเคยไปโรงงานเล็มมิ่งของกูเกิ้ลไหม? มันเป็นสถานที่ที่แปลกมาก พื้นของโรงงานจะถูกแบ่งเป็นตารางกริดขนาด '''R x C''' ในแต่ละช่องกริด จะมีสายพานที่อาจจะมีทิศทางขึ้นลง ซ้ายขวา หรือในทิศทแยงทั้งสองแบบ สายพานนี้หมุนได้สองแบบในทิศทางที่มันติดตั้งไว้ และนอกจากนี้ คุณยังสามารถเลือกทิศการหมุนของแต่ละสายพานแต่ละเส้นได้อย่างเป็นอิสระต่อกัน |
(ดูรูปประกอบจากลิงก์ด้านบน) | (ดูรูปประกอบจากลิงก์ด้านบน) | ||
เมื่อเริ่มต้น มีเล็มมิ่งอยู่ที่ตรงกลางของทุก ๆ ช่องกริด เมื่อคุณเริ่มให้สายพานทำงาน เล็มมิ่งแต่ละตัวจะเคลื่อนที่ไปในทิศทางของสายพานจนไปอยู่ที่กลางช่องใหม่ในทิศที่สายพานเคลื่อนที่ การเคลื่อนที่นี้เกิดขึ้นพร้อม ๆ กัน และใช้เวลาหนึ่งวินาทีพอดี หลังจากนั้นเล็มมิ่งทุกตัวจะอยู่ที่กลางช่องใหม่ และกระบวนการเคลื่อนที่ก็จะเริ่มอีกครั้งไปเรื่อย ๆ ไม่มีวันสิ้นสุด (หรือจนกระทั่งคุณปิดเครื่อง) | เมื่อเริ่มต้น มีเล็มมิ่งอยู่ที่ตรงกลางของทุก ๆ ช่องกริด เมื่อคุณเริ่มให้สายพานทำงาน เล็มมิ่งแต่ละตัวจะเคลื่อนที่ไปในทิศทางของสายพานจนไปอยู่ที่กลางช่องใหม่ในทิศที่สายพานเคลื่อนที่ การเคลื่อนที่นี้เกิดขึ้นพร้อม ๆ กัน และใช้เวลาหนึ่งวินาทีพอดี หลังจากนั้นเล็มมิ่งทุกตัวจะอยู่ที่กลางช่องใหม่ และกระบวนการเคลื่อนที่ก็จะเริ่มอีกครั้งไปเรื่อย ๆ ไม่มีวันสิ้นสุด (หรือจนกระทั่งคุณปิดเครื่อง) | ||
| + | |||
| + | * เมื่อเล็มมิ่งเข้าไปยังช่องใหม่ เขาจะยังเคลื่อนที่ไปในทิศทางเดิมจนกระทั่งไปถึงกลางช่อง เขาจะไม่ได้รับผลกระทบจากสายพานใหม่จนกระทั่งการเคลื่อนที่ในวินาทีถัดไปเริ่มขึ้น | ||
| + | |||
| + | * ถ้าเล็มมิ่งเคลื่อนที่ตกขอบของกริด เขาจะโผล่ขึ้นที่ตำแหน่งเดียวกันที่อีกด้านของกริด ยกตัวอย่างเช่น ถ้าเขาเคลื่อนที่ไปในทิศทาง ขึ้น-ซ้าย และทะลุขอบที่กริดชองบนซ้ายสุด เขาจะปรากฏขึ้นที่ขอบล่างของช่องขวาสุด ด้วยความสามารถของวิทยาศาสตร์ เหตุการณ์เคลื่อนที่นี้ก็ยังเกิดขึ้นภายในเวลา 1 วินาทีเช่นเดียวกับการเคลื่อนที่อื่น ๆ | ||
| + | |||
| + | * เล็มมิ่งจะไม่เดินชนกันและสามารถเดินผ่านเล็มมิ่งอื่น ๆ ได้อย่างไม่มีความลำบากใด ๆ | ||
| + | |||
| + | เป้าหมายของเราก็คือการเลือกทิศทางให้กับสายพาน เพื่อที่จะรับประกันว่าเล็มมิ่งจะเคลื่อนที่ไปตลอดกาลโดยไม่มีเล็มมิ่งสองตัวใด ๆ ที่จะไปอยู่ที่จุดกลางของช่องใด ๆ ในเวลาเดียวกัน สังเกตว่าถ้าเหตุการณ์นั้นเกิดขึ้น เล็มมิ่งทั้งสองจะเคลื่อนที่ติดกันไปตลอดและมันไม่สนุกเลยสำหรับพวกเขา | ||
| + | |||
| + | ด้านล่าง (ดูรูปจากลิงก์) เป็นวิธีสองวิธีในการกำหนดทิศทางให้กับสายพานจากตัวอย่างสายพานในรูปข้างต้น | ||
| + | |||
| + | (ดูรูปที่ลิงก์) | ||
| + | |||
| + | ในทั้งสองกรณี เราหลีกเลี่ยงการส่งเล็มมิ่งสองตัวไปยังจุดกลางของช่องใด ๆ พร้อมกันได้ | ||
| + | |||
| + | ให้แผนผังของโรงงาน คำนวณ '''N''' ซึ่งเป็นจำนวนวิธีในการเลือกทิศทางให้กับสายพาน เพื่อที่จะรับประกันว่าไม่มีเล็มมิ่งสองตัวใด ๆ ที่จะเคลื่อนที่ไปที่จุดกลางของช่องใด ๆ พร้อมกัน เนื่องจากคำตอบนั้นอาจมีค่ามหาศาล ให้ตอบคำตอบ modulo 1000003 | ||
รุ่นแก้ไขปัจจุบันเมื่อ 01:31, 17 พฤษภาคม 2556
Round 3
C. Perpetual Motion
Source: [1]
คุณเคยไปโรงงานเล็มมิ่งของกูเกิ้ลไหม? มันเป็นสถานที่ที่แปลกมาก พื้นของโรงงานจะถูกแบ่งเป็นตารางกริดขนาด R x C ในแต่ละช่องกริด จะมีสายพานที่อาจจะมีทิศทางขึ้นลง ซ้ายขวา หรือในทิศทแยงทั้งสองแบบ สายพานนี้หมุนได้สองแบบในทิศทางที่มันติดตั้งไว้ และนอกจากนี้ คุณยังสามารถเลือกทิศการหมุนของแต่ละสายพานแต่ละเส้นได้อย่างเป็นอิสระต่อกัน
(ดูรูปประกอบจากลิงก์ด้านบน)
เมื่อเริ่มต้น มีเล็มมิ่งอยู่ที่ตรงกลางของทุก ๆ ช่องกริด เมื่อคุณเริ่มให้สายพานทำงาน เล็มมิ่งแต่ละตัวจะเคลื่อนที่ไปในทิศทางของสายพานจนไปอยู่ที่กลางช่องใหม่ในทิศที่สายพานเคลื่อนที่ การเคลื่อนที่นี้เกิดขึ้นพร้อม ๆ กัน และใช้เวลาหนึ่งวินาทีพอดี หลังจากนั้นเล็มมิ่งทุกตัวจะอยู่ที่กลางช่องใหม่ และกระบวนการเคลื่อนที่ก็จะเริ่มอีกครั้งไปเรื่อย ๆ ไม่มีวันสิ้นสุด (หรือจนกระทั่งคุณปิดเครื่อง)
- เมื่อเล็มมิ่งเข้าไปยังช่องใหม่ เขาจะยังเคลื่อนที่ไปในทิศทางเดิมจนกระทั่งไปถึงกลางช่อง เขาจะไม่ได้รับผลกระทบจากสายพานใหม่จนกระทั่งการเคลื่อนที่ในวินาทีถัดไปเริ่มขึ้น
- ถ้าเล็มมิ่งเคลื่อนที่ตกขอบของกริด เขาจะโผล่ขึ้นที่ตำแหน่งเดียวกันที่อีกด้านของกริด ยกตัวอย่างเช่น ถ้าเขาเคลื่อนที่ไปในทิศทาง ขึ้น-ซ้าย และทะลุขอบที่กริดชองบนซ้ายสุด เขาจะปรากฏขึ้นที่ขอบล่างของช่องขวาสุด ด้วยความสามารถของวิทยาศาสตร์ เหตุการณ์เคลื่อนที่นี้ก็ยังเกิดขึ้นภายในเวลา 1 วินาทีเช่นเดียวกับการเคลื่อนที่อื่น ๆ
- เล็มมิ่งจะไม่เดินชนกันและสามารถเดินผ่านเล็มมิ่งอื่น ๆ ได้อย่างไม่มีความลำบากใด ๆ
เป้าหมายของเราก็คือการเลือกทิศทางให้กับสายพาน เพื่อที่จะรับประกันว่าเล็มมิ่งจะเคลื่อนที่ไปตลอดกาลโดยไม่มีเล็มมิ่งสองตัวใด ๆ ที่จะไปอยู่ที่จุดกลางของช่องใด ๆ ในเวลาเดียวกัน สังเกตว่าถ้าเหตุการณ์นั้นเกิดขึ้น เล็มมิ่งทั้งสองจะเคลื่อนที่ติดกันไปตลอดและมันไม่สนุกเลยสำหรับพวกเขา
ด้านล่าง (ดูรูปจากลิงก์) เป็นวิธีสองวิธีในการกำหนดทิศทางให้กับสายพานจากตัวอย่างสายพานในรูปข้างต้น
(ดูรูปที่ลิงก์)
ในทั้งสองกรณี เราหลีกเลี่ยงการส่งเล็มมิ่งสองตัวไปยังจุดกลางของช่องใด ๆ พร้อมกันได้
ให้แผนผังของโรงงาน คำนวณ N ซึ่งเป็นจำนวนวิธีในการเลือกทิศทางให้กับสายพาน เพื่อที่จะรับประกันว่าไม่มีเล็มมิ่งสองตัวใด ๆ ที่จะเคลื่อนที่ไปที่จุดกลางของช่องใด ๆ พร้อมกัน เนื่องจากคำตอบนั้นอาจมีค่ามหาศาล ให้ตอบคำตอบ modulo 1000003
