1049 : Runner
Problem type : Batch
Time limit : 1.0 second(s)
Memory limit : 16 megabyte(s)
Problem type : Batch
Time limit : 1.0 second(s)
Memory limit : 16 megabyte(s)
นักวิ่ง N คน วิ่งแข่งกันในสนามที่มีลู่วิ่ง M ลู่ ก่อนการแข่งขันจะเริ่มต้น นักวิ่งจะทยอยไปยืนรออยู่ที่ลู่วิ่งโดยจะยืนรอกันตามลำดับที่เดินเข้ามาในสนาม ในการยืนรอนี้ ไม่จำเป็นที่จำนวนนักวิ่งในแต่ละลู่ต้องเท่ากัน เมื่อนักวิ่งยืนที่ลู่ครบทุกคนแล้ว การแข่งจะเริ่มขึ้น โดยจะแบ่งเป็นรอบ ๆ ในรอบที่ 1 นักวิ่งที่ยืนอยู่เป็นอันดับแรกของแต่ละลู่วิ่งจะวิ่งแข่งกัน คนที่มีความเร็วสูงที่สุดจะเป็นผู้ชนะ จากนั้นในรอบถัดมา นักวิ่งคนถัดไปของทุกลู่วิ่งจะวิ่ง การแข่งขันจะดำเนินไปเรื่อย ๆ จนกระทั่งนักวิ่งทุกคนออกวิ่ง
ให้เขียนโปรแกรมรับข้อมูลการเดินเข้าลู่วิ่งของนักวิ่งแต่ละคน พร้อมด้วยอัตราเร็วในการวิ่ง จากนั้นให้โปรแกรมคำนวณหาผู้ชนะในการวิ่งแต่ละรอบจนครบทุกรอบ
ข้อมูลนำเข้า
ให้อ่านข้อมูลจาก standard input ข้อมูลในบรรทัดแรกประกอบด้วยจำนวนเต็ม N และ M (1 <= N <= 100,000; 1 <= M <= 10,000) จากนั้นอีก N บรรทัดจะเป็นข้อมูลการเดินเข้าสนามและความเร็วของนักวิ่งแต่ละคน กล่าวคือ ในบรรทัดที่ 1 + i จะเป็นข้อมูลของนักวิ่งที่เดินเข้าสนามมาเป็นลำดับที่ i บรรทัดดังกล่าวประกอบไปด้วยจำนวนเต็ม Ai Li Si โดยที่ Ai คือหมายเลขของนักแข่งซึ่งจะไม่ซ้ำกัน Li แทนหมายเลขลู่ที่เขาเดินไปรอ และ Si แทนความเร็วของนักวิ่ง (1<= Ai <= 1,000,000; 1<= Li <= M; 1<= Si <= 1,000,000)
ข้อมูลส่งออก
แสดงออกทาง standard output ผลลัพธ์จะมีจำนวนบรรทัดเท่ากับจำนวนรอบของการแข่งขัน ในแต่ละบรรทัด j ให้พิมพ์หมายเลขของนักวิ่งที่ชนะในรอบที่ j นักวิ่งที่ชนะในรอบที่ j คือคนที่มีอัตราเร็วสูงสุดที่วิ่งในรอบนั้น ถ้านักวิ่งที่มีอัตราเร็วมากที่สุดมีมากกว่าหนึ่งคน ให้ตอบคนที่อยู่ในลู่วิ่งที่มีหมายเลขน้อยที่สุด
ข้อมูลชุดทดสอบ
ใน 30% ของข้อมูลชุดทดสอบ N <= 100; M<= 100
ที่มา: สอบปฏิบัติ ครั้งที่ 1 ค่ายคัดเลือกผู้แทนประเทศไทย ไปแข่งขันคอมพิวเตอร์โอลิมปิกระหว่างประเทศ ปี 2550 ค่ายที่ 1
รูปประกอบตัวอย่างข้อมูลนำเข้า
ความช่วยเหลือ: ไม่มีคำใบ้สำหรับปัญหานี้
ให้เขียนโปรแกรมรับข้อมูลการเดินเข้าลู่วิ่งของนักวิ่งแต่ละคน พร้อมด้วยอัตราเร็วในการวิ่ง จากนั้นให้โปรแกรมคำนวณหาผู้ชนะในการวิ่งแต่ละรอบจนครบทุกรอบ
ข้อมูลนำเข้า
ให้อ่านข้อมูลจาก standard input ข้อมูลในบรรทัดแรกประกอบด้วยจำนวนเต็ม N และ M (1 <= N <= 100,000; 1 <= M <= 10,000) จากนั้นอีก N บรรทัดจะเป็นข้อมูลการเดินเข้าสนามและความเร็วของนักวิ่งแต่ละคน กล่าวคือ ในบรรทัดที่ 1 + i จะเป็นข้อมูลของนักวิ่งที่เดินเข้าสนามมาเป็นลำดับที่ i บรรทัดดังกล่าวประกอบไปด้วยจำนวนเต็ม Ai Li Si โดยที่ Ai คือหมายเลขของนักแข่งซึ่งจะไม่ซ้ำกัน Li แทนหมายเลขลู่ที่เขาเดินไปรอ และ Si แทนความเร็วของนักวิ่ง (1<= Ai <= 1,000,000; 1<= Li <= M; 1<= Si <= 1,000,000)
ข้อมูลส่งออก
แสดงออกทาง standard output ผลลัพธ์จะมีจำนวนบรรทัดเท่ากับจำนวนรอบของการแข่งขัน ในแต่ละบรรทัด j ให้พิมพ์หมายเลขของนักวิ่งที่ชนะในรอบที่ j นักวิ่งที่ชนะในรอบที่ j คือคนที่มีอัตราเร็วสูงสุดที่วิ่งในรอบนั้น ถ้านักวิ่งที่มีอัตราเร็วมากที่สุดมีมากกว่าหนึ่งคน ให้ตอบคนที่อยู่ในลู่วิ่งที่มีหมายเลขน้อยที่สุด
ข้อมูลชุดทดสอบ
ใน 30% ของข้อมูลชุดทดสอบ N <= 100; M<= 100
ที่มา: สอบปฏิบัติ ครั้งที่ 1 ค่ายคัดเลือกผู้แทนประเทศไทย ไปแข่งขันคอมพิวเตอร์โอลิมปิกระหว่างประเทศ ปี 2550 ค่ายที่ 1
รูปประกอบตัวอย่างข้อมูลนำเข้า
| ตัวอย่างข้อมูลนำเข้า | ตัวอย่างข้อมูลส่งออก |
| 6 3 1 1 10 2 2 5 3 2 10 4 3 10 5 1 7 6 2 7 | 1 3 6 |
ความช่วยเหลือ: ไม่มีคำใบ้สำหรับปัญหานี้
กำลังออนไลน์: 8 ผู้เยี่ยมชมและ 0 สมาชิก (0 บอท)