Nested Dolls
Xem dạng PDF
Gửi bài giải
Điểm:
0,23 (OI)
Giới hạn thời gian:
1.0s
Giới hạn bộ nhớ:
256M
Input:
stdin
Output:
stdout
Nguồn bài:
Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch
"Dilworth" có một bộ sưu tập các con búp bê Nga. Búp bê với chiều rộng ~w_1~ và chiều cao ~h_1~ sẽ nằm trong được con búp bê chiều rộng ~w_2~ và chiều cao ~h_2~ nếu ~w_1 < w_2~ và ~h_1 < h_2~.
Tính số lớp búp bê bao nhau ít nhất mà có thể tạo ra được từ các búp bê ban đầu.
Input
Dòng đầu là số test ~(1 \le t \le 20)~.
Mỗi test gồm:
- số nguyên ~m (1 \le m \le 20000)~, số lượng búp bê ban đầu.
- Dòng tiếp theo là ~2m~ số nguyên ~w_1, h_1, w_2, h_2, ..., w_m, h_m~, là chiều rộng và chiều cao của con búp bê thứ ~i~ ~(1 \le w_i, h_i \le 10000)~.
Output
Ghi số lớp búp bê bao nhau ít nhất có thể trên một dòng cho từng test.
Sample Input
4
3
20 30 40 50 30 40
4
20 30 10 10 30 20 40 50
3
10 30 20 20 30 10
4
10 10 20 30 40 50 39 51
Sample Output
1
2
3
2
Bình luận
mn giải thích test mẫu vs :((
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.