1085 : ล่าสมบัติทั่วทุกทิศ (explore)
Problem type : Batch
Time limit : 1.0 second(s)
Memory limit : 32 megabyte(s)
Problem type : Batch
Time limit : 1.0 second(s)
Memory limit : 32 megabyte(s)
ในที่สุด หลังจากลุ้นตัวโก่ง คุณก็สามารถผ่านการตอบปัญหาไปได้ ขั้นต่อมาก็คือ ตามหาอัญมณีนี้ในโบราณสถานอันกว้างใหญ่
คุณรู้มาว่า อัญมณีชิ้นนี้ถูกซ่อนอยู่ในโบราณสถานซึ่งมีลักษณะเป็นห้องๆซึ่งมีทั้งหมด n ห้อง คือห้องที่ 1,2,3,…,n ซึ่งห้องที่อยู่ติดกันจะมีประตูหากันได้ กล่าวคือ ห้องที่ 1 จะมีประตูเชื่อมกับห้องที่ 2 , ห้องที่ 2 จะมีประตูเชื่อมกับห้องที่ 3 , … , ห้องที่ n-1 จะมีประตูเชื่อมกับห้องที่ n
***โดยประตูนั้นจะเป็นประตูทางเดียว กล่าวคือ จะไม่สามารถใช้เดินทางจากห้อง i+1 ไปยัง ห้อง i ได้ แต่จะสามารถใช้เดินทางได้เฉพาะการเดินทางจาก ห้อง i ไปยัง ห้อง i+1 (เมื่อ 1 <= i < n)
เนื่องจากอัญมณีดังกล่าวนั้นมีมูลค่าสูงจนประเมินไม่ได้ มันจึงถูกซ่อนอยู่ในห้องที่ n ยิ่งไปกว่านั้นแล้ว เทพเจ้าที่รักษาสถานที่นี้ไม่ต้องการให้คุณได้อัญมณีล้ำค่าไปง่ายๆจึงสร้างหินมากั้นห้องบางห้องไว้ทำให้คุณไม่สามารถเดินไปต่อยังห้องต่อไปได้
แต่ยังโชคดีที่คุณค้นพบระบบขนย้ายมวลสารในโบราณสถานนี้ กล่าวคือคุณสามารถข้ามจากห้องที่มีเครื่องขนย้ายมวลสารไปยังห้องปลายทางที่เครื่องกำหนดได้ ซึ่งเครื่องนี้มีลักษณะพิเศษคือ จะเคลื่อนย้ายคุณไปยังห้องที่มีเลขสูงกว่าเท่านั้น คุณจะได้รับข้อมูลของโบราณสถานทั้งหมดแล้วจงหาว่า คุณสามารถไปถึงห้องที่มีอัญมณีได้หรือไม่ ถ้าไม่ได้ คุณสามารถไปยังห้องที่มีเลขห้องมากสุดเท่าใด โดยเริ่มต้นคุณอยู่ที่ห้องหมายเลข 1
งานของคุณ
จงเขียนโปรแกรมรับข้อมูลของโบราณสถานนี้ และตอบว่า คุณสามารถไปยังห้องที่มีอัญมณีได้หรือไม่ ถ้าไม่ได้ คุณสามารถไปยังห้องที่มีเลขห้องมากสุดเท่าใด
ข้อมูลนำเข้า
บรรทัดแรก มีจำนวนเต็มบวก n, m, k แทนจำนวนห้องทั้งหมด จำนวนเครื่องขนย้ายมวลสาร และ จำนวนหินกั้นทางตามลำดับ โดยที่ 1 <= n <= 500,000, 0 <= m <=1,000,000, 0 <= k <= n-1
อีก m บรรทัดต่อมา แต่ละบรรทัดประกอบด้วยจำนวนเต็ม 2 จำนวน a, b หมายความว่า ในห้อง a มีเครื่องขนย้ายมวลสาร ที่สามารถใช้เดินทางไปยังห้อง b ได้
อีก k บรรทัดต่อมา แต่ละบรรทัดมีจำนวนเต็ม x ซึ่งบอกว่ามีหินกั้น ระหว่างห้อง x กับ x + 1
ข้อมูลส่งออก
มีบรรทัดเดียว ถ้าสามารถเก็บอัญมณีได้ให้พิมพ์ 1 ถ้าเก็บอัญมณีไม่ได้ให้พิมพ์ 0 แล้วตามด้วยหมายเลขห้องที่มีค่าสูงสุดที่ไปถึงได้
โจทย์โดย: วีระกานต์ สินทวีเลิศมงคล
ที่มา: TOI.CPP:03-2009
ความช่วยเหลือ: ไม่มีคำใบ้สำหรับปัญหานี้
คุณรู้มาว่า อัญมณีชิ้นนี้ถูกซ่อนอยู่ในโบราณสถานซึ่งมีลักษณะเป็นห้องๆซึ่งมีทั้งหมด n ห้อง คือห้องที่ 1,2,3,…,n ซึ่งห้องที่อยู่ติดกันจะมีประตูหากันได้ กล่าวคือ ห้องที่ 1 จะมีประตูเชื่อมกับห้องที่ 2 , ห้องที่ 2 จะมีประตูเชื่อมกับห้องที่ 3 , … , ห้องที่ n-1 จะมีประตูเชื่อมกับห้องที่ n
***โดยประตูนั้นจะเป็นประตูทางเดียว กล่าวคือ จะไม่สามารถใช้เดินทางจากห้อง i+1 ไปยัง ห้อง i ได้ แต่จะสามารถใช้เดินทางได้เฉพาะการเดินทางจาก ห้อง i ไปยัง ห้อง i+1 (เมื่อ 1 <= i < n)
เนื่องจากอัญมณีดังกล่าวนั้นมีมูลค่าสูงจนประเมินไม่ได้ มันจึงถูกซ่อนอยู่ในห้องที่ n ยิ่งไปกว่านั้นแล้ว เทพเจ้าที่รักษาสถานที่นี้ไม่ต้องการให้คุณได้อัญมณีล้ำค่าไปง่ายๆจึงสร้างหินมากั้นห้องบางห้องไว้ทำให้คุณไม่สามารถเดินไปต่อยังห้องต่อไปได้
แต่ยังโชคดีที่คุณค้นพบระบบขนย้ายมวลสารในโบราณสถานนี้ กล่าวคือคุณสามารถข้ามจากห้องที่มีเครื่องขนย้ายมวลสารไปยังห้องปลายทางที่เครื่องกำหนดได้ ซึ่งเครื่องนี้มีลักษณะพิเศษคือ จะเคลื่อนย้ายคุณไปยังห้องที่มีเลขสูงกว่าเท่านั้น คุณจะได้รับข้อมูลของโบราณสถานทั้งหมดแล้วจงหาว่า คุณสามารถไปถึงห้องที่มีอัญมณีได้หรือไม่ ถ้าไม่ได้ คุณสามารถไปยังห้องที่มีเลขห้องมากสุดเท่าใด โดยเริ่มต้นคุณอยู่ที่ห้องหมายเลข 1
งานของคุณ
จงเขียนโปรแกรมรับข้อมูลของโบราณสถานนี้ และตอบว่า คุณสามารถไปยังห้องที่มีอัญมณีได้หรือไม่ ถ้าไม่ได้ คุณสามารถไปยังห้องที่มีเลขห้องมากสุดเท่าใด
ข้อมูลนำเข้า
บรรทัดแรก มีจำนวนเต็มบวก n, m, k แทนจำนวนห้องทั้งหมด จำนวนเครื่องขนย้ายมวลสาร และ จำนวนหินกั้นทางตามลำดับ โดยที่ 1 <= n <= 500,000, 0 <= m <=1,000,000, 0 <= k <= n-1
อีก m บรรทัดต่อมา แต่ละบรรทัดประกอบด้วยจำนวนเต็ม 2 จำนวน a, b หมายความว่า ในห้อง a มีเครื่องขนย้ายมวลสาร ที่สามารถใช้เดินทางไปยังห้อง b ได้
อีก k บรรทัดต่อมา แต่ละบรรทัดมีจำนวนเต็ม x ซึ่งบอกว่ามีหินกั้น ระหว่างห้อง x กับ x + 1
ข้อมูลส่งออก
มีบรรทัดเดียว ถ้าสามารถเก็บอัญมณีได้ให้พิมพ์ 1 ถ้าเก็บอัญมณีไม่ได้ให้พิมพ์ 0 แล้วตามด้วยหมายเลขห้องที่มีค่าสูงสุดที่ไปถึงได้
โจทย์โดย: วีระกานต์ สินทวีเลิศมงคล
ที่มา: TOI.CPP:03-2009
| ตัวอย่างข้อมูลนำเข้า | ตัวอย่างข้อมูลส่งออก |
| 5 1 1 2 5 2 | 1 |
| 5 1 1 1 2 2 | 0 2 |
ความช่วยเหลือ: ไม่มีคำใบ้สำหรับปัญหานี้
กำลังออนไลน์: 5 ผู้เยี่ยมชมและ 0 สมาชิก (0 บอท)