ผลต่างระหว่างรุ่นของ "โจทย์เขียนโปรแกรม: beads2"
Cardcaptor (คุย | มีส่วนร่วม) |
Cardcaptor (คุย | มีส่วนร่วม) |
||
| แถว 8: | แถว 8: | ||
<center>[[Image:Swapper.JPG]]</center> | <center>[[Image:Swapper.JPG]]</center> | ||
| + | |||
| + | สิ่งที่เครื่อง ค.ล.ต. มีความสามารถเหนือเครื่อง UBS คือ โปรเฟสเซอร์ X สามารถเลือกปิดหรือเปิดเครื่องสลับรางพร้อมกันเป็นแถบๆ ได้ กล่าวคือเขาสามารถกำหนดเครื่องสลับราง M<sub>1</sub> และ M<sub>2</sub> โดยที่ M<sub>1</sub> <= M<sub>2</sub> แล้วสั่งให้เครื่อง ค.ล.ต. ปิดหรือเปิดเครื่องสลับรางใดๆ ที่มีหมายเลขอยู่ตั้งแต่ M<sub>1</sub> ถึง M<sub>2</sub> (ถ้าเครื่องสลับรางใดถูกปิดอยู่แล้วถูกปิด มันก็จะยังถูกปิดอยู่ต่อไป ในทำนองเดียวกัน ถ้าเครื่องสลับรางที่เปิดถูกเปิด มันก็ยังจะเปิดต่อไปอยู่อย่างนั้น) โดยเมื่อแถวของลูกแก้วสลับรางเคลื่อนที่ผ่านเครื่องสลับรางที่ถูกปิดไป ลูกแก้วที่เคลื่อนที่ผ่านเครื่องสลับรางที่ดับอยู่จะไม่ถูกสลับที่ | ||
| + | |||
| + | == งานของคุณ == | ||
| + | จงเขียนโปรแกรมเพื่อรับและประมวลคำสั่งต่อไปนี้ | ||
| + | * เปิดเครื่องสลับรางตั้งแต่หมายเลข M<sub>1</sub> ถึง M<sub>2</sub> | ||
| + | * ปิดเครื่องสลับรางตั้งแต่หมายเลข M<sub>1</sub> ถึง M<sub>2</sub> | ||
| + | * ตอบคำถามที่ว่า "เมื่อกำหนด J และ K ให้ ลูกแก้วที่ถูกปอนเข้าสู่รางหมายเลข K ด้านเหนือของเครื่อง ค.ล.ต จะถูก สลับไปอยู่ที่รางหมายเลขใดหลังจากวิ่งผ่านตัวสลับรางหมายเลข J" | ||
| + | |||
| + | กำหนดว่าตอนเริ่มต้น เครื่องสลับรางทุกเรื่องถูกปิดอยู่ | ||
| + | |||
| + | เรารับประกันว่า ณ เวลาใดๆ จะไม่มีช่วงของเครื่องสลับรางถูกเปิดอยู่พร้อมกันมากกว่าสิบช่วง | ||
| + | |||
| + | == ข้อมูลเข้า == | ||
| + | บรรทัดแรกระบุจำนวนราง N (1 <= N <= 100,000) และจำนวนตัวสลับราง M (1 <= M <= 100,000) | ||
| + | |||
| + | อีก M บรรทัดถัดไประบุตำแหน่งของตัวสลับราง เรียงตามลำดับจากเหนือไปใต้ โดยแต่ละบรรทัดมีจำนวนเต็ม P (1 <= P <= N-1) ซึ่งหมายความว่าตัวสลับรางคร่อมระหว่างรางที่ P และ P+1 | ||
| + | |||
| + | บรรทัดต่อไปมีจำนวนเต็ม C (1 <= C <= 200,000) แสดงจำนวนคำสั่งสามแบบทั้งหมด | ||
| + | |||
| + | อีก C บรรทัดต่อไปมีแต่ละบรรทัดมีรูปแบบดังต่อไปนี้ | ||
| + | * "1 M<sub>1</sub> M<sub>2</sub>" โดยที่ 1 <= M<sub>1</sub> <= M<sub>2</sub> <= M หมายความว่าให้เปิดเครื่องสลับรางตั้งแต่หมายเลข M<sub>1</sub> ถึง M<sub>2</sub> | ||
รุ่นแก้ไขเมื่อ 07:50, 7 มิถุนายน 2551
หลังจากที่โปรเฟสเซอร์ X ได้เผยโฉม "เครื่องสลับลูกแก้วสะท้านโลกันต์" (UBS) ให้ประจักษ์แก้ชาวโลก เขาก็ได้พัฒนามันให้มีประสิทธิภาพและใช้่งานง่ายยิ่งขึ้น จนสามารถออกรุ่นที่สอง "เครื่องสลับลูกแก้วสะท้านโลกันตร์ตะรื้ดวิญญาณ" (ค.ล.ต.) มาให้ชาวโลกได้ยลโฉมได้
เครื่อง ค.ล.ต. ประกอบด้วยราง N รางและตัวสลับราว M ตัวเช่นเดียวกับเครื่อง UBS โปรเฟสเซอร์ X ให้หมายเลขรางจากซ้่ายไปขวาด้วยหมายเลข 1 ถึง N และให้หมายเลขเครื่องสลับรางจาก 1 ถึง M จากเหนือลงใต้ (ไม่มีเครื่องสลับรางใดๆ อยู่ระดับเดียวกันในแนวเหนือใต้) รางทุกรางจะเคลื่อนที่ไปด้วยความเร็วเท่ากันเช่นเดียวกับเครื่อง UBS เมื่อมองเครื่อง ค.ล.ต. จากด้านบนจะเหมือนกับเครื่อง UBS ทุกประการ ดังภาพ
เครื่อง ค.ล.ต. มีวิธีการใช้งานแบบเดียวกันกับเครื่อง UBS กล่าวคือผู้ใช้จะนำลูกแก้ว N ลูกไปวางไว้บนปลายด้านเหนือสุดของรางแต่ละราง รางละหนึ่งลูก เพื่อให้เวลาลูกแก้วเคลื่อนที่ไปบนรางมันจะเรียงกันแบนแถวหน้ากระดาน ลูกแก้วสองลูกที่เคลื่อนที่ไปอยู่ใต้เครื่องสลับรางจะุถูกสลับที่กันโดยไม่ทำให้แถวหน้ากระดานแตก ดังภาพ
สิ่งที่เครื่อง ค.ล.ต. มีความสามารถเหนือเครื่อง UBS คือ โปรเฟสเซอร์ X สามารถเลือกปิดหรือเปิดเครื่องสลับรางพร้อมกันเป็นแถบๆ ได้ กล่าวคือเขาสามารถกำหนดเครื่องสลับราง M1 และ M2 โดยที่ M1 <= M2 แล้วสั่งให้เครื่อง ค.ล.ต. ปิดหรือเปิดเครื่องสลับรางใดๆ ที่มีหมายเลขอยู่ตั้งแต่ M1 ถึง M2 (ถ้าเครื่องสลับรางใดถูกปิดอยู่แล้วถูกปิด มันก็จะยังถูกปิดอยู่ต่อไป ในทำนองเดียวกัน ถ้าเครื่องสลับรางที่เปิดถูกเปิด มันก็ยังจะเปิดต่อไปอยู่อย่างนั้น) โดยเมื่อแถวของลูกแก้วสลับรางเคลื่อนที่ผ่านเครื่องสลับรางที่ถูกปิดไป ลูกแก้วที่เคลื่อนที่ผ่านเครื่องสลับรางที่ดับอยู่จะไม่ถูกสลับที่
งานของคุณ
จงเขียนโปรแกรมเพื่อรับและประมวลคำสั่งต่อไปนี้
- เปิดเครื่องสลับรางตั้งแต่หมายเลข M1 ถึง M2
- ปิดเครื่องสลับรางตั้งแต่หมายเลข M1 ถึง M2
- ตอบคำถามที่ว่า "เมื่อกำหนด J และ K ให้ ลูกแก้วที่ถูกปอนเข้าสู่รางหมายเลข K ด้านเหนือของเครื่อง ค.ล.ต จะถูก สลับไปอยู่ที่รางหมายเลขใดหลังจากวิ่งผ่านตัวสลับรางหมายเลข J"
กำหนดว่าตอนเริ่มต้น เครื่องสลับรางทุกเรื่องถูกปิดอยู่
เรารับประกันว่า ณ เวลาใดๆ จะไม่มีช่วงของเครื่องสลับรางถูกเปิดอยู่พร้อมกันมากกว่าสิบช่วง
ข้อมูลเข้า
บรรทัดแรกระบุจำนวนราง N (1 <= N <= 100,000) และจำนวนตัวสลับราง M (1 <= M <= 100,000)
อีก M บรรทัดถัดไประบุตำแหน่งของตัวสลับราง เรียงตามลำดับจากเหนือไปใต้ โดยแต่ละบรรทัดมีจำนวนเต็ม P (1 <= P <= N-1) ซึ่งหมายความว่าตัวสลับรางคร่อมระหว่างรางที่ P และ P+1
บรรทัดต่อไปมีจำนวนเต็ม C (1 <= C <= 200,000) แสดงจำนวนคำสั่งสามแบบทั้งหมด
อีก C บรรทัดต่อไปมีแต่ละบรรทัดมีรูปแบบดังต่อไปนี้
- "1 M1 M2" โดยที่ 1 <= M1 <= M2 <= M หมายความว่าให้เปิดเครื่องสลับรางตั้งแต่หมายเลข M1 ถึง M2
