Tin học trẻ B - TP Đà Nẵng 2023 - Bộ đề bài

#	Bài tập	Điểm	Thời gian:	Giới hạn bộ nhớ
1	Chuẩn hóa (THTB Đà Nẵng 2023)	100 (p)	1.0s	1G
2	Trung bình cộng (THTB Đà Nẵng 2023)	100 (p)	1.0s	1G
3	Bộ ba số (THTB Đà Nẵng 2023)	100 (p)	1.0s	1G
4	Rút tiền (THTB Đà Nẵng 2023)	100 (p)	1.0s	1G

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

Nhập vào một xâu \(s\) là họ tên của một người, hãy chuẩn hóa lại họ tên đó. Xâu họ tên là xâu chuẩn hóa khi thỏa mãn các điều sau:

Không có dấu cách thừa.
Chữ cái đầu mỗi từ viết in hoa còn lại là in thường.

Input

Nhập từ bàn phím một xâu \(s\) là họ tên của một người có độ dài không quá \(255\) kí tự.

Output

In ra màn hình xâu họ tên sau khi được chuẩn hóa.

Example

Test 1

Input

lE  VaN    TEO

Output

Le Van Teo

Test 2

Input

NgUyen vAn Ca

Output

Nguyen Van Ca

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

Cho số nguyên \(n\) và dãy gồm \(n\) số nguyên \(a_1, a_2, \ldots, a_n\). Tìm cách xóa đi tối đa 2 dãy con liên tiếp không cắt nhau của dãy đó để các phần tử còn lại có trung bình cộng lớn nhất.

Input

Đọc từ file văn bản TBCONG.INP gồm:

Dòng đầu tiên chứa số nguyên dương \(n\) \((1 \le n \le 10^6)\) là số phần tử của dãy số.
Dòng thứ hai gồm \(n\) số nguyên \(a_1, a_2, \ldots, a_n\) \((|a_i| \le 10^9)\) là các phần tử của dãy.

Output

Ghi ra file văn bản TBCONG.OUT một số nguyên duy nhất là phần nguyên trung bình cộng của các phần tử còn lại.

Example

Test 1

Input

5
2 5 5 1 3

Output

Note

Xóa đi 2 dãy \([1,1]\) và \([4,5]\).

Scoring

Có \(30\%\) số test với \(n \le 10^2\).
Có \(30\%\) số test tiếp theo với \(n \le 10^3\).
Có \(40\%\) số test còn lại với \(n \le 10^6\).

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

Cho \(n\) số nguyên không âm \(a_1, a_2, ..., a_n\) và một số nguyên dương \(m\). Hãy đếm số bộ ba số \((i, j, k)\) mà \(a_i \cdot a_j \cdot a_k\) chia hết cho \(m\) (lưu ý nếu 2 bộ ba mà bộ này là hoán vị của bộ kia thì vẫn tính là 2 bộ, ví dụ \((1, 2, 3)\) và \((2, 1, 3)\) là hai bộ khác nhau).

Input

Dòng đầu tiên chứa 2 số nguyên \(n\) và \(m\) \((1 \le n \le 2 \cdot 10^3, 1 \le m \le 3 \cdot 10^3)\).
Dòng thứ hai chứa \(n\) số nguyên không âm \(a_1, a_2, ..., a_n\) \((0 \le a_i \le 10^9)\).

Output

Ghi ra một dòng là số bộ ba số thỏa mãn yêu cầu.

Example

Test 1

Input

2 5
1 5

Output

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

Note

Có tất cả 657 bộ ba số thỏa mãn chia hết cho 3.

Scoring

Có 50% số test với \(1 \le n \le 200\).
Có 50% số test còn lại với \(200 < n \le 2 \cdot 10^3\).

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

An có rất nhiều tiền trong ngân hàng Thụy Sĩ, một hôm An cần rút một số tiền \(N\) \((N \leq 10^5)\), ngân hàng chỉ có \(K\) \((K \leq 10^3)\) loại mệnh giá lần lượt là \(A_1, A_2, \ldots, A_K\). Vì lí do đặc biệt nên An mong muốn số tờ tiền rút được là ít nhất.

Input

Dòng thứ nhất chứa 2 số nguyên dương \(N\) và \(K\). Trong đó \(N\) là số tiền cần rút, \(K\) là số loại tiền mệnh giá.
Dòng thứ hai chứa \(K\) số nguyên dương \(A_1, A_2, \ldots, A_K\) lần lượt là mệnh giá của các tờ tiền.

Output

Ghi ra một số nguyên dương duy nhất là số tờ tiền ít nhất mà An rút được, nếu không thể in ra \(-1\).

Example

Test 1

Input

125 6
1 2 5 10 20 50

Output

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

Note

Không có cách nào để từ các tờ tiền mệnh giá 2, 4, 6 tạo thành số tiền là 5 cho nên ta in ra \(-1\).

Scoring

Có \(20\%\) số test có \(K = 2\) và \(A_i\) khác nhau từng đôi một.
Có \(30\%\) số test tiếp theo có \(K \leq 10\), \(N \leq 100\) và \(A_i\) khác nhau từng đôi một.
Có \(50\%\) số test còn lại không có giới hạn gì khác.