LQDOJ Contest #8 - Tạm biệt năm Quý Mão

_minhduc là một cậu học sinh lớp \(1\). Tết năm nay _minhduc được rất nhiều người lì xì, cậu ấy biết rằng các mệnh giá cậu ấy nhận được là các tờ \(100.000\) VND, \(200.000\) VND, và \(500.000\) VND.

_minhduc muốn đếm số bao lì xì của lần lượt các mệnh giá trên để tính tổng số tiền mà cậu ấy đã nhận được, nhưng số tiền quá lớn và số bao lì xì quá nhiều nên cậu ấy không thể đếm hết được.

Yêu cầu: Bạn hãy giúp _minhduc đếm tổng số tiền lì xì năm nay cậu ấy nhận được. Biết rằng cậu ấy có \(a\) bao có mệnh giá \(100.000\) VND, \(b\) bao có mệnh giá \(200.000\) VND, và \(c\) bao có mệnh giá \(500.000\) VND.

Input

• Chứa ba số nguyên dương lần lượt là \(a,b,c\) \((1 \le a,b,c \le 10^{9})\).

Output

• In ra kết quả bài toán sau khi thực hiện yêu cầu đề bài.

Example

1 2 3

2000000

Phường LQDOJ Có \(N\) gia đình sinh sống. Nhà thứ \(i\) có tọa độ là \(x_i\).

Chủ tịch UBND phường quyết định tổ chức lễ tất niên cuối năm và tất cả các gia đình đều phải tham gia lễ tất niên này. Lễ tất niên này có thể tổ chức tại một ngôi nhà \(m\) bất kì (\(m\) phải là số nguyên), nhà thứ \(i\) cần phải trả \((x_i - m)^2\) đồng.

Yêu cầu: Bạn hãy lập trình tính tổng số tiền ít nhất có thể mà tất cả các nhà phải trả.

Input

• Dòng đầu tiên chứa số nguyên dương \(N\) \((1 \le N \le 10^6)\).
• Dòng tiếp theo chứa \(N\) số nguyên dương \(x_1,x_2,...,x_N\) \((1 \le x_i \le 10^6)\).

Output

• In ra kết quả bài toán sau khi thực hiện yêu cầu đề bài.

Scoring

• Subtask \(1\) (\(50\%\) số điểm): Có \(N \le 5000\).

• Subtask \(2\) (\(50\%\) số điểm): Không có ràng buộc gì thêm.

Example

3
1 2 3

2

shiba - bạn thân của _minhduc trong khi làm bài tập tết để vào ngày mùng tết cậu ấy có thể đi chơi thoải mái thì gặp một bài từ rất khó từ thầy giáo: Cho một số nguyên dương \(N\). Một dãy được gọi là dãy đẹp khi dãy đó là hoán vị của các số từ \(1\) đến \(N\) và dãy đó thỏa mãn rằng có ít nhất một cặp số liền kề trong dãy đó có dạng \((x,x+1)\). Ví dụ với \(N = 4\) thì các dãy \((1,2,4,3)\) và \((3,4,1,2)\) là các dãy đẹp, còn các dãy \((3,1,4,2)\) và \((4,3,2,1)\) thì không phải. shiba cần đếm số dãy đẹp khác nhau có thể tạo ra khi biết trước số nguyên dương \(N\).

Bài này khó đến nổi shiba không làm được. Cậu ấy chợt nhớ nhớ ra rằng _minhduc rất thông thạo về dãy hoán vị nên shiba đã hỏi bài bạn thân của mình. Nhưng _minhduc đang bận chơi game "bình nguyên vô tận" với bạn gái nên không thể chỉ bài cho shiba được vì sợ nếu bỏ trận đấu giữa chừng thì bạn gái của mình sẽ giận. Vì vậy _minhduc nhờ các bạn tài giỏi trong LQDOJ giải quyết bài toán này cho shiba ~rồi _minhduc sẽ lì xì cho các bạn :Đ~

Yêu cầu: Bạn hãy viết chương trình giải quyết bài toán trên sau khi chia lấy dư cho \(M\) với \(M\) là một số nguyên dương được nhập từ bàn phím.

Input

• Chứa hai số nguyên dương lần lượt là \(N\) và \(M\) \((1 \le N \le 10^{18}, 2 \le M \le 10^7)\).

Output

• In ra kết quả bài toán sau khi chia lấy dư cho \(M\).

Scoring

• Subtask \(1\) (\(10\%\) số điểm): Có \(N \le 10\).

• Subtask \(2\) (\(20\%\) số điểm): Có \(N \le 15\).

• Subtask \(3\) (\(20\%\) số điểm): Có \(N \le 20\).

• Subtask \(4\) (\(30\%\) số điểm): Có \(N \le 10^6\).

• Subtask \(5\) (\(20\%\) số điểm): Không có ràng buộc gì thêm.

Example

4 100

13

Thành phố A nổi tiếng với nhiều danh lam thắng cảnh, hiện thành phố có \(n\) điểm du lịch được đánh số từ \(1\) đến \(n\), các điểm được nối với nhau bởi \(n -1\) con đường \(2\) chiều, các điểm liên thông với nhau, nghĩa là luôn có đường đi giữa \(2\) thành điểm bất kì trong thành phố. Thành phố A hiện tại thành phố bắt đầu cho thuê các địa điểm du lịch này. Có \(m\) đoàn du lịch, đoàn thứ \(i\) muốn thuê các điểm du lịch trên đường đi ngắn nhất từ \(u_i\) đến \(v_i\) với giá là \(c_i\). Vì muốn nâng cao chất lượng kinh tế, chủ tịch thành phố quyết định cho các đoàn du lịch thuê các địa điểm, nhưng vì quá bận nên chủ tịch nhờ bạn chọn các đoàn du lịch sao cho lợi nhuận thu về là lớn nhất thỏa mãn điều kiện là ở \(1\) điểm bất kì chỉ được thuê bởi nhiều nhất \(1\) đoàn du lịch.

Input:

• Dòng thứ nhất chứa \(2\) số nguyên dương \(n\) và \(m\) (\(1 \le n, m \le 10^5\)).
• \(n - 1\) dòng tiếp theo lần lượt là \(2\) số \(u\) và \(v\) biểu thị có đường đi giữa \(u\) và \(v\) .
• \(m\) dòng tiếp theo là lần lượt là các số \(u_i, v_i, c_i\) (\(1 \le u_i, v_i \le n\), \(1 \le c_i \le 10 ^5\)).

Output:

• Gồm một số duy nhất là lợi nhuận lớn nhất có thể nhận được.

Scoring

• Subtask \(1\) (\(20\%\) số điểm): Có \(1 \le n, m \le 300\).
• Subtask \(2\) (\(80\%\) số điểm): Không có ràng buộc gì thêm.

Example

5 6
1 2
2 3
3 4
4 5
1 5 59535
2 3 9850
1 2 13264
1 4 46643
2 4 17545
4 5 97294

110558

Cho ba số tự nhiên \(n,a,b\). Ta sẽ định nghĩa cặp \((x,y)\) là cặp số đẹp nếu thỏa mãn tất cả các điều kiện như sau:

• \(1 \le x \le a\).
• \(1 \le y \le b\).
• \((x \times y)\) chia hết cho \((x+y)\) và phép chia đó có kết quả không vượt quá \(n\).
• \(x\) và \(y\) là hai số tự nhiên.

Yêu cầu: Bạn hãy đếm số cặp \((x,y)\) thỏa mãn yêu cầu đề bài là cặp số đẹp.

Input

• Chứa ba số tự nhiên lần lượt là \(n,a,b\) \((1 \le n,a,b \le 10^{10})\).

• Dữ liệu luôn đảm bảo rằng kết quả bài toán không vượt quá \(10^{18}\).

Output

• In ra kết quả bài toán sau khi thực hiện yêu cầu đề bài.

Scoring

• Subtask \(1\) (\(10\%\) số điểm): Có \(n,a,b \le 2 \times 10^4\).

• Subtask \(2\) (\(20\%\) số điểm): Có \(n,a,b \le 2.5 \times 10^7\).

• Subtask \(3\) (\(10\%\) số điểm): Có \(n,a,b \le 2.5 \times 10^8\).

• Subtask \(4\) (\(10\%\) số điểm): Có \(n,a,b \le 2 \times 10^9\).

• Subtask \(5\) (\(20\%\) số điểm): Có \(n = 10^{10}\) và \(a = b\).

• Subtask \(6\) (\(10\%\) số điểm): Có \(n = 10^{10}\).

• Subtask \(7\) (\(20\%\) số điểm): Không có ràng buộc gì thêm.

Example

6 12 18

14