HSG 9 Hà Tĩnh 2025

Bộ đề bài

Trở lại kỳ thi
# Bài tập Điểm Thời gian: Giới hạn bộ nhớ
1 Số nguyên dương K 100 (p) 1.0s 256M
2 Nuôi cá cảnh 100 (p) 1.0s 256M
3 Số nguyên tố 100 (p) 1.0s 256M
4 Dãy con 100 (p) 1.0s 256M

1. Số nguyên dương K

Điểm: 100 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

2. Nuôi cá cảnh

Điểm: 100 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

BigZero có một bể cá với đàn cá nhiều màu sắc. Hằng ngày sau những giờ học bài, cậu thường ngồi ngắm đàn cá và cho chúng ăn. Thức ăn của cá được đựng trong các gói đóng sẵn. Mỗi ngày đàn cá ăn hết đúng 3 gói, giá bán thức ăn thường xuyên biến động. Cửa hàng cho biết trước giá bán trong \(n\) ngày lần lượt là \(a_1, a_2, ..., a_n\), mỗi ngày được mua nhiều gói với giá bán của ngày đó, thức ăn thừa có thể được dùng cho các ngày tiếp theo. BigZero đang lên kế hoạch để mua thức ăn cho đàn cá trong \(n\) ngày sao cho tiết kiệm nhất.

Input

  • Dòng đầu tiên chứa một số nguyên dương \(n\) \((1 \leq n \leq 10^6)\)
  • Dòng thứ hai chứa \(n\) số nguyên dương \(a_1, a_2, ..., a_n\) \((1 \leq i \leq n; a_i \leq 10^9)\) trong đó \(a_i\) là giá bán một gói thức ăn trong ngày thứ \(i\)

Output

  • Ghi ra một số nguyên duy nhất là số tiền tối thiểu để mua thức ăn cho đàn cá trong \(n\) ngày.

Scoring

  • \(30\%\) số test ứng với \(30\%\) số điểm của bài thoả mãn: \(a_1 \leq a_2 \leq ... \leq a_n\)
  • \(30\%\) số test khác ứng với \(30\%\) số điểm của bài thoả mãn: \(a_1 \geq a_2 \geq ... \geq a_n\)
  • \(40\%\) số test còn lại ứng với \(40\%\) số điểm của bài không có ràng buộc gì thêm

Example

Test 1

Input 
3
2 3 5
Output 
18
Note

Kế hoạch mua thức ăn là: ngày 1 mua 9 gói với giá là 2, ngày 2, 3 không mua gói nào.
Số tiền tối thiểu để mua thức ăn là: \(9 \cdot 2 + 0 \cdot 3 + 0 \cdot 5 = 18\)

Test 2

Input 
3
5 3 2
Output 
30
Note

Kế hoạch mua thức ăn là: ngày 1 mua 3 gói với giá là 5, ngày 2 mua 3 gói với giá là 3, ngày 3 mua 3 gói với giá là 2.
Số tiền tối thiểu để mua thức ăn là: \(3 \cdot 5 + 3 \cdot 3 + 3 \cdot 2 = 30\)

Test 3

Input 
3
5 2 3
Output 
27
Note

Kế hoạch mua thức ăn là: ngày 1 mua 3 gói với giá là 5, ngày 2 mua 6 gói với giá là 2, ngày 3 không mua gói nào.
Số tiền tối thiểu để mua thức ăn là: \(3 \cdot 5 + 6 \cdot 2 + 0 \cdot 3 = 27\)

3. Số nguyên tố

Điểm: 100 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình


4. Dãy con

Điểm: 100 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình