Độ khó: Khá (3/4 điểm)

Đề thi chọn học sinh giỏi lớp 12 cấp Thành phố – TP. Hồ Chí Minh — Năm học 2023 - 2024 — Bài 1 (6 điểm)

Trong kỳ thi lập trình có ~N~ đội tham dự được đánh số từ ~1~ đến ~N~. Theo quy định của ban tổ chức, số điểm cuối cùng một đội nhận được là hai chỉ số ~(a, b)~ lần lượt là số bài tập đội đó giải được và tổng số điểm phạt của tất cả các bài đã giải. Điểm phạt cho một bài của mỗi đội được tính qua số lần nộp không thành công bài đó. Khi bắt đầu cuộc thi, tất cả các đội có điểm số là ~(0, 0)~.

Xét hai đội ~X_1~ và ~X_2~ lần lượt có điểm số là ~(a_1, b_1)~ và ~(a_2, b_2)~. Đội ~X_1~ được xem là có điểm số tốt hơn đội ~X_2~ khi hoặc ~a_1 > a_2~ hoặc khi ~a_1 = a_2~ và ~b_1 < b_2~. Một đội được xếp hạng ~H~ nếu có ~H-1~ đội có điểm số tốt hơn đội đó. Khi có một đội nộp thành công một bài, ban tổ chức sẽ thông báo cho tất cả các đội biết đội nào đã nộp thành công và điểm phạt cho bài nộp thành công của đội đó. Bạn là thành viên của đội số ~1~ và muốn biết thứ hạng của đội mình mỗi khi có đội nộp thành công.

Yêu cầu: Hãy viết một chương trình cho biết thứ hạng của đội ~1~ mỗi khi có đội nộp bài thành công.

Input

Dữ liệu vào từ bàn phím (stdin). Dòng đầu chứa hai số nguyên ~N, M~ lần lượt cho biết số đội tham dự và số lần một đội nộp bài thành công. Mỗi dòng trong ~M~ dòng tiếp theo chứa hai số nguyên ~T, P~ ~(1 \le T \le N~ và ~1 \le P \le 1000)~ cho biết đội ~T~ đã nộp một bài thành công và có điểm phạt cho bài nộp này là ~P~. Các lần thông báo được cho theo thứ tự thời gian nộp bài tăng dần.

Output

Kết quả in ra màn hình (stdout). In ra màn hình, với mỗi sự kiện nộp bài thành công hãy xuất một số nguyên trên một dòng cho biết thứ hạng của đội ~1~ vào ngay sau thời điểm đó.

Scoring

• ~40\%~ số điểm của bài: ~1 \le N, M \le 100~ và mỗi đội giải thành công tối đa một bài.
• ~80\%~ số điểm của bài: ~1 \le N, M \le 1\,000~.
• ~100\%~ số điểm của bài: ~1 \le N, M \le 100\,000~.

Sample Input

3 5
2 4
3 2
1 3
1 8
2 7

Sample Output

2
3
2
1
1

Notes

Độ khó: Trung bình (2/4 điểm)

Đề thi chọn học sinh giỏi lớp 12 cấp Thành phố – TP. Hồ Chí Minh — Năm học 2023 - 2024 — Bài 2 (7 điểm)

Một băng chuyền có ~N~ khay đựng cam được đánh số liên tiếp từ ~1~ đến ~N~. Mỗi khay chứa hai quả cam, mỗi quả cam được dán nhãn phân loại từ ~1~ đến ~5~. Trong đợt khuyến mãi này, người mua chỉ được chọn mua một loại cam bất kỳ trong một dãy liên tiếp các khay và mỗi khay người mua phải chọn một trong hai quả cam chứa trong khay đó.

Yêu cầu: Cho biết phân loại các quả cam trong ~N~ khay liên tiếp. Hãy viết một chương trình cho biết số lượng quả cam nhiều nhất một khách hàng có thể mua và loại cam tương ứng.

Input

Dữ liệu vào từ bàn phím (stdin). Dòng đầu chứa một số nguyên ~N~. Mỗi dòng trong ~N~ dòng tiếp theo chứa hai số nguyên ~A~ và ~B~ ~(1 \le A, B \le 5)~ cho biết phân loại của ~2~ quả cam trong lần lượt các khay.

Output

Kết quả in ra màn hình (stdout). In ra màn hình hai số nguyên lần lượt cho biết số lượng quả cam nhiều nhất một khách hàng có thể mua và loại cam tương ứng. Trong trường hợp có nhiều kết quả giống nhau hãy xuất ra kết quả ứng với loại cam nhỏ nhất.

Scoring

• ~40\%~ số điểm của bài: ~N \le 100~
• ~80\%~ số điểm của bài: ~N \le 10\,000~
• ~100\%~ số điểm của bài: ~N \le 100\,000~

Sample Input 1

2
1 2
3 1

Sample Output 1

2 1

Sample Input 2

3
1 2
2 3
4 3

Sample Output 2

2 2

Độ khó: Khá (3/4 điểm)

Đề thi chọn học sinh giỏi lớp 12 cấp Thành phố – TP. Hồ Chí Minh — Năm học 2023 - 2024 — Bài 3 (7 điểm)

Trò chơi rút ván thiết kế trên một vùng hình chữ nhật được bao bởi hai đoạn thẳng có độ dài là ~A~ và hai đoạn thẳng có độ dài là ~B~. Ta có thể xem hai điểm góc chéo nhau của vùng chơi có tọa độ là ~(0; 0)~ và ~(A; B)~, ~1 \le A, B \le 10^9~. Có ~N~ thanh dọc có độ dài ~B~, một đầu của thanh dọc thứ ~i~ được đặt tại điểm có tọa độ ~(a_i; 0)~, đầu còn lại nằm trên điểm ~(a_i; B)~, ~0 < a_i < A~. Có ~M~ thanh ngang có độ dài ~A~, một đầu của thanh ngang thứ ~j~ được đặt tại điểm có tọa độ ~(0; b_j)~, đầu còn lại nằm trên điểm ~(A; b_j)~, ~0 < b_j < B~. Cách bố trí các thanh dọc, ngang như trên chia hình chữ nhật ban đầu thành ~(N+1)(M+1)~ khu vực khép kín.

Tại những điểm giao nhau, ta cắt thanh dọc và thanh ngang để tạo ra những đoạn nhỏ hơn. Nhiệm vụ của người chơi là cần bỏ đi các đoạn sao cho tất cả khu vực trong vùng chơi thông với nhau và tổng độ dài các đoạn bỏ đi là ít nhất. Có thể hiểu rằng khi tất cả khu vực thông nhau thì trong vùng chơi từ một khu vực ta có thể di chuyển đến một khu vực bất kỳ.

Hình minh họa ví dụ bên dưới: cần bỏ các đoạn nét đứt để các khu vực thông nhau.

Yêu cầu: Hãy viết một chương trình cho biết tổng độ dài ít nhất các đoạn cần bỏ đi để tất cả khu vực trong vùng chơi thông nhau.

Input

Dữ liệu vào từ bàn phím (stdin). Dòng đầu chứa ~4~ số nguyên ~A, B, N, M~. Mỗi dòng trong ~N~ dòng tiếp theo chứa một số nguyên lần lượt là vị trí của các thanh dọc ~a_1, a_2, \ldots, a_N~. Mỗi dòng trong ~M~ dòng tiếp theo chứa một số nguyên lần lượt là vị trí của các thanh ngang ~b_1, b_2, \ldots, b_M~.

Output

Kết quả in ra màn hình (stdout). In ra màn hình một số nguyên cho biết tổng độ dài ít nhất các đoạn cần bỏ đi để tất cả các khu vực trong vùng chơi thông nhau.

Scoring

• ~30\%~ số điểm của bài: ~0 \le N, M \le 3~
• ~60\%~ số điểm của bài: ~0 \le N, M \le 1\,000~
• ~100\%~ số điểm của bài: ~0 \le N, M \le 25\,000~

Sample Input

5 5 2 2
1
3
3
4

Sample Output

10