href="http://lqdonkh.xyz/viewpr/203">Breaking Sticks (brst.*)

Nguồn: https://www.hackerrank.com/

Đề bài:

Tom nhận được một túi quà có rất nhiều thanh sô-cô-la, Tom muốn ăn hết ngay lập tức tuy nhiên cân nặng đang tăng lên theo ngày làm cho Tom bối rối. Jerry liền đưa ra một ý tưởng để giúp Tom kéo dài thời gian ăn sô-cô-la.

Với mỗi thanh sô-cô-la, Tom có thể ăn hoặc bẻ thành nhiều phần bằng nhau rồi để vào lại trong túi, vì mỗi phần đều phải là số nguyên nên khi bẻ thanh sô-cô-la thành \(d\) phần thì \(d\) phải là ước của độ dài thanh sô-cô-la. Lưu ý nếu độ dài thanh sô-cô-la là 1 thì Tom không thể tiếp tục bẻ mà chỉ có thể ăn nó.

Mỗi lần bẻ hoặc ăn một thanh sô-cô-la được xem là một thao tác. Ví dụ với thanh sô-cô-la có độ dài 4 thì cần 7 thao tác để Tom ăn hết như hình:

Hãy cho biết với một túi có \(n\) thanh sô-cô-la, thanh thứ \(i\) có chiều dài \(a_{i}\) thì Tom cần nhiều nhất bao nhiêu thao tác để ăn hết.

Dữ liệu vào:

+ Dòng đầu tiên ghi số nguyên dương \(n\ (1 \leq n \leq 100)\)

+ Dòng thứ 2 ghi lần lượt các số nguyên dương \(a_{1},a_{2},\ldots,a_{n}(1 \leq a_{i} \leq 10^{12})\)

Kết quả:

+ Một số nguyên duy nhất là kết quả bài toán

Ví dụ: