2025 THT bảng B - Buổi 2

Bộ đề bài

Trở lại kỳ thi

1. Chuẩn hóa (THTB Đà Nẵng 2023)

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

Link đề: https://drive.google.com/file/d/1QPeBId9VmQ_LkWuAqpmqdSbKEpEBCvL2/view

Test 1

Input 
lE  VaN    TEO
Output 
Le Van Teo

Test 2

Input
Output

2. Trung bình cộng (THTB Đà Nẵng 2023)

Điểm: 100 (p) Thời gian: 1.0s Bộ nhớ: 1G Input: TBCONG.INP Output: TBCONG.OUT

Test 1

Input 
5
2 5 5 1 3
Output 
5
Note

Xóa đi 2 đoạn [1,1] và [4,5]

Test 2

Input
Output

3. Bộ ba số (THTB Đà Nẵng 2023)

Điểm: 100 (p) Thời gian: 1.0s Bộ nhớ: 1G Input: BOBASO.INP Output: BOBASO.OUT

Test 1

Input 
2 5
1 5
Output 
7
Note

Có 7 bộ ba là \((1,1,5);(1,5,1);(1,5,5);(5,1,1);(5,1,5),(5,5,1),(5,5,5)\)

Test 2

Input 
10 3
1 2 3 4 5 6 7 8 9 10
Output 
657

4. Rút tiền (THTB Đà Nẵng 2023)

Điểm: 100 (p) Thời gian: 1.0s Bộ nhớ: 1G Input: TIEN.INP Output: TIEN.OUT

Test 1

Input 
125 6
1 2 5 10 20 50
Output 
4
Note

Số tờ tiền ít nhất có thể lấy là 4 tờ gồm 2 tờ mệnh giá 50, 1 tờ mệnh giá 20, 1 tờ mệnh giá 5.

Test 2

Input 
5 3
2 4 6
Output 
-1

5. Bài toán hủ kẹo dẻo

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

Có \(N\) hủ kẹo dẻo được đặt trên một hàng. Ban đầu, hủ thứ \(i\) có độ ngọt là \(a_i\).

\(Kaninho\) cố gắng kết hợp tất cả các hủ kẹo này thành một hủ kẹo lớn hơn. Anh ấy thực hiện phép toán dưới đây nhiều lần cho đến khi chỉ còn một hủ kẹo duy nhất thì dừng:

  • Chọn \(2\) hủ kẹo kề nhau bất kì và kết hợp chúng lại thành một hủ kẹo. Hủ kẹo mới này có độ ngọt là \(x+y\), trong đó \(x,y\) lần lượt là độ ngọt của hai hủ kẹo trước đó. Và việc này tốn chi phí là \(x+y\). Mối quan hệ về vị trí giữa các hủ kẹo vẫn không thay đổi khi ta kết hợp chúng lại với nhau.

Input

  • Dòng thứ nhất chứa số nguyên \(N(2\le N\le 400)\)

  • Dòng thứ hai chứa \(N\) số nguyên \(a_i(1\le a_i\le 10^9)\).

Output

  • In ra chi phí tối thiểu để kết hợp tất cả các hủ kẹo trên thành \(1\) hủ duy nhất.

Example

Test 1

Input 
4
10 20 30 40
Output 
190
Note

  • \(Kaninho\) sẽ là như sau:

  • \((10,20,30,40)\rightarrow (30,30,40)\) (Tốn chi phí: 10+20=30)

  • \((30,30,40)\rightarrow (60,40)\) (Tốn chi phí: 30+30=60)

  • \((60,40)\rightarrow (100)\) (Tốn chi phí: 60+40=100)

Vậy tổng chỉ phí tối thiểu cần dùng là \(30+60+100=190\)