1049.html

<span style="font-family: Courier New;">นักวิ่ง N คน วิ่งแข่งกันในสนามที่มีลู่วิ่ง M ลู่ ก่อนการแข่งขันจะเริ่มต้น นักวิ่งจะทยอยไปยืนรออยู่ที่ลู่วิ่งโดยจะยืนรอกันตามลำดับที่เดินเข้ามาในสนาม&nbsp; ในการยืนรอนี้ ไม่จำเป็นที่จำนวนนักวิ่งในแต่ละลู่ต้องเท่ากัน&nbsp; เมื่อนักวิ่งยืนที่ลู่ครบทุกคนแล้ว การแข่งจะเริ่มขึ้น&nbsp; โดยจะแบ่งเป็นรอบ ๆ&nbsp;&nbsp; ในรอบที่ 1 นักวิ่งที่ยืนอยู่เป็นอันดับแรกของแต่ละลู่วิ่งจะวิ่งแข่งกัน&nbsp; คนที่มีความเร็วสูงที่สุดจะเป็นผู้ชนะ&nbsp; จากนั้นในรอบถัดมา นักวิ่งคนถัดไปของทุกลู่วิ่งจะวิ่ง&nbsp; การแข่งขันจะดำเนินไปเรื่อย&nbsp; ๆ จนกระทั่งนักวิ่งทุกคนออกวิ่ง<br />
<br />
ให้เขียนโปรแกรมรับข้อมูลการเดินเข้าลู่วิ่งของนักวิ่งแต่ละคน พร้อมด้วยอัตราเร็วในการวิ่ง&nbsp; จากนั้นให้โปรแกรมคำนวณหาผู้ชนะในการวิ่งแต่ละรอบจนครบทุกรอบ<br />
<br />
<u><strong>ข้อมูลนำเข้า</strong></u><br />
ให้อ่านข้อมูลจาก standard input&nbsp; ข้อมูลในบรรทัดแรกประกอบด้วยจำนวนเต็ม N และ M&nbsp; (1 &lt;= N &lt;= 100,000; 1 &lt;= M &lt;= 10,000)&nbsp; จากนั้นอีก N บรรทัดจะเป็นข้อมูลการเดินเข้าสนามและความเร็วของนักวิ่งแต่ละคน&nbsp; กล่าวคือ ในบรรทัดที่ 1 + i&nbsp; จะเป็นข้อมูลของนักวิ่งที่เดินเข้าสนามมาเป็นลำดับที่ i&nbsp; บรรทัดดังกล่าวประกอบไปด้วยจำนวนเต็ม Ai Li Si&nbsp;&nbsp; โดยที่ Ai คือหมายเลขของนักแข่งซึ่งจะไม่ซ้ำกัน&nbsp; Li แทนหมายเลขลู่ที่เขาเดินไปรอ และ Si แทนความเร็วของนักวิ่ง&nbsp; (1&lt;= Ai &lt;= 1,000,000; 1&lt;= Li &lt;= M; 1&lt;= Si &lt;= 1,000,000)<br />
<br />
<u><strong>ข้อมูลส่งออก</strong></u><br />
แสดงออกทาง standard output&nbsp; ผลลัพธ์จะมีจำนวนบรรทัดเท่ากับจำนวนรอบของการแข่งขัน ในแต่ละบรรทัด j ให้พิมพ์หมายเลขของนักวิ่งที่ชนะในรอบที่ j&nbsp; นักวิ่งที่ชนะในรอบที่ j คือคนที่มีอัตราเร็วสูงสุดที่วิ่งในรอบนั้น&nbsp; ถ้านักวิ่งที่มีอัตราเร็วมากที่สุดมีมากกว่าหนึ่งคน ให้ตอบคนที่อยู่ในลู่วิ่งที่มีหมายเลขน้อยที่สุด<br />
<br />
<u><strong>ข้อมูลชุดทดสอบ</strong></u><br />
ใน 30% ของข้อมูลชุดทดสอบ N &lt;= 100; M&lt;= 100<br />
<br />
<u><strong>ที่มา</strong></u><strong>: สอบปฏิบัติ ครั้งที่ 1 ค่ายคัดเลือกผู้แทนประเทศไทย ไปแข่งขันคอมพิวเตอร์โอลิมปิกระหว่างประเทศ ปี 2550 ค่ายที่ 1</strong><br />
<br />
<u><strong>รูปประกอบตัวอย่างข้อมูลนำเข้า</strong></u><br />
<img alt="" src="./img/1049/1049-1.gif" /> </span>
		<table>
			<tr>
				<th>ข้อมูลนำเข้า</th>
				<th>ข้อมูลส่งออก</th>
			</tr>	
		
			<tr>
				<td>6 3
<br />1 1 10
<br />2 2 5
<br />3 2 10
<br />4 3 10
<br />5 1 7
<br />6 2 7
<br /></td>
				<td>1
<br />3
<br />6
<br /></td>
			</tr></table>