1052 : Domino
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 ชิ้นวางเรียงอยู่บนเส้นแนวแกน x ที่วางตามแนวซ้าย-ขวา จุดปลายด้านซ้ายของเส้นถือว่ามีพิกัดในแกน x เท่ากับ 0 เราจะเรียกโดมิโนเรียงตามลำดับจากปลายด้านซ้ายไปยังปลายด้านขวา โดยเริ่มจากชิ้นที่ 1 ไปจนถึงชิ้นที่ N โดมิโนชิ้นที่ I มีความสูง HI และวางอยู่บนเส้นที่มีพิกัดแกน x เท่ากับ XI ตัวอย่างการวาง (ในแนวด้านข้าง) แสดงดังรูป
ในการเล่นโดมิโนนั้น เราจะเลือกโดมิโนตัวแรกแล้วผลักไปทางด้านซ้ายหรือทางด้านขวาก็ได้ ถ้าโดมิโน “ล้ม” ไปโดนโดมิโนตัวใด ตัวที่ถูกล้มโดนจะล้มไปชนตัวอื่น ๆ ด้วย โดมิโนสามารถล้มออกไปนอกขอบของเส้นตรงด้านล่างได้
อย่างไรก็ตาม เราถือว่าโดมิโนไม่มีความหนา ดังนั้นถ้าล้มไปแล้วปลายโดมิโนไปสัมผัสอีกตัวหนึ่งพอดี จะไม่มีการล้มต่อ ยกตัวอย่างเช่น ถ้ามีโดมิโนความสูง 1 หน่วยอยู่ที่ตำแหน่ง 10 และมีโดมิโนอีกชิ้นอยู่ที่ตำแหน่ง 11 ถ้าโดมิโนความสูง 1 หน่วย ถูกทำให้ล้มไปทางด้านขวา โดมิโนที่อยู่ที่ตำแหน่ง 11 จะไม่ล้มไปด้วย เพราะว่าไม่มีการชน (โดมิโนที่ล้มลงมาสัมผัสอีกอันพอดี)
จงเขียนโปรแกรมรับข้อมูลของโดมิโน จากนั้นให้คำนวณหาโดมิโนตัวตั้งต้นที่เราควรจะไปผลัก (จะเป็นการผลักไปทางซ้ายหรือทางขวาก็ได้) เพื่อทำให้มีโดมิโนล้มลงมากที่สุด
ข้อมูลนำเข้า
บรรทัดแรก ระบุจำนวนเต็ม N (1 <= N <= 100,000) จากนั้นอีก N บรรทัดจะระบุข้อมูลของโดมิโนแต่ละอัน กล่าวคือ บรรทัดที่ 1 + I จะระบุจำนวนเต็มสองจำนวน XI HI (1 <= XI <= 1,000,000,000; 1 <= HI <= 1,000,000,000) รับประกันว่า 0 <= XI < XI+1 สำหรับทุก ๆ 1 <= I < N
ข้อมูลส่งออก
มีบรรทัดเดียว ประกอบไปด้วยจำนวนเต็ม J และอักขระ D โดยที่ J คือหมายเลขของโดมิโนที่ถ้าเราเริ่มผลัก และอักขระ D จะเป็นค่า L หรือ R เพื่อระบุทิศทางในการผลัก โดยที่ L แทนการผลักไปทางซ้าย และ R แทนการผลักไปทางขวา ถ้ามีโดมิโนหลายชิ้นที่พลักได้จำนวนเท่ากัน ให้ตอบตัวที่มีหมายเลขน้อยที่สุด และในกรณีที่พิจารณาโดมิโนตัวที่มีหมายเลยน้อยที่สุดแล้วผลักได้ทั้งสองทิศทาง ให้ตอบการผลักไปทางซ้าย
ข้อมูลชุดทดสอบ
ไม่น้อยกว่า 20% ของข้อมูลชุดทดสอบมี N <= 1000
ที่มา: สอบปฏิบัติ ครั้งที่ 2 ค่ายคัดเลือกผู้แทนประเทศไทย ไปแข่งขันคอมพิวเตอร์โอลิมปิกระหว่างประเทศ ปี 2550 ค่ายที่ 1
ความช่วยเหลือ: ไม่มีคำใบ้สำหรับปัญหานี้
ในการเล่นโดมิโนนั้น เราจะเลือกโดมิโนตัวแรกแล้วผลักไปทางด้านซ้ายหรือทางด้านขวาก็ได้ ถ้าโดมิโน “ล้ม” ไปโดนโดมิโนตัวใด ตัวที่ถูกล้มโดนจะล้มไปชนตัวอื่น ๆ ด้วย โดมิโนสามารถล้มออกไปนอกขอบของเส้นตรงด้านล่างได้
อย่างไรก็ตาม เราถือว่าโดมิโนไม่มีความหนา ดังนั้นถ้าล้มไปแล้วปลายโดมิโนไปสัมผัสอีกตัวหนึ่งพอดี จะไม่มีการล้มต่อ ยกตัวอย่างเช่น ถ้ามีโดมิโนความสูง 1 หน่วยอยู่ที่ตำแหน่ง 10 และมีโดมิโนอีกชิ้นอยู่ที่ตำแหน่ง 11 ถ้าโดมิโนความสูง 1 หน่วย ถูกทำให้ล้มไปทางด้านขวา โดมิโนที่อยู่ที่ตำแหน่ง 11 จะไม่ล้มไปด้วย เพราะว่าไม่มีการชน (โดมิโนที่ล้มลงมาสัมผัสอีกอันพอดี)
จงเขียนโปรแกรมรับข้อมูลของโดมิโน จากนั้นให้คำนวณหาโดมิโนตัวตั้งต้นที่เราควรจะไปผลัก (จะเป็นการผลักไปทางซ้ายหรือทางขวาก็ได้) เพื่อทำให้มีโดมิโนล้มลงมากที่สุด
ข้อมูลนำเข้า
บรรทัดแรก ระบุจำนวนเต็ม N (1 <= N <= 100,000) จากนั้นอีก N บรรทัดจะระบุข้อมูลของโดมิโนแต่ละอัน กล่าวคือ บรรทัดที่ 1 + I จะระบุจำนวนเต็มสองจำนวน XI HI (1 <= XI <= 1,000,000,000; 1 <= HI <= 1,000,000,000) รับประกันว่า 0 <= XI < XI+1 สำหรับทุก ๆ 1 <= I < N
ข้อมูลส่งออก
มีบรรทัดเดียว ประกอบไปด้วยจำนวนเต็ม J และอักขระ D โดยที่ J คือหมายเลขของโดมิโนที่ถ้าเราเริ่มผลัก และอักขระ D จะเป็นค่า L หรือ R เพื่อระบุทิศทางในการผลัก โดยที่ L แทนการผลักไปทางซ้าย และ R แทนการผลักไปทางขวา ถ้ามีโดมิโนหลายชิ้นที่พลักได้จำนวนเท่ากัน ให้ตอบตัวที่มีหมายเลขน้อยที่สุด และในกรณีที่พิจารณาโดมิโนตัวที่มีหมายเลยน้อยที่สุดแล้วผลักได้ทั้งสองทิศทาง ให้ตอบการผลักไปทางซ้าย
ข้อมูลชุดทดสอบ
ไม่น้อยกว่า 20% ของข้อมูลชุดทดสอบมี N <= 1000
ที่มา: สอบปฏิบัติ ครั้งที่ 2 ค่ายคัดเลือกผู้แทนประเทศไทย ไปแข่งขันคอมพิวเตอร์โอลิมปิกระหว่างประเทศ ปี 2550 ค่ายที่ 1
| ตัวอย่างข้อมูลนำเข้า | ตัวอย่างข้อมูลส่งออก |
| 5 1 1 3 3 5 4 7 15 10 3 | 2 R |
ความช่วยเหลือ: ไม่มีคำใบ้สำหรับปัญหานี้
กำลังออนไลน์: 5 ผู้เยี่ยมชมและ 0 สมาชิก (0 บอท)