1088 : กิ้งก่า (iguana)
Problem type : Batch
Time limit : 0.5 second(s)
Memory limit : 32 megabyte(s)
Problem type : Batch
Time limit : 0.5 second(s)
Memory limit : 32 megabyte(s)
คุณเป็นเจ้าของสวนสัตว์ ที่มีกิ้งก่าชนิดประหลาดหายากนำเข้าอยู่ N ตัว อยู่ใน N กรงที่วางเรียงกัน ถ้าเกิดว่ามีคนเอานิ้วไปจิ้มกิ้งก่าชนิดนี้ มันจะเปลี่ยนสีทันที และอาหารที่มันอยากกินก็จะเปลี่ยนไปตามสีของมันด้วย
กิ้งก่ามีสีที่เป็นไปได้สามสี คือ แดง เขียว และ น้ำเงิน กิ้งก่าสีแดงจะเปลี่ยนสีเป็นสีเขียวเมื่อถูกจิ้ม สีเขียวจะเปลี่ยนเป็นสีน้ำเงิน และสีน้ำเงินจะเปลี่ยนเป็นสีแดง เริ่มต้นกิ้งก่าทุกตัวเป็นสีแดง
เนื่องจากมีกิ้งก่าหิวโซตัวหนึ่งคาบกุญแจของคุณไปกิน ทำให้คุณไม่ได้ล็อกกรง เมื่อวานนี้ มีเด็กมือบอน M คนเข้ามา คนที่ i เดินจิ้มกิ้งก่าตั้งแต่ตัวละ A_i ถึงตัวที่ B_i ตัวละหนึ่งครั้ง จนกิ้งก่าเปลี่ยนสีมั่วไปหมด
และเนื่องจากมีกิ้งก่าตัวหนึ่งป่วนคุณตอนกำลังสั่งอาหาร ทำให้อาหารทั้งหมดที่สั่งมานั้นกลายเป็นอาหารสำหรับกิ้งก่าสีเดียว ซึ่งคุณจะเปลี่ยนก็ไม่ทันแล้ว ถามว่า คุณต้องไปจิ้มกิ้งก่าอย่างน้อยกี่ครั้ง เพื่อให้กิ้งก่าทุกตัวสามารถกินอาหารที่สั่งมาได้
งานของคุณ
จงเขียนโปรแกรมรับจำนวนกิ้งก่า การจิ้มกิ้งก่าของเด็ก และอาหารสีที่คุณสั่งมา แล้วตอบว่า คุณต้องจิ้มกิ้งก่าอย่างน้อยกี่ครั้ง เพื่อให้ทุกตัวสีเดียวกับอาหารนั้น
ข้อมูลนำเข้า
บรรทัดแรกมีจำนวนเต็มบวกสองจำนวน N, M (1≤N≤100,000,000, 0≤M≤100,000)
บรรทัดถัดไป M บรรทัด มีจำนวนเต็มบวกสองจำนวน A_i, B_i (1≤Ai≤Bi≤N) เป็นการบอกว่า เด็กมือบอนแต่ละคนจิ้มกิ้งก่าตั้งแต่ตัวไหนถึงตัวไหน
บรรทัดถัดไป มีตัวหนังสือภาษาอังกฤษหนึ่งตัว R (แดง), G (เขียว) หรือ B (น้ำเงิน) เป็นการบอกว่า อาหารที่สั่งมาสำหรับกิ้งก่าสีอะไร
ข้อมูลส่งออก
มีบรรทัดเดียว มีจำนวนเต็ม บอกจำนวนครั้งที่น้อยที่สุดที่ต้องจิ้มกิ้งก่า ที่จะทำให้กิ้งก่าทุกตัวเป็นสีเดียวกับอาหาร
อธิบายข้อมูลน้ำเข้าและส่งออก
หลังจากการจิ้มทั้งหมด กิ้งก่าตัวแรกจะมีสีเขียว ตัวที่สองสีน้ำเงิน และตัวที่สามสีเขียว อาหารที่สั่งมาเป็นสีแดง จึงต้องจิ้มกิ้งก่าตัวแรกสองครั้ง ตัวที่สองหนึ่งครั้ง และตัวที่สามสองครั้ง เพื่อให้ทุกตัวเปลี่ยนเป็นสีแดง
ความช่วยเหลือ: ไม่มีคำใบ้สำหรับปัญหานี้
กิ้งก่ามีสีที่เป็นไปได้สามสี คือ แดง เขียว และ น้ำเงิน กิ้งก่าสีแดงจะเปลี่ยนสีเป็นสีเขียวเมื่อถูกจิ้ม สีเขียวจะเปลี่ยนเป็นสีน้ำเงิน และสีน้ำเงินจะเปลี่ยนเป็นสีแดง เริ่มต้นกิ้งก่าทุกตัวเป็นสีแดง
เนื่องจากมีกิ้งก่าหิวโซตัวหนึ่งคาบกุญแจของคุณไปกิน ทำให้คุณไม่ได้ล็อกกรง เมื่อวานนี้ มีเด็กมือบอน M คนเข้ามา คนที่ i เดินจิ้มกิ้งก่าตั้งแต่ตัวละ A_i ถึงตัวที่ B_i ตัวละหนึ่งครั้ง จนกิ้งก่าเปลี่ยนสีมั่วไปหมด
และเนื่องจากมีกิ้งก่าตัวหนึ่งป่วนคุณตอนกำลังสั่งอาหาร ทำให้อาหารทั้งหมดที่สั่งมานั้นกลายเป็นอาหารสำหรับกิ้งก่าสีเดียว ซึ่งคุณจะเปลี่ยนก็ไม่ทันแล้ว ถามว่า คุณต้องไปจิ้มกิ้งก่าอย่างน้อยกี่ครั้ง เพื่อให้กิ้งก่าทุกตัวสามารถกินอาหารที่สั่งมาได้
งานของคุณ
จงเขียนโปรแกรมรับจำนวนกิ้งก่า การจิ้มกิ้งก่าของเด็ก และอาหารสีที่คุณสั่งมา แล้วตอบว่า คุณต้องจิ้มกิ้งก่าอย่างน้อยกี่ครั้ง เพื่อให้ทุกตัวสีเดียวกับอาหารนั้น
ข้อมูลนำเข้า
บรรทัดแรกมีจำนวนเต็มบวกสองจำนวน N, M (1≤N≤100,000,000, 0≤M≤100,000)
บรรทัดถัดไป M บรรทัด มีจำนวนเต็มบวกสองจำนวน A_i, B_i (1≤Ai≤Bi≤N) เป็นการบอกว่า เด็กมือบอนแต่ละคนจิ้มกิ้งก่าตั้งแต่ตัวไหนถึงตัวไหน
บรรทัดถัดไป มีตัวหนังสือภาษาอังกฤษหนึ่งตัว R (แดง), G (เขียว) หรือ B (น้ำเงิน) เป็นการบอกว่า อาหารที่สั่งมาสำหรับกิ้งก่าสีอะไร
ข้อมูลส่งออก
มีบรรทัดเดียว มีจำนวนเต็ม บอกจำนวนครั้งที่น้อยที่สุดที่ต้องจิ้มกิ้งก่า ที่จะทำให้กิ้งก่าทุกตัวเป็นสีเดียวกับอาหาร
อธิบายข้อมูลน้ำเข้าและส่งออก
หลังจากการจิ้มทั้งหมด กิ้งก่าตัวแรกจะมีสีเขียว ตัวที่สองสีน้ำเงิน และตัวที่สามสีเขียว อาหารที่สั่งมาเป็นสีแดง จึงต้องจิ้มกิ้งก่าตัวแรกสองครั้ง ตัวที่สองหนึ่งครั้ง และตัวที่สามสองครั้ง เพื่อให้ทุกตัวเปลี่ยนเป็นสีแดง
การให้คะแนน
- 50% ของชุดข้อมูลทดสอบทั้งหมด N≤10,000 และ M≤10,000
- 70% ของชุดข้อมูลทดสอบทั้งหมด N≤100,000,000 และ M≤10,000
- ทุกชุดข้อมูลทดสอบ N≤100,000,000 และ M≤100,000
โจทย์โดย: ทักษพร กิตติอัครเสถียร
ที่มา: TOI.C:04-2009
| ตัวอย่างข้อมูลนำเข้า | ตัวอย่างข้อมูลส่งออก |
| 3 2 1 2 2 3 R | 5 |
ความช่วยเหลือ: ไม่มีคำใบ้สำหรับปัญหานี้
กำลังออนไลน์: 6 ผู้เยี่ยมชมและ 0 สมาชิก (0 บอท)