ผลต่างระหว่างรุ่นของ "โจทย์เขียนโปรแกรม: beads2"

จาก Theory Wiki
ไปยังการนำทาง ไปยังการค้นหา
(typo)
 
(ไม่แสดง 13 รุ่นระหว่างกลางโดยผู้ใช้ 4 คน)
แถว 1: แถว 1:
 +
__NOTOC__
 
หลังจากที่โปรเฟสเซอร์ X ได้เผยโฉม "เครื่องสลับลูกแก้วสะท้านโลกันต์" (UBS) ให้ประจักษ์แก้ชาวโลก เขาก็ได้พัฒนามันให้มีประสิทธิภาพและใช้่งานง่ายยิ่งขึ้น จนสามารถออกรุ่นที่สอง "เครื่องสลับลูกแก้วสะท้านโลกันตร์ตะรื้ดวิญญาณ" (ค.ล.ต.) มาให้ชาวโลกได้ยลโฉมได้
 
หลังจากที่โปรเฟสเซอร์ X ได้เผยโฉม "เครื่องสลับลูกแก้วสะท้านโลกันต์" (UBS) ให้ประจักษ์แก้ชาวโลก เขาก็ได้พัฒนามันให้มีประสิทธิภาพและใช้่งานง่ายยิ่งขึ้น จนสามารถออกรุ่นที่สอง "เครื่องสลับลูกแก้วสะท้านโลกันตร์ตะรื้ดวิญญาณ" (ค.ล.ต.) มาให้ชาวโลกได้ยลโฉมได้
  
เครื่อง ค.ล.ต. ประกอบด้วยราง N รางและตัวสลับราว M ตัวเช่นเดียวกับเครื่อง UBS โปรเฟสเซอร์ X ให้หมายเลขรางจากซ้่ายไปขวาด้วยหมายเลข 1 ถึง N และให้หมายเลขเครื่องสลับรางจาก 1 ถึง M จากเหนือลงใต้ (ไม่มีเครื่องสลับรางใดๆ อยู่ระดับเดียวกันในแนวเหนือใต้) รางทุกรางจะเคลื่อนที่ไปด้วยความเร็วเท่ากันเช่นเดียวกับเครื่อง UBS เมื่อมองเครื่อง ค.ล.ต. จากด้านบนจะเหมือนกับเครื่อง UBS ทุกประการ ดังภาพ
+
เครื่อง ค.ล.ต. ประกอบด้วยราง N รางและตัวสลับราว M ตัวเช่นเดียวกับเครื่อง UBS โปรเฟสเซอร์ X ให้หมายเลขรางจากซ้ายไปขวาด้วยหมายเลข 1 ถึง N และให้หมายเลขเครื่องสลับรางจาก 1 ถึง M จากเหนือลงใต้ (ไม่มีเครื่องสลับรางใดๆ อยู่ระดับเดียวกันในแนวเหนือใต้) รางทุกรางจะเคลื่อนที่ไปด้วยความเร็วเท่ากันเช่นเดียวกับเครื่อง UBS เมื่อมองเครื่อง ค.ล.ต. จากด้านบนจะเหมือนกับเครื่อง UBS ทุกประการ ดังภาพ
  
[[Image:Ubs.JPG|300px]]
+
<center>[[Image:Ubs.JPG|400px]]</center>
 +
 
 +
เครื่อง ค.ล.ต. มีวิธีการใช้งานแบบเดียวกันกับเครื่อง UBS กล่าวคือผู้ใช้จะนำลูกแก้ว N ลูกไปวางไว้บนปลายด้านเหนือสุดของรางแต่ละราง รางละหนึ่งลูก เพื่อให้เวลาลูกแก้วเคลื่อนที่ไปบนรางมันจะเรียงกันแบนแถวหน้ากระดาน ลูกแก้วสองลูกที่เคลื่อนที่ไปอยู่ใต้เครื่องสลับรางจะุถูกสลับที่กันโดยไม่ทำให้แถวหน้ากระดานแตก ดังภาพ
 +
 
 +
<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 ให้ ลูกแก้วที่ถูกป‡อนเข้าสู่รางหมายเลข 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>
 +
* "2 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>
 +
* "3 J" โดยที่ 1 <= J <= N หมายความว่าให้ตอบคำถาม "ลูกแก้วที่ถูกป‡อนเข้าสู่รางหมายเลข J ด้านเหนือของเครื่อง ค.ล.ต จะถูก สลับไปอยู่ที่รางหมายเลขใดหลังจากแถวของลูกแก้วผ่านเครื่องสลับรางทั้งหมดไปแล้ว"
 +
 
 +
== ข้อมูลออก ==
 +
มี Q บรรทัด โดยที่ Q เป็นจำนวนบรรทัดที่มีรูปแบบรูปแบบ "3 J" ในข้อมูลเข้า ในแต่ละบรรทัดให้พิมพ์จำนวนเต็ม K (1 <= K <= 100,000) ซึ่งเป็นคำตอบของคำถามที่ตรงกับบรรทัดรูปแบบ "3 J" ในข้อมูลเข้า เรียงจากคำถามแรกไปยังคำถามสุดท้าย ตามลำดับที่พบในข้อมูลเข้า
 +
 
 +
== ตัวอย่าง ==
 +
{| border="0" cellpadding="10" align="left" width="100%"
 +
|-
 +
|
 +
'''ข้อมูลเข้า 1'''<br>
 +
<pre>
 +
5 5
 +
2
 +
4
 +
1
 +
3
 +
3
 +
10
 +
3 1
 +
3 5
 +
1 2 4
 +
3 1
 +
3 5
 +
2 3 3
 +
3 3
 +
1 1 5
 +
3 1
 +
3 3
 +
</pre>
 +
'''ข้อมูลออก 1'''<br>
 +
<pre>
 +
1
 +
5
 +
2
 +
3
 +
3
 +
2
 +
1
 +
</pre>
 +
|}
 +
== ข้อกำหนด ==
 +
โปรแกรมของคุณต้องทำงานเสร็จสิ้นในเวลา 2 วินาที และใช้หน่วยความจำไม่เกิน 256 MB

รุ่นแก้ไขปัจจุบันเมื่อ 07:49, 8 มิถุนายน 2551

หลังจากที่โปรเฟสเซอร์ X ได้เผยโฉม "เครื่องสลับลูกแก้วสะท้านโลกันต์" (UBS) ให้ประจักษ์แก้ชาวโลก เขาก็ได้พัฒนามันให้มีประสิทธิภาพและใช้่งานง่ายยิ่งขึ้น จนสามารถออกรุ่นที่สอง "เครื่องสลับลูกแก้วสะท้านโลกันตร์ตะรื้ดวิญญาณ" (ค.ล.ต.) มาให้ชาวโลกได้ยลโฉมได้

เครื่อง ค.ล.ต. ประกอบด้วยราง N รางและตัวสลับราว M ตัวเช่นเดียวกับเครื่อง UBS โปรเฟสเซอร์ X ให้หมายเลขรางจากซ้ายไปขวาด้วยหมายเลข 1 ถึง N และให้หมายเลขเครื่องสลับรางจาก 1 ถึง M จากเหนือลงใต้ (ไม่มีเครื่องสลับรางใดๆ อยู่ระดับเดียวกันในแนวเหนือใต้) รางทุกรางจะเคลื่อนที่ไปด้วยความเร็วเท่ากันเช่นเดียวกับเครื่อง UBS เมื่อมองเครื่อง ค.ล.ต. จากด้านบนจะเหมือนกับเครื่อง UBS ทุกประการ ดังภาพ

Ubs.JPG

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

Swapper.JPG

สิ่งที่เครื่อง ค.ล.ต. มีความสามารถเหนือเครื่อง UBS คือ โปรเฟสเซอร์ X สามารถเลือกปิดหรือเปิดเครื่องสลับรางพร้อมกันเป็นแถบๆ ได้ กล่าวคือเขาสามารถกำหนดเครื่องสลับราง M1 และ M2 โดยที่ M1 <= M2 แล้วสั่งให้เครื่อง ค.ล.ต. ปิดหรือเปิดเครื่องสลับรางใดๆ ที่มีหมายเลขอยู่ตั้งแต่ M1 ถึง M2 (ถ้าเครื่องสลับรางใดถูกปิดอยู่แล้วถูกปิด มันก็จะยังถูกปิดอยู่ต่อไป ในทำนองเดียวกัน ถ้าเครื่องสลับรางที่เปิดถูกเปิด มันก็ยังจะเปิดต่อไปอยู่อย่างนั้น) โดยเมื่อแถวของลูกแก้วสลับรางเคลื่อนที่ผ่านเครื่องสลับรางที่ถูกปิดไป ลูกแก้วที่เคลื่อนที่ผ่านเครื่องสลับรางที่ดับอยู่จะไม่ถูกสลับที่

งานของคุณ

จงเขียนโปรแกรมเพื่อรับและประมวลคำสั่งต่อไปนี้

  • เปิดเครื่องสลับรางตั้งแต่หมายเลข M1 ถึง M2
  • ปิดเครื่องสลับรางตั้งแต่หมายเลข M1 ถึง M2
  • ตอบคำถามที่ว่า "เมื่อกำหนด J ให้ ลูกแก้วที่ถูกป‡อนเข้าสู่รางหมายเลข 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
  • "2 M1 M2" โดยที่ 1 <= M1 <= M2 <= M หมายความว่าให้ปิดเครื่องสลับรางตั้งแต่หมายเลข M1 ถึง M2
  • "3 J" โดยที่ 1 <= J <= N หมายความว่าให้ตอบคำถาม "ลูกแก้วที่ถูกป‡อนเข้าสู่รางหมายเลข J ด้านเหนือของเครื่อง ค.ล.ต จะถูก สลับไปอยู่ที่รางหมายเลขใดหลังจากแถวของลูกแก้วผ่านเครื่องสลับรางทั้งหมดไปแล้ว"

ข้อมูลออก

มี Q บรรทัด โดยที่ Q เป็นจำนวนบรรทัดที่มีรูปแบบรูปแบบ "3 J" ในข้อมูลเข้า ในแต่ละบรรทัดให้พิมพ์จำนวนเต็ม K (1 <= K <= 100,000) ซึ่งเป็นคำตอบของคำถามที่ตรงกับบรรทัดรูปแบบ "3 J" ในข้อมูลเข้า เรียงจากคำถามแรกไปยังคำถามสุดท้าย ตามลำดับที่พบในข้อมูลเข้า

ตัวอย่าง

ข้อมูลเข้า 1

5 5
2
4
1
3
3
10
3 1
3 5
1 2 4
3 1
3 5
2 3 3
3 3
1 1 5
3 1
3 3

ข้อมูลออก 1

1
5
2
3
3
2
1

ข้อกำหนด

โปรแกรมของคุณต้องทำงานเสร็จสิ้นในเวลา 2 วินาที และใช้หน่วยความจำไม่เกิน 256 MB