Translated by SmiLe-DoG
COCI#3 2006-2007
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
4.TENKICI | 32 MB | 1 sec
เมอร์โกและสลาฟโกเล่นเกมรถถังบนตาราง N x N ช่อง โดยรถถังแต่ละคันสามารถเคลื่อนที่ไปในช่องด้านซ้าย ขวา บน หรือล่างของตัวมันเท่านั้น พวกเขาต้องการให้ในแต่ละแถวและแต่ละคอลัมของตารางมีรถถังอยู่เพียงหนึ่งคันเท่านั้น โดยต้องการให้มีการเคลื่อนที่ของรถถังให้น้อยครั้งที่สุด
ให้เขียนโปรแกรมเพื่อหาวิธีการเคลื่อนที่ของรถถังให้ได้ตรงตามเงื่อนไขนั้น
อย่างไรก็ตามจะไม่มีรถถัง 2 คันใดๆอยู่ในช่องเดียวกัน
Input
บรรทัดแรกบรรจุจำนวนเต็ม N (5<=N<=500)
N บรรทัดถัดมา สำหรับแต่ละบรรทัดบรรจุจำวนเต็ม 2 จำนวน R และ C (1<=R,C<=N) แสดงตำแหน่งของรถถังเป็นแถวและคอลัมตามลำดับ ***ระบบพิกัดจะเริ่มจาก 1 ถึง N ในแนวบน-ล่าง ซ้าย-ขวา
Output
บรรทัดแรกแสดงจำนวนครั้งการเคลื่อนที่ที่น้อยที่สุด K
K บรรทัดถัดมา สำหรับแต่ละบรรทัดจะแสดงข้อมูลการเคลื่อนที่ของรถถังโดยประกอบด้วยหมายเลขของรถถัง (1-N เรียงตามลำดับข้อมูล Input) และทิศทางการเคลื่อนที่ ('R','L','U','D')
Sample of input
input 5 1 1 1 2 1 3 1 4 1 5 output 10 1 D 2 D 3 D 4 D 1 D 2 D 3 D 1 D 2 D 1 D | input 5 2 3 3 2 3 3 3 4 4 3 output 8 1 R 1 R 2 U 2 U 4 D 4 D 5 L 5 L | input 6 1 1 1 2 2 1 5 6 6 5 6 6 output 8 2 R 2 D 3 D 3 R 4 U 4 L 5 L 5 U |
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
5.BICIKLI | 32 MB | 1 sec
ในดินแดนอันแสนไกลโพ้น มีเมืองอยู่ทั้งหมด N เมือง ที่เชื่อมต่อกันด้วยถนนทางเดียว M เส้น จะมีการจัดการแข่งขันจักรยานประจำปีขึ้นโดยคณะกรรมการจัดการแข่งขัน ต้องการที่จะเลิอกเส้นทางที่ใช้ในการแข่งขันที่มีจุดเริ่มต้นอยู่ที่เมืองที่ 1 และมีเส้นชัยอยู่ที่เมืองที่ 2
ให้เขียนโปรแกรมเพื่อหาจำนวนวิธีการทั้งหมดที่คณะกรรมการจะสามารถเลือกเส้นทางที่ใช้ในการแข่งขันให้สอดคล้องได้ตามเงื่อนไข โดยที่เส้นทางที่เลือกจะแตกต่างกันก็ต่อเมื่อมีถนนที่เลือกอย่างน้อยหนึ่งเส้นที่แตกต่างกัน
Input
บรรทัดแรกประกอบด้วยจำนวนเต็ม N และ M (1<=N<=10000, 1<=M<=100000) เป็นจำนวนเมืองและจำนวนถนนตามลำดับ
M บรรทัดถัดมา สำหรับแต่ละบรรทัดประกอบด้วยจำนวนเต็ม A และ B แสดงให้เห็นว่ามีถนนเชื่อมจากเมือง A ไปยังเมือง B
Output
แสดงจำนวนวิธีทั้งหมดที่จะจัดเส้นทางการแข่งขันได้ หากว่ามีจำนวนเป็นอนันต์ให้แสดง "inf" ออกมา
Sample of input
input 6 7 1 3 1 4 3 2 4 2 5 6 6 5 3 4 output 3 | input 6 8 1 3 1 4 3 2 4 2 5 6 6 5 3 4 4 3 output inf | input 31 60 1 3 1 3 3 4 3 4 4 5 4 5 5 6 5 6 6 7 6 7 … … … 28 29 28 29 29 30 29 30 30 31 30 31 31 2 31 2 output 073741824 |
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
6.LISTA | 32 MB | 1 sec
เมอร์โกได้ของขวัญวันเกิดจากป้าที่อเมริกาเป็น double linked-list อันใหม่!!! โดยลิสต์นั้นประกอบด้วยโหนด N โหนด ซึ่งมีหมายเลขตั้งแต่ 1 ถึง N ในลิสต์นั้นเมอร์โกสามารถย้ายโหนดได้ 2 แบบคือ
A) ย้ายโหนดหมายเลข X ไปไว้หน้าโหนดหมายเลข Y
B) ย้ายโหนดหมายเลข X ไปไว้หลังโหนดหมายเลข Y
ดังรูป
เมอร์โกเล่นของเล่นนั้นอยู่หลายชั่วโมง เขาได้จดไว้ว่าเขาเคลื่อนที่ในรูปแบบใดไปบ้าง เพื่อที่ว่าเขาจะได้สามารถทำให้ลิสต์นั้นย้อนกลับมาอยู่ในสภาพเริ่มต้นได้ (โหนดเรียงตั้งแต่ 1 ถึง N จากซ้่ายไปขวา)
แต่แล้วเมื่อเมอร์โกตัดสินใจที่จะทำให้ลิสต์กลับคืนไปสู่สภาพเริ่มต้นนั้น เขาก็ค้นพบเรื่องน่าประหลาดใจว่าเขาไม่สามารถทำย้อนกลับการเคลื่อนที่ที่เขาจดไว้ได้ เพราะเขาไม่รู้จุดเริ่มต้นที่โหนดย้ายมา เขารู้เพียงตำแหน่งของโหนดหลังจากการย้ายแล้วเท่านั้น
ระหว่างที่เมอร์โกกำลังช็อคอยู่นั้น!! ให้เขียนโปรแกรมเพื่อหาลำดับการย้ายที่สั้นที่สุดที่จะทำให้ลิสต์กลับไปอยู่ในสภาพเริ่มต้นได้
Input
บรรทัดแรกประกอบด้วยจำนวนเต็มสองจำนวน N และ K (2<=N<=500000, 0<=M<=100000) เป็นจำนวนของโหนดและจำนวนครั้งการย้ายของเมอร์โก M แถวถัดมา สำหรับแต่ละแถวประกอบด้วยข้อมูลการ คือประกอบด้วยตัวอักขระ 'A' หรือ 'B' และจำนวนเต็ม X และ Y
Output
บรรทัดแรกประกอบด้วยจำนวนเต็ม K เป็นจำนวนครั้งการย้ายที่น้อยที่สุึด
K บรรทัดถัดมา สำหรับแต่ละแถวประกอบด้วยข้อมูลการย้ายหนึ่งครั้ง โดยมีรูปแบบเหมือนข้อมูลนำเข้า
อนึ่งข้อมูล Output อาจจะไม่ได้มีเพียงรูปแบบเดียว ให้แสดงผลรูปแบบใดก็ได้
Sample of input
input 2 1 A 2 1 output 1 A 1 2 | input 4 3 B 1 2 A 4 3 B 1 4 output 2 A 1 2 B 4 3 | input 6 5 A 1 4 B 2 5 B 4 2 B 6 3 A 3 5 output 3 A 4 5 B 6 5 |
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
