นักล่าสมบัติ (toi10_raider)


Time limit:
1000 ms
Memory limit:
512 MB

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

ดร.เค ได้รับมอบหมายให้เดินทางไปยังถ้ำสมบัติ TOI (Tomb of Informatics) ตามที่ระบุไว้ในแผนที่ลายแทง เมื่อ ดร.เค เดินทางไปถึงถ้ำสมบัติ เขาก็ต้องฉงนงงงวย!!? เมื่อพบว่าวิธีการที่จะไปยังหีบสมบัติซึ่งวางอยู่ด้านในสุดของถ้ำ จะต้องเดินผ่านพื้นกลที่ชนเผ่าต๋อยในอดีตวางไว้เพื่อไม่ให้นำหีบสมบัติออกจากถ้ำไปโดยง่าย ื้นกลประกอบด้วยแผ่นหินกลรูปหกเหลี่ยมด้านเท่ามุมเท่า ขนาดเท่ากันทุกแผ่น แผ่นหินกลดังกล่าวถูกปูติดกันพอดี เป็นจำนวน m แถว และในแต่ละแถวจะมีแผ่นหินกล n แผ่น ซึ่งจัดเรียงแผ่นหินกลจากแผ่นที่ 0 ไปยังแผ่นที่ n-1 ในแนว้ําไปยังหีบสมบัต และมีการเรียงแถวจากแถวที่ 0 ถึงแถวที่ m-1 จากด้านซ้ายมือไปยังด้านขวามือ อย่างมีเงื่อนไข คือ แผ่นหินกลแผ่นที่ 0 ของแถวที่มีลําดับซึ่งเป็นเลขคู่จะอยู่จากแนวปากถ้ำกว่าแผ่นหินกลแผ่นที่ 0 ของแถวเลขคี่เสมอ และดร.เค พบอีกว่าปากถ้ำและหีบสมบัติอยู่ในแนวเดียวกันกับแผ่นหินกล แถวที่ (m-1)/2 ดังตัวอย่างในรูปที่ 1

รูปที่ 1 ตัวอย่างแสดงพื้นกล ตำแหน่งของปากถ้ำ และหีบสมบัติ เมื่อ m = 5 และ n = 4

ดร.เค ต้องการไปยังหีบสมบัติดังกล่าวซึ่งจำเป็นต้องก้าวผ่านพื้นกล โดยมีเงื่อนไขต่อไปนี้

  • ต้องเริ่มก้าวจากแผ่นหินกลแผ่นที่ 0 ของแถวที่ (m-1)/2 - 1, (m-1)/2 หรือ (m-1)/2 + 1 เท่านั้น
  • การก้าวลงบนแผ่นหินกลต้องเหยียบลงบนแผ่นหินกลทีละแผ่นเท่านั้น
  • การก้าวจากแผ่นหินกลแผ่นหนึ่งไปยังอีกแผ่นหนึ่ง ต้องก้าวไปยังแผ่นหินกลที่อยู่ติดกันเท่านั้น โดยไม่อนุญาตให้ย่ำอยู่ที่เดิม
  • แผ่นหินกลแต่ละแผ่น สามารถถูก ดร.เค ก้าวกลับมาเหยียบได้มากกว่า 1 ครั้ง
  • แผ่นหินกลแต่ละแผ่นมีัยซึ่งเป็นจํานวนเต็มตั้งแต่ 0 ถึง 9 โดยไม่อนุญาตให้ก้าวลงบนแผ่นหินกลที่มีหมายเลขปลอดภัยเป็น 0 หรือ เมื่อ ดร.เค ก้าวลงแผ่นหินกลนั้นในการก้าวครั้งที่ yth แล้วหมายเลขปลอดภัย x บนแผ่นหินกล หาร y ไม่ลงตัว (y ถูกหารด้วย x ไม่ลงตัว)
  • ดร.เค จะสามารถนำหีบสมบัติกลับออกมาจากถ้ำได้ถ้า ก้าวไปถึงแผ่นหินกลที่ n-1 ของแถวที่ (m-1)/2

รูปที่ 2 แสดงตัวอย่าง ลำดับการก้าวไปยังหีบสมบัติของ ดร.เค กรณี m = 5 และ n = 4 ดร.เค สามารถ เลือกเดินก้าวแรกเหยียบบนแผ่นหินกลแผ่นที่ 0 แถวที่ 2 หรือ แถวที่ 3 เท่านั้น เนื่องจากแผ่นที่ 0 ของแถวที่ 1 มีหมายเลขปลอดภัยเป็น 0 และ ดร.เค จะสามารถไปยังหีบสมบัติได้เมื่อก้าวเดินไปถึงแผ่นหินกลที่ 3 ของแถวที่ 2

รูปที่ 2 ตัวอย่างการก้าวเดินไปยังหีบสมบัติสองวิธีที่แตกต่างกันตามเงื่อนไขที่กําหนด

จากตัวอย่างรูป 2(ก) ดร.เค เริ่มก้าวแรกที่แผ่นหินกลที่ 0 แถวที่ 3 ซึ่งสามารถเดินี่ 2 ต่อไปได้เพียงแผ่นหินกลที่ 0 แถวที่ 2 หรือ แผ่นหินกลที่ 0 แถวที่ 4 เท่านั้น ไม่สามารถก้าวไปยังแผ่นหินกลที่ 1 แถวที่ 3 เนื่องจาก หมายเลขปลอดภัยของแผ่นหินกลดังกล่าวคือ 3 และ จำนวน 2 ไม่สามารถถูกหารด้วย 3 ลงตัว

จากรูปที่ 2 เห็นได้ว่า ถ้า ดร.เค ก้าวเดินตามการก้าวเดินดังรูป 2(ก) จะมีจำนวนก้าวเดินทั้งหมด 7 ก้าว ขณะที่ รูป 2(ข) แสดงอีกวิธีการก้าวเดินไปยังหีบสมบัติอีกหนึ่งวิธี ซึ่งมีจำนวนก้าวเดินทั้งหมดถึง 21 ก้าว

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

Input

บรรทัดแรก มีหนึ่งจํานวน คือ จำนวนเต็ม m แสดงจํานวนแถวของแผ่นหินกล เมื่อ 5 ≤ m ≤ 97 และ m หารด้วย 4 แล้วเหลือเศษ 1 เสมอ

บรรทัดที่ 2 มีหนึ่งจํานวน คือ จำนวนเต็ม n แสดงจํานวนแผ่นหินกลในแต่ละแถว เมื่อ 4 ≤ n ≤ 100

บรรทัดที่ 3 ถึง m + 2 แต่ละบรรทัดมีจํานวนเต็ม n จํานวน แสดงหมายเลขปลอดภัยของแผ่นหินกลแผ่นที่ 0 ถึงแผ่นที่ n-1 ในแต่ละแถว หมายเลขปลอดภัยแต่ละจำนวนถูกคั่นด้วยช่องว่างหนึ่งช่อง เรียงจากแถวที่ 0 ไปจนถึงแถวที่ m – 1

Output

มีเพียงบรรทัดเดียว แสดงจํานวนเต็มบวกหนึ่งจํานวน แทนจํานวนก้าวที่น้อยที่สุดที่เป็นไปได้ในเดินจาก ปากถ้ำผ่านพื้นกลไปยังหีบสมบัติ

Constrains/Subtasks

อย่างน้อยร้อยละ 30 ค่าหมายเลขปลอดภัยมีค่าเป็น 0 หรือ 1 เท่านั้น และทุกข้อมูลทดสอบมีคำตอบไม่เกิน 5000

Editor:

Source: Thailand Olympiad in Informatics 2014 (TOI10 / TOI 2014)

Select description language

Thai (raw)

If you don't find what you want

Translate it!

Edit this description

Edit

Tag

None