Kirito và những con rồng

Submit solution
Points: 2 (partial)
Time limit: 1.0s
Memory limit: 98M
Author:
kai
Problem type
Allowed languages
Ada, Assembly, Awk, C, C++, C11, CLANG, CLANGX, Classical, COBOL, Coffee, CSC, D lang, DART, F95, FORTH, Fortrn, GAS32, GO, Haskell, Itercal, Java, kotlin, LEAN, LISP, LUA, MONOVB, Nasm, OCAML, Pascal, Perl, php, PIKE, prolog, Pypy, Python, Ruby 2, RUST, Scala, SCM, SED, SWIFT, TCL, TUR, V8JS, VB, ZIG

Kirito đang bị mắc kẹt ở tầng 10 của một trò chơi tên là S.A.O. Để leo lên được các tầng tiếp theo, anh ấy phải đánh bại tất cả n con rồng sống ở tầng này. Kirito và những con rồng có sức mạnh, được biểu thị bằng một số nguyên. Trong cuộc đọ sức giữa hai đối thủ, kết quả của cuộc đọ sức được quyết định bởi sức mạnh của họ. Ban đầu, sức mạnh của Kirito bằng s.

Nếu Kirito bắt đầu đấu tay đôi với rồng thứ i (1 ≤ i ≤ n) và sức mạnh của Kirito không lớn hơn sức mạnh của rồng xi, thì Kirito thua trận đấu và chết. Nhưng nếu sức mạnh của Kirito lớn hơn sức mạnh của con rồng, thì anh ta sẽ đánh bại con rồng và được tăng thêm sức mạnh theo yi.

Kirito có thể chiến đấu với những con rồng theo bất kỳ thứ tự nào. Xác định xem liệu anh ta có thể chuyển sang tầng tiếp theo của trò chơi hay không, tức là đánh bại tất cả những con rồng mà không bị thua một lần nào.

Input:

  • Dòng đầu tiên chứa hai số nguyên được phân tách bằng dấu cách s và n (1 ≤ s ≤ 10^4, 1 ≤ n ≤ 10^3). Sau đó n dòng tiếp theo: dòng thứ i chứa các số nguyên được phân tách bằng dấu cách là xi và yi (1 ≤ xi ≤ 10^4, 0 ≤ yi ≤ 10^4) - sức mạnh của con rồng thứ i và sức mạnh được thưởng khi đánh bại nó.

Output:

  • Một dòng duy nhất là kết quả của cuộc chiến. In ra ''YES'' nếu Kirito có thể leo lên tầng tiếp theo và ngược lại in ra ''No''

Example 1:

Input 1:

2 2
1 99
100 0

Output 1:

YES

Input 2:

10 1
100 100

Output 2:

NO

Comments


  • 0
    ga123  commented on Sept. 4, 2021, 5:11 a.m.

    Nếu không làm được thì đọc

    Đây là dạng bài tập sanity check điển hình, nhắc nhở lại về vấn đề xử lý điều kiện vòng lặp hợp lý , không bị lặp vô hạn. Giống như bài toán ốc sên, chúng ta xem xét về điều kiện thành công và điều kiện thất bại.

    • kirito có chỉ số khởi tạo là a, nếu a to hơn sức mạnh của rồng, thì kirito thắng và nhận được số điểm tương ứng của rồng.
    • việc kirito thắng hay bại được quyết định trước khi đánh rồng.
    • việc kirito được nhân điểm hay không được quyết định sau khi đánh rồng.
    • trong trường hợp kirito đã đi toàn bộ rồng và không có 1 cơ hội thắng nào, chỉ số của anh ấy là không đổi.

    Sau khi đã xem xết toàn bộ điều kiện trên, ta rút ra thuật toán sau:

    • kirito sẽ đi xung quanh toàn bộ tầng
    • anh ấy sẽ đánh con rồng nào yếu hơn, không cần biết đã đi qua bao nhiêu lần.
    • kirito phải đánh bại được rồng mạnh nhất để thành công.
    • nếu muốn thành công, thì sức mạnh mới của kirito phải tăng sau mỗi lần đi hết tầng.

    vòng lặp sẽ được xây dựng trên đúng quy tắc trên:

    sức mạnh lúc bắt đầu
(while kirito < rồng mạnh nhất )
{
for(i=1;i< số rồng;i++)//đi xung quanh tầng
{
if(kirito > rồng thứ i)
 {
kirito += rồng mạnh nhất;
 }
}
sức mạnh lúc bắt đầu = kirito;
//sanity check để đảm bảo không lặp vô hạn.
//sức mạnh mới bây giờ trở thành sức mạnh của kirito sau khi đã đi hết tầng
if( sức mạnh lúc bắt đầu == kirito )//sức mạnh không tăng sau khi đi hết tầng
{
cout<<"NO";// kirito chắc chắn đã thất bại
break;//kết thúc lặp
}
}
if(kirito>rồng mạnh nhất)
cout<<""YES"; vì kirito thoát được vòng lặp và mạnh hơn toàn bộ rồng.