Tí có một bộ đồ chơi gồm khối hộp được đánh số từ đến . Khối hộp thứ là một hình hộp chữ nhật có kích thước ( là mặt đáy, chiều cao luôn là ). Tí muốn dùng các khối hộp trong bộ đồ chơi của mình để xếp thành một tháp hộp cao nhất có thể, thỏa mãn các điều kiện:
Các khối tiếp xúc nhau theo mặt đáy;
Nếu khối dưới có mặt đáy là và khối trên có mặt đáy là thì và .
Yêu cầu: Cho biết và kích thước các khối hộp, hãy giúp Tí tính chiều cao lớn nhất của tháp hộp xếp được.
Dữ liệu vào:
Dòng đầu chứa số nguyên dương ;
Dòng thứ trong số dòng tiếp theo chứa hai số nguyên dương được ghi cách nhau một dấu cách.
Dữ liệu ra:
Ghi ra một số nguyên duy nhất là chiều cao lớn nhất của tháp hộp xếp được.
Ví dụ:
Dữ liệu vào:
3
3 2
3 3
4 3
Dữ liệu ra:
2
Giải thích:
Xếp khối hộp thứ nhất chồng lên khối hộp thứ ba ta được tháp hộp có chiều cao bằng .
Giới hạn:
40% số điểm của bài có 1<=n<=20;
30% số điểm khác có 20<=n<=1000;
10% số điểm còn lại có 1000<=n<=100000.
Nguồn: ĐỀ THI CHỌN HỌC SINH GIỎI THPT CẤP TỈNH - NĂM HỌC 2019 – 2020
