ปืนใหญ่แห่งป้อมปราการ (toi11_cannon)


Time limit:
1000 ms
Memory limit:
512 MB

ชายแดนฝั่งตะวันออกของบุหงาตันหยงนครติดกับชายทะเล ดังนั้นเพื่อป้องกันการรุกรานจากข้าศึก ท่านแม่ทัพประจํากองพันทหารปืนใหญ่แห่งบุหงาตันหยงนครจึงวางแผนจัดกําลังพลทหารปืนใหญ่ประจําบนป้อมปราการ และนําปืนใหญ่จํานวน N กระบอก  (1 ≤ N ≤ 1,000,000)  มาติดตั้งในร่องกําแพงของป้อมปราการ ซึ่งมีจํานวนทั้งหมด 10,000,000 ร่อง แต่ละร่องห่างกัน 1 เมตร เรียงลําดับในแนวเส้นตรง และสามารถติดตั้งปืนใหญ่ได้มากที่สุดหนึ่งกระบอกต่อหนึ่งร่องกําแพงเท่านั้น เรียกแทนตําแหน่งร่องกําแพงว่า ร่องกําแพงที่ 0 1 2 ... 9,999,999 ตามลําดับ 

นอกจากนี้ เพื่อเป็นการอํานวยความสะดวกให้พลทหารในการขนถ่ายกระสุนปืนใหญ่ไปยังปืนใหญ่แต่ละกระบอก ท่านแม่ทัพจึงวางแผนติดตั้งจุดลําเลียงกระสุนปืนใหญ่อีก M จุด   (1 ≤ M ≤ 1,000) ตรงกับตําแหน่งของร่องกําแพงด้วย และแต่ละร่องกําแพงสามารถติดตั้งจุดลําเลียงกระสุนปืนใหญ่ได้มากที่สุดหนึ่งจุดเท่านั้น ทั้งนี้มีความเป็นไปได้ที่จะติดตั้งปืนใหญ่และจุดลําเลียงกระสุนปืนใหญ่ที่ตําแหน่งร่องกําแพงเดียวกัน จากจุดลําเลียงกระสุนปืนใหญ่แต่ละจุดจะมีรางลําเลียงกระสุนความยาว L * 2 เมตร เพื่อใช้ลําเลียงกระสุนปืนใหญ่ไปทางซ้ายและขวาด้านละ L เมตร  (1 ≤ L ≤ 500,000) ดังนั้นหากมีจุดลําเลียงกระสุนปืนใหญ่ที่ร่องกําแพงที่ m จะสามารถลําเลียงกระสุนปืนใหญ่ไปยังปืนใหญ่ทั้งหมดที่ถูกติดตั้งในตําแหน่งร่องกําแพงที่ m - L ถึงตําแหน่งร่องกำแพงที่ m + L และอาจจะมีปือใหญาบางกระบอกที่มีรางลำเลียงกระสุนปืนใหญ่ผ่านมากกว่าหนึ่งราง

ท่านแม่ทัพได้ตัดสินใจจัดวางปืนใหญ่ N กระบอก และวางแผนการจัดวางจุดลําเลียงกระสุนปืนใหญ่ไว้ K รูปแบบ (1 ≤ K ≤ 400) ในแต่ละรูปแบบมีจุดลําเลียงกระสุนปืนใหญ่ M จุดที่แตกต่างกันไป จากตัวอย่างที่ 1 ปืนใหญ่จํานวนสามกระบอกถูกติดตั้งบนร่องกําแพงของป้อมปราการ และจุดลําเลียงกระสุนปืนใหญ่อยู่ที่ร่องกําแพงตําแหน่งที่สอง โดยรางลําเลียงกระสุนปืนใหญ่ในตัวอย่างนี้จะผ่านปืนใหญ่ทั้งหมดจํานวนสองกระบอก ดังรูป

Input

บรรทัดแรก มีจํานวนเต็มสี่จํานวน ประกอบด้วย N ระบุจํานวนปืนใหญ่ที่ถูกติดตั้ง, M ระบุจํานวนจุดลําเลียงกระสุนปืนใหญ่, K ระบุจํานวนรูปแบบของแผนการจัดวางจุดลำเลียงกระสุนปืนใหญ่ และ L ระบุความยาวครึ่งหนึ่งของรางลําเลียงกระสุนปืนใหญ่ในหน่วยเมตร
โดยแต่ละจํานวนถูกคั่นด้วยช่องว่างหนึ่งช่อง กําหนดให้ 1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 1,000, 1 ≤ K ≤ 400, 1 ≤ L ≤ 500,000

บรรทัดที่ 2 มีจํานวนเต็ม N จํานวน แต่ละจํานวน คือ ni ซึ่งระบุตําแหน่งติดตั้งปืนใหญ่กระบอกที่ i เรียงลําดับตําแหน่งจากน้อยไปมาก กําหนดให้ 0 ≤ ni ≤ 9,999,999 และ
1 ≤ i ≤ N

บรรทัดที่ 3 ถึง K + 2 แต่ละบรรทัดมีจํานวนเต็ม M จํานวน แต่ละจํานวน คือ mj ซึ่งระบุตําแหน่งจัดวางจุดลําเลียงกระสุนปืนใหญ่ที่ j ในแผนการจัดวางแต่ละรูปแบบ เรียงลําดับ
ตําแหน่งจากน้อยไปมาก กําหนดให้ 0 ≤ mj ≤ 9,999,999 และ 1 ≤ j ≤ M

Output

มี K บรรทัด แต่ละบรรทัดแสดงจํานวนปืนใหญ่ทั้งหมดที่มีรางลําเลียงกระสุนปืนใหญ่ผ่าน สำหรับแผนการจัดวางแต่ละรูปแบบ

Editor:

Source: Thailand Olympiad in Informatics 2015 (TOI11 / TOI 2015)

Select description language

Thai (brief)
Thai (raw)

If you don't find what you want

Translate it!

Edit this description

Edit

Tag

None