Bỏ qua đến nội dung

Hướng giải: SURAJ

SURAJ

Mã bài: free026 Nhóm: Uncategorized Điểm: 100 điểm
Giới hạn
1,0 s, 256 MB
Tỉ lệ AC
11,4%
Người giải
4
Chỉ đọc hướng giải khi bế tắc và đừng sao chép mã trong đó. Hãy tôn trọng người ra đề và người viết hướng giải: nộp lời giải chính thức khi chưa tự giải được bài có thể khiến bạn bị khóa tài khoản.

Nguồn: Free Contest

Trước tiên ta cần tìm số n lớn nhất sao cho cả k cửa sổ đều mở n tab mà không vượt quá bộ nhớ. Tổng bộ nhớ đã được sử dụng là:

\displaystyle S = k(1 + 2 + 3 + ... + n) = k\frac{n(n + 1)}{2}

Dùng tìm kiếm nhị phân ta tìm được số n, sau đó lấy phần dư còn lại của bộ nhớ và chia lấy nguyên cho n + 1. Kết quả cuối cùng là:

\displaystyle nk + \left\lfloor\frac{m - S}{n + 1}\right\rfloor

Độ phức tạp: O(Tlog(m)).

Bình luận