1052.html

<span style="font-family: Courier New;">มีโดมิโน N ชิ้นวางเรียงอยู่บนเส้นแนวแกน x ที่วางตามแนวซ้าย-ขวา&nbsp; จุดปลายด้านซ้ายของเส้นถือว่ามีพิกัดในแกน x เท่ากับ 0&nbsp;&nbsp;&nbsp; เราจะเรียกโดมิโนเรียงตามลำดับจากปลายด้านซ้ายไปยังปลายด้านขวา&nbsp; โดยเริ่มจากชิ้นที่ 1 ไปจนถึงชิ้นที่ N&nbsp;&nbsp; โดมิโนชิ้นที่ I&nbsp; มีความสูง HI และวางอยู่บนเส้นที่มีพิกัดแกน x เท่ากับ XI&nbsp; ตัวอย่างการวาง (ในแนวด้านข้าง) แสดงดังรูป<br />
<br />
<center><img src="./img/1052/1052-1.gif" alt="" /></center><br />
<br />
ในการเล่นโดมิโนนั้น&nbsp; เราจะเลือกโดมิโนตัวแรกแล้วผลักไปทางด้านซ้ายหรือทางด้านขวาก็ได้&nbsp; ถ้าโดมิโน &ldquo;ล้ม&rdquo; ไปโดนโดมิโนตัวใด&nbsp; ตัวที่ถูกล้มโดนจะล้มไปชนตัวอื่น ๆ ด้วย&nbsp;&nbsp; โดมิโนสามารถล้มออกไปนอกขอบของเส้นตรงด้านล่างได้<br />
<br />
อย่างไรก็ตาม เราถือว่าโดมิโนไม่มีความหนา&nbsp; ดังนั้นถ้าล้มไปแล้วปลายโดมิโนไปสัมผัสอีกตัวหนึ่งพอดี จะไม่มีการล้มต่อ&nbsp; ยกตัวอย่างเช่น ถ้ามีโดมิโนความสูง 1 หน่วยอยู่ที่ตำแหน่ง 10&nbsp; และมีโดมิโนอีกชิ้นอยู่ที่ตำแหน่ง 11 ถ้าโดมิโนความสูง 1 หน่วย ถูกทำให้ล้มไปทางด้านขวา&nbsp; โดมิโนที่อยู่ที่ตำแหน่ง 11 จะไม่ล้มไปด้วย เพราะว่าไม่มีการชน (โดมิโนที่ล้มลงมาสัมผัสอีกอันพอดี)<br />
<br />
จงเขียนโปรแกรมรับข้อมูลของโดมิโน&nbsp; จากนั้นให้คำนวณหาโดมิโนตัวตั้งต้นที่เราควรจะไปผลัก (จะเป็นการผลักไปทางซ้ายหรือทางขวาก็ได้)&nbsp; เพื่อทำให้มีโดมิโนล้มลงมากที่สุด<br />
<br />
<u><strong>ข้อมูลนำเข้า</strong></u><br />
<strong>บรรทัดแรก</strong> ระบุจำนวนเต็ม N (1 &lt;= N &lt;= 100,000)&nbsp; จากนั้นอีก N บรรทัดจะระบุข้อมูลของโดมิโนแต่ละอัน&nbsp; กล่าวคือ <strong>บรรทัดที่ 1 + I&nbsp; </strong>จะระบุจำนวนเต็มสองจำนวน&nbsp; XI&nbsp; HI&nbsp;&nbsp; (1 &lt;= XI &lt;= 1,000,000,000; 1 &lt;= HI &lt;= 1,000,000,000)&nbsp; รับประกันว่า&nbsp; 0 &lt;= XI &lt; XI+1&nbsp; สำหรับทุก ๆ&nbsp; 1 &lt;= I &lt; N<br />
<br />
<strong><u>ข้อมูลส่งออก</u></strong><br />
<strong>มีบรรทัดเดียว</strong> ประกอบไปด้วยจำนวนเต็ม J&nbsp; และอักขระ D&nbsp;&nbsp; โดยที่ J คือหมายเลขของโดมิโนที่ถ้าเราเริ่มผลัก และอักขระ D จะเป็นค่า L หรือ R เพื่อระบุทิศทางในการผลัก โดยที่ L แทนการผลักไปทางซ้าย และ R แทนการผลักไปทางขวา&nbsp; ถ้ามีโดมิโนหลายชิ้นที่พลักได้จำนวนเท่ากัน ให้ตอบตัวที่มีหมายเลขน้อยที่สุด&nbsp; และในกรณีที่พิจารณาโดมิโนตัวที่มีหมายเลยน้อยที่สุดแล้วผลักได้ทั้งสองทิศทาง ให้ตอบการผลักไปทางซ้าย<br />
<br />
<u><strong>ข้อมูลชุดทดสอบ</strong></u><br />
ไม่น้อยกว่า 20% ของข้อมูลชุดทดสอบมี N &lt;= 1000<br />
<br />
<u><strong>ที่มา</strong></u><strong>: สอบปฏิบัติ ครั้งที่ 2 ค่ายคัดเลือกผู้แทนประเทศไทย ไปแข่งขันคอมพิวเตอร์โอลิมปิกระหว่างประเทศ ปี 2550 ค่ายที่ 1</strong><br />
</span>
		<table>
			<tr>
				<th>ข้อมูลนำเข้า</th>
				<th>ข้อมูลส่งออก</th>
			</tr>	
		
			<tr>
				<td>5
<br />1 1
<br />3 3
<br />5 4
<br />7 15
<br />10 3
<br /></td>
				<td>2 R</td>
			</tr></table>