Lịch Nghi Lễ · canuc80k7707 · Thuật toán Canuc80k

Có $N$ sự kiện trong cùng một ngày. Sự kiện $i$ diễn ra từ $S_{i}$ đến $T_{i}$ và cần một nghi lễ dài $D_{i}$ phút. Nghi lễ phải nằm ngay đầu sự kiện, tức $[S_{i}, S_{i} + D_{i})$ , hoặc ngay cuối sự kiện, tức $[T_{i} - D_{i}, T_{i})$ . Hãy chọn một trong hai khoảng cho mỗi sự kiện sao cho không có hai nghi lễ chồng lấn. Các khoảng là nửa mở, vì vậy một khoảng có thể bắt đầu đúng lúc khoảng khác kết thúc.

Input

Dòng đầu chứa số nguyên $N$ .
Mỗi trong $N$ dòng tiếp theo chứa $S_{i}, T_{i}, D_{i}$ . Hai thời điểm dùng định dạng hh:mm; $D_{i}$ tính bằng phút.

Output

Nếu không thể xếp đủ nghi lễ, in NO.
Nếu có thể, in YES, sau đó in $N$ dòng. Dòng thứ $i$ chứa thời điểm bắt đầu và kết thúc của nghi lễ đã chọn cho sự kiện $i$ , theo dạng hh:mm.

Constraints

$1 \leq N \leq 1000.$
$S_{i}$ và $T_{i}$ là thời điểm hợp lệ trong cùng một ngày, $00$ : $00 \leq S_{i} < T_{i} \leq 23$ : $59$ .
$1 \leq D_{i} \leq T_{i} - S_{i}$ tính theo phút.

Scoring

Subtask $1$ ( $50%$ số điểm): $N \leq 16$ .
Subtask $2$ ( $50%$ số điểm): Không có giới hạn bổ sung.

Example

Test 1

Input

3
08:00 08:20 20
08:10 09:00 20
09:10 09:30 20

Output

YES
08:00 08:20
08:40 09:00
09:10 09:30

Giải thích: Sự kiện $1$ và $3$ có khoảng cố định. Sự kiện $2$ không thể chọn $08$ : $10$ - $08$ : $30$ vì chồng với sự kiện $1$ , nên phải chọn $08$ : $40$ - $09$ : $00$ .

Test 2

Input

2
08:00 08:30 30
08:10 08:40 30

Output

NO

Giải thích: Mỗi sự kiện chỉ có một khoảng dài $30$ phút và hai khoảng này chồng nhau, nên không có lịch hợp lệ.

Phân tích: Mỗi đối tượng có đúng hai lựa chọn, nên ta biểu diễn bằng một biến Boolean. Gọi biến của sự kiện i cho biết chọn khoảng đầu hay khoảng cuối. Với mỗi cặp lựa chọn chồng lấn, ta cấm đồng thời chọn cả hai.
Phân tích: Mỗi cấm đoán “không được đồng thời chọn A và B” tương đương clause (NOT A OR NOT B). Các quan hệ bằng nhau hoặc khác nhau cũng viết được bằng hai clause. Với clause (P OR Q), thêm hai cung kéo theo NOT P -> Q và NOT Q -> P.
Thuật toán: 1. Tạo hai đỉnh literal cho mỗi biến. 2. Chuyển từng quan hệ của đề thành các clause hai literal và thêm cung kéo theo. 3. Tìm các thành phần liên thông mạnh bằng hai lượt DFS lặp. 4. Nếu một biến và phủ định của nó nằm cùng SCC, hệ vô nghiệm. Ngược lại, thứ tự SCC cho một phép gán hợp lệ. 5. Từ phép gán, in đúng khoảng đầu hoặc cuối đã chọn cho từng sự kiện; nếu mâu thuẫn SCC thì in NO.
Chứng minh đúng: Mỗi clause được thêm là tương đương chính xác với một quan hệ hoặc một cặp lựa chọn bị cấm trong đề. Vì vậy, một phép gán thỏa công thức 2-CNF khi và chỉ khi các lựa chọn tương ứng thỏa toàn bộ yêu cầu gốc. Tiêu chuẩn SCC của 2-SAT phát hiện vô nghiệm đúng khi một literal và phủ định của nó kéo theo lẫn nhau. Khi không có cặp như vậy, phép gán theo thứ tự SCC thỏa mọi cung kéo theo, do đó thỏa mọi clause. Bởi vậy thuật toán báo đúng tính khả thi và mọi chứng nhận được in đều hợp lệ.
Độ phức tạp: O(N^2) thời gian để xét mọi cặp lựa chọn và O(N^2) bộ nhớ trong trường hợp xấu nhất.