Kiểm tra lịch giao việc

Bối cảnh

Một nhóm có n công việc độc lập, mỗi công việc được mô tả bởi (deadline, duration). Hệ thống lập một lịch tham chiếu bằng cách sắp công việc theo deadline tăng dần; nếu deadline bằng nhau, công việc có duration nhỏ hơn làm trước. Sau khi có lịch, cần kiểm tra thời điểm hoàn thành tích lũy. Nếu ở rank k, tổng duration của các công việc 1..k lớn hơn deadline của công việc k, lịch bắt đầu vi phạm tại đó.

Bài không yêu cầu tìm lịch tối ưu hay chọn bỏ công việc; chỉ phân tích một policy được định nghĩa sẵn. Comparator quyết định thứ tự, prefix duration mô tả thời gian hoàn thành. Đây là Homework Medium vì một lỗi state phổ biến là build prefix trước sort hoặc kiểm tra deadline theo record cũ, dẫn đến kết quả sai dù code từng phần có vẻ đúng.

Yêu cầu

1. Đọc n cặp deadline duration.
2. Sort deadline tăng; tie duration tăng.
3. Build prefix duration theo thứ tự đã sort.
4. Tìm rank 1-based đầu tiên có prefix > deadline.
5. Nếu không có, in OK; nếu có in VIOLATION rank completion deadline.

Input

Dòng 1 n; n dòng deadline duration.

Output

OK hoặc một dòng VIOLATION rank completion deadline.

Ràng buộc

1≤n≤5000, 0≤deadline,duration≤10^9.

Ví dụ 1

Input

4
5 2
10 3
7 2
20 5

Output

OK

Giải thích

Sau sort theo deadline, thứ tự là (5,2),(7,2),(10,3),(20,5). Completion lần lượt 2≤5, 4≤7, 7≤10, 12≤20 nên không rank nào vi phạm và output là OK. Prefix phải được tính trên đúng thứ tự sau comparator.

Ví dụ 2

Input

3
2 2
3 2
10 1

Output

VIOLATION 2 4 3

Giải thích

Sort cho thứ tự (2,2),(3,2),(10,1). Sau job 1, completion=2 đúng deadline 2. Sau job 2, completion=4 nhưng deadline chỉ 3, nên đây là vi phạm đầu tiên. Chương trình dừng và in VIOLATION 2 4 3.

Thông tin học tập

• Module: M05
• Buổi: B17
• Loại bài: HOMEWORK
• Độ khó: Medium
• Concepts: pair, custom comparator, prefix sum, schedule validation, first violation
• Giới hạn kiến thức: B01-B17
• Time limit: 1 second(s)
• Memory limit: 256 MB
• Point: 100