1031 : Tower
Problem type : Batch
Time limit : 1.0 second(s)
Memory limit : 128 megabyte(s)
Problem type : Batch
Time limit : 1.0 second(s)
Memory limit : 128 megabyte(s)
จอมยุทธทุกคนก่อนที่จะเป็นยอดฝีมือได้นั้นจะต้องผ่านการฝึกฝนที่หนักหนาสาหัสด้วยกันทั้งสิ้น วิธีหนึ่งในการฝึกฝนตนเองของเหล่ายอดยุทธ คือ การฝ่าด่านต่างๆ ในหอฝึกยุทธ ชาวยุทธแต่ละคนที่ผ่านหอฝึกยุทธมาได้ล้วนกลายเป็นผู้เลื่องชื่อ ยิ่งขึ้นไปบนหอฝึกยุทธได้สูงเท่าไร ก็จะได้ยอดวิชาในระดับที่สูงขึ้นไปเท่านั้น อย่างไรก็ตามแต่ละคนมีพลังในการฝ่าด่านไม่เท่ากัน ไม่ใช่ว่าใครก็จะสามารถขึ้นไปบนหอชั้นสูงสุดได้
ในการฝ่าแต่ละด่านผู้ฝึกยุทธจะต้องเสียพลังงานไปหนึ่งหน่วยและต้องฝ่าด่านให้ได้ ก่อนถึงจะไปยังชั้น ต่อไปได้ แต่ละชั้นไม่จำเป็นต้องมีบันไดเชื่อมกับชั้นที่ติดกัน บางชั้นอาจจะไม่มีบันไดเลยในขณะที่บางชั้นอาจจะมีบันไดมากกว่าหนึ่งอันก็ได้ และบันไดทุกอันเป็นบันไดพิเศษที่ขึ้นได้ลงไม่ได้ (ตอนขากลับผู้ฝึกยุทธต้องใช้วิชาตัวเบาร่อนลงมายังชั้นล่างสุด)
คุณได้รับการว่าจ้างจากผู้ฝึกยุทธนิรนามผู้หนึ่งให้ช่วยหาทางที่จะขึ้นไปยังหอฝึกยุทธให้สูงที่สุดเท่าที่พลังของเขาจะทำได้
ให้คุณรับข้อมูลของหอฝึกยุทธและพลังของผู้ฝึกยุทธท่านนั้น แล้วหาว่าเขาสามารถขึ้นไปบนหอได้สูงที่สุดชั้นที่เท่าไรโดยเริ่มนับชั้นล่างสุดเป็นชั้นที่ 1 และไม่มีหอสองชั้นใดที่เชื่อมกันด้วยบันไดมากกว่าหนึ่งอัน
งานของคุณ
รับตัวตัวเลขจำนวนเต็ม K ซึ่งเป็นพลังของผู้ฝึกยุทธ, ตัวเลขจำนวนเต็ม N ซึ่งเป็นจำนวนชั้น ของหอฝึกยุทธ และ ข้อมูลของบันไดในหอแต่ละชั้น ซึ่งเป็นบันไดขึ้นไปยังหอชั้นถัดไป แล้วแสดงผลลัพธ์เป็นชั้นของหอที่สูงที่สุดที่ผู้ฝึกยุทธสามารถขึ้นไปได้
ข้อมูลนำเข้า
บรรทัดแรก ประกอบด้วยตัวเลขจำนวนเต็มสามตัว K, N และ M (1 <= K <= N <= 10,000; 1 <= M <= 100,000) แยกจากกันด้วยช่องว่างหนึ่งช่อง แทนพลังของผู้ฝึกยุทธ์ จำนวนชั้นของหอฝึกยุทธ์ และจำนวนบันไดตามลำดับ
ในอีก M บรรทัดต่อมา ในบรรทัดที่ i+1 จะประกอบด้วยตัวเลขจำนวนเต็มสองตัว ai และ bi (1 <= ai < bi <= N) แทนบันไดที่เชื่อมจากชั้น ที่ ai ไปยังชั้น ที่ bi
ข้อมูลส่งออก
ประกอบด้วยตัวเลขจำนวนเต็มหนึ่งตัว แทนจำนวนชั้นที่สูงที่สุดที่ชาวยุทธที่มีพลังงาน K สามารถขึ้นไปได้
ที่มา: Young Thai Online Programming Competition 2008
ความช่วยเหลือ: ไม่มีคำใบ้สำหรับปัญหานี้
ในการฝ่าแต่ละด่านผู้ฝึกยุทธจะต้องเสียพลังงานไปหนึ่งหน่วยและต้องฝ่าด่านให้ได้ ก่อนถึงจะไปยังชั้น ต่อไปได้ แต่ละชั้นไม่จำเป็นต้องมีบันไดเชื่อมกับชั้นที่ติดกัน บางชั้นอาจจะไม่มีบันไดเลยในขณะที่บางชั้นอาจจะมีบันไดมากกว่าหนึ่งอันก็ได้ และบันไดทุกอันเป็นบันไดพิเศษที่ขึ้นได้ลงไม่ได้ (ตอนขากลับผู้ฝึกยุทธต้องใช้วิชาตัวเบาร่อนลงมายังชั้นล่างสุด)
คุณได้รับการว่าจ้างจากผู้ฝึกยุทธนิรนามผู้หนึ่งให้ช่วยหาทางที่จะขึ้นไปยังหอฝึกยุทธให้สูงที่สุดเท่าที่พลังของเขาจะทำได้
ให้คุณรับข้อมูลของหอฝึกยุทธและพลังของผู้ฝึกยุทธท่านนั้น แล้วหาว่าเขาสามารถขึ้นไปบนหอได้สูงที่สุดชั้นที่เท่าไรโดยเริ่มนับชั้นล่างสุดเป็นชั้นที่ 1 และไม่มีหอสองชั้นใดที่เชื่อมกันด้วยบันไดมากกว่าหนึ่งอัน
งานของคุณ
รับตัวตัวเลขจำนวนเต็ม K ซึ่งเป็นพลังของผู้ฝึกยุทธ, ตัวเลขจำนวนเต็ม N ซึ่งเป็นจำนวนชั้น ของหอฝึกยุทธ และ ข้อมูลของบันไดในหอแต่ละชั้น ซึ่งเป็นบันไดขึ้นไปยังหอชั้นถัดไป แล้วแสดงผลลัพธ์เป็นชั้นของหอที่สูงที่สุดที่ผู้ฝึกยุทธสามารถขึ้นไปได้
ข้อมูลนำเข้า
บรรทัดแรก ประกอบด้วยตัวเลขจำนวนเต็มสามตัว K, N และ M (1 <= K <= N <= 10,000; 1 <= M <= 100,000) แยกจากกันด้วยช่องว่างหนึ่งช่อง แทนพลังของผู้ฝึกยุทธ์ จำนวนชั้นของหอฝึกยุทธ์ และจำนวนบันไดตามลำดับ
ในอีก M บรรทัดต่อมา ในบรรทัดที่ i+1 จะประกอบด้วยตัวเลขจำนวนเต็มสองตัว ai และ bi (1 <= ai < bi <= N) แทนบันไดที่เชื่อมจากชั้น ที่ ai ไปยังชั้น ที่ bi
ข้อมูลส่งออก
ประกอบด้วยตัวเลขจำนวนเต็มหนึ่งตัว แทนจำนวนชั้นที่สูงที่สุดที่ชาวยุทธที่มีพลังงาน K สามารถขึ้นไปได้
ที่มา: Young Thai Online Programming Competition 2008
| ตัวอย่างข้อมูลนำเข้า | ตัวอย่างข้อมูลส่งออก |
| 2 6 5 1 2 1 3 2 5 3 4 5 6 | 5 |
ความช่วยเหลือ: ไม่มีคำใบ้สำหรับปัญหานี้
กำลังออนไลน์: 27 ผู้เยี่ยมชมและ 0 สมาชิก (0 บอท)