Steve tham gia rất nhiều kỳ thi, lớp ngoại khóa khác nhau và có đủ các
loại chứng chỉ. Các chứng chỉ này được kẹp lưu trữ ở các tập khác nhau không
theo một quy tắc nào cả. Cũng may là bên ngoài tập còn ghi số lượng chứng chỉ kẹp
trong đó.
Hôm nay Steve cần đi ra văn phòng công chứng sao lại chứng chỉ kết quả
thi Tin học Quốc gia để làm hồ sơ xin được tuyển thẳng vào khoa Công nghệ thông
tin. Steve chỉ có một chứng chỉ này. Bạn ấy muốn tìm tập chứa chứa chứng chỉ
đang cần, mang ra nơi công chứng và trong thời gian xếp hàng chờ đợi sẽ tìm và
lấy nó ra để sao. Việc mở một tập kẹp chứng chỉ mất 1 giây, xem xét một chứng
chỉ có phải là cái mình đang tìm hay không cũng mất 1 giây. Dĩ nhiên Steve
không tìm ở các tập có ghi số lượng là 0. Việc chuyển từ tập này sang tập khác
là không đáng kể.
Yêu cầu: Cho n – số tập lưu chứng chỉ và các số ai
– số chứng chỉ lưu trong tập i ( 0 ≤ ai ≤ 106,
1 ≤ n
≤ 106, i = 1 ÷ n). Hãy xác định, trong trường hợp xấu
nhất, Steve cần ít nhất bao nhiêu thời
gian để tìm ra tập cần thiết.
Dữ liệu: Vào từ file văn bản CERTIF.INP:
+ Dòng đầu tiên chứa số
nguyên n,
+ Dòng thứ 2 chứa n
số nguyên a1, a2, . . ., an.
Kết quả: Đưa ra file văn bản CERTIF.OUT một số nguyên – thời gian cần để tìm.
Ví dụ:
