🎁 Doraemon contest #01

Cho một dãy số nguyên dương gồm \(n\) phần tử: \(a_1, a_2, \dots, a_n\). Một phần tử \(a_i\) được gọi là đặc biệt nếu tồn tại một phần tử khác \(a_j\) \((i \ne j)\) sao cho \(a_i + a_j\) là một số chính phương.

Yêu cầu

Đếm số lượng phần tử đặc biệt trong dãy.

Input

• Dòng 1: Gồm một số nguyên \(n\).
• Dòng 2: Gồm \(n\) số nguyên \(a_1, a_2, \dots, a_n\).

Output

• In ra một số nguyên duy nhất là số lượng phần tử đặc biệt tìm được.

Constraints

• \(1 \le n \le 2 \cdot 10^5\)
• \(0 \le a_i \le 10^6\)

Example

5
1 3 5 6 10

4

Scoring

• Subtask \(1\) (\(50\%\) số điểm): \(n \le 4000\).
• Subtask \(2\) (\(50\%\) số điểm): \(n \le 2 \cdot 10^5\).

Trong một cuộc bầu cử, có \(N\) đảng và tổng cộng \(V\) phiếu. Hiện tại đã kiểm được một phần phiếu, mỗi đảng \(i\) có \(a_i\) phiếu và tổng không vượt quá \(V\). Số phiếu còn lại là \(V - \sum a_i\).

Bạn chọn một đảng \(X\) và có quyền phân phối toàn bộ số phiếu còn lại cho các đảng bất kỳ, có thể dồn hết cho một đảng hoặc chia nhỏ.

Sau khi phân phối, gọi \(b_i\) là số phiếu cuối cùng của đảng \(i\) và \(s_i\) là số ghế đảng \(i\) đã nhận được tại thời điểm đang xét. Ban đầu mọi \(s_i = 0\).

\(M\) ghế được chia theo phương pháp D'Hondt với ngưỡng \(5\%\):

• Loại các đảng có \(b_i\) nhỏ hơn \(5\%\) của tổng \(V\).
• Sau đó lặp \(M\) lần, mỗi lần chọn đảng còn lại có giá trị \(Q_i = \frac{b_i}{s_i + 1}\) lớn nhất để nhận ghế.
• Sau khi đảng \(i\) nhận một ghế, tăng \(s_i\) lên \(1\).
• Nếu hòa thì chọn đảng có chỉ số nhỏ hơn.

Hãy xác định số ghế lớn nhất mà đảng \(X\) có thể đạt được nếu phân phối số phiếu còn lại một cách tối ưu.

Input

• Dòng đầu tiên gồm bốn số nguyên \(V, N, M, X\).
• Dòng thứ hai gồm \(N\) số nguyên \(a_1, a_2, \dots, a_N\).

Output

• In ra một số nguyên duy nhất là số ghế lớn nhất mà đảng \(X\) có thể đạt được.

Constraints

• \(1 \le N \le 2 \cdot 10^5\)
• \(1 \le M \le 2 \cdot 10^5\)
• \(1 \le V \le 10^{12}\)
• \(1 \le X \le N\)
• \(0 \le a_i \le V\)
• \(\sum a_i \le V\)

Example

20 4 5 1
4 3 6 1

3

Scoring

• Subtask \(1\) (\(10\%\) số điểm): \(N \le 8\), \(M \le 20\), \(V - \sum a_i \le 15\).
• Subtask \(2\) (\(20\%\) số điểm): \(N \le 100\), \(M \le 200\).
• Subtask \(3\) (\(20\%\) số điểm): \(N \le 1000\), \(M \le 2000\), \(\sum a_i = V\).
• Subtask \(4\) (\(20\%\) số điểm): \(N \le 1000\), \(M \le 2000\).
• Subtask \(5\) (\(30\%\) số điểm): Không có ràng buộc bổ sung.

Vào một ngày đẹp trời, khi ánh nắng nhẹ chiếu qua từng tán lá, bgb đang thong thả đi dạo trong khu vườn quen thuộc của mình. Không khí yên bình khiến bgb cảm thấy vô cùng thư giãn và thầm nghĩ trên đời sao lại có nhiều người ảo tưởng vậy nhỉ?
Nhưng vừa nói xong, một cơn gió lạnh thổi qua.
Phía sau bụi cây, có một người lạ xuất hiện. Tên đó tự xưng tên là hieuln2011.
Chưa kịp hiểu chuyện gì xảy ra, bgb đã bị bắt vào một không gian tối tăm, xung quanh là những bức tường phủ kín bởi vô số con số kỳ lạ.
hieuln2011 cười lớn và nói:

• "Ngươi dám cười ta là kẻ ảo tưởng? Vậy hôm nay ta sẽ cho ngươi thấy thế nào là ảo tưởng thật sự!"

Nó đưa ra thử thách:

Ta sẽ cho ngươi một số \(n\).

Nhiệm vụ của người là tìm số lượng số \(x\) là số ảo tưởng thoả mãn \(1 ≤ x ≤ n\), \(x\) là số ảo tưởng nếu \(x\) thoả mãn 2 điều kiện:

• Tổng các chữ số chia hết cho số lượng chữ số
• Tích các chữ số chia hết cho tổng các chữ số

Yêu cầu: Nhập vào một số nguyên dương \(n\). Hãy tính số lượng số ảo tưởng từ \(1\) đến \(n\).

Input

• Một dòng duy nhất chứa số nguyên \(n\) \((1 ≤ n ≤ 10^{12})\)

Output

• Một dòng duy nhất là kết quả bài toán.

Example

20

10

Scoring

• Subtask 1 \(20\%\) số test tương ứng với \(20\%\) điểm có \(1 ≤ n ≤ 100\).
• Subtask 2 \(30\%\) số test tương ứng với \(30\%\) điểm có \(1 ≤ n ≤ 10^5\).
• Subtask 3 \(50\%\) test còn lại ứng với \(50\%\) số điểm có \(1 ≤ n ≤ 10^{12}\).

bgb chuyển nhà đến một trang trại nhỏ, nhưng cậu ấy thường xuyên quay lại trang trại của bạn bè. Vì rất thích phong cảnh ven đường và không muốn chuyến đi kết thúc quá nhanh, mỗi lần đi từ trang trại \(1\) đến trang trại \(N\), bgb chọn đường đi ngắn thứ hai thay vì đường đi ngắn nhất.

Cho một đồ thị vô hướng có trọng số gồm \(N\) đỉnh và \(M\) cạnh. Cạnh thứ \(i\) nối hai đỉnh \(u_i, v_i\) và có độ dài \(w_i\).

Một đường đi từ \(1\) đến \(N\) có thể đi qua cùng một đỉnh hoặc cùng một cạnh nhiều lần.

Hãy tìm độ dài của đường đi ngắn thứ hai nghiêm ngặt từ \(1\) đến \(N\), tức là độ dài nhỏ nhất trong các đường đi có độ dài lớn hơn nghiêm ngặt độ dài đường đi ngắn nhất từ \(1\) đến \(N\).

Input

• Dòng đầu tiên chứa hai số nguyên \(N, M\).
• \(M\) dòng tiếp theo, mỗi dòng chứa ba số nguyên \(u, v, w\), mô tả một cạnh vô hướng giữa \(u\) và \(v\) có độ dài \(w\).

Output

• In ra một số nguyên duy nhất: độ dài đường đi ngắn thứ hai nghiêm ngặt từ \(1\) đến \(N\).

Constraints

• \(2 \le N \le 2 \cdot 10^5\)
• \(1 \le M \le 2 \cdot 10^5\)
• \(1 \le u, v \le N\)
• \(u \neq v\)
• \(1 \le w \le 5000\)
• Có ít nhất một đường đi từ \(1\) đến \(N\).
• Có thể có nhiều cạnh nối cùng một cặp đỉnh.

Example

4 4
1 2 100
2 4 200
2 3 250
3 4 100

450

4 5
1 2 1
2 4 1
1 3 1
3 4 1
2 3 5

4

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(N \le 500, M \le 500\).
• Subtask \(2\) (\(30\%\) số điểm): \(N \le 5000, M \le 5000\).
• Subtask \(3\) (\(40\%\) số điểm): Không có ràng buộc bổ sung.

Cho một cây gồm \(n\) đỉnh, đánh số từ \(1\) đến \(n\). Mỗi đỉnh \(i\) có trọng số không âm \(a_i\). Mỗi cạnh có trọng số không âm \(w_e\).

Bạn cần chọn đúng \(k\) đỉnh. Giá trị nhận được bằng tổng trọng số của các đỉnh được chọn, trừ đi tổng trọng số nhỏ nhất của các cạnh cần dùng để nối tất cả các đỉnh được chọn thành một cây con liên thông.

Nói cách khác, với tập \(S\) gồm đúng \(k\) đỉnh được chọn, gọi \(E(S)\) là tập cạnh của cây con nhỏ nhất chứa tất cả các đỉnh trong \(S\). Cần tối đa hóa:

Input

• Dòng đầu chứa hai số nguyên \(n, k\).
• Dòng thứ hai chứa \(n\) số nguyên \(a_1, a_2, \dots, a_n\).
• \(n - 1\) dòng tiếp theo, mỗi dòng chứa ba số nguyên \(u, v, w\), mô tả một cạnh của cây.

Output

• In ra một số nguyên duy nhất là giá trị lớn nhất có thể đạt được.

Constraints

• \(1 \le k \le n \le 5000\)
• \(0 \le a_i \le 10^9\)
• \(0 \le w_e \le 10^9\)

Example

5 3
1 2 3 4 5
1 2 1
1 3 1
3 4 1
3 5 1

10

8 4
26 6 46 39 34 44 42 32
1 2 20
1 3 6
2 4 24
2 5 26
3 6 29
3 7 27
4 8 24

96

Scoring

• Subtask \(1\) (\(10\%\) số điểm): \(n \le 20\).
• Subtask \(2\) (\(10\%\) số điểm): \(w_e = 0\) với mọi cạnh.
• Subtask \(3\) (\(10\%\) số điểm): \(k \le 2\).
• Subtask \(4\) (\(15\%\) số điểm): Cây là một đường thẳng.
• Subtask \(5\) (\(15\%\) số điểm): Tồn tại số nguyên \(W\) sao cho mọi cạnh đều có trọng số \(W\) và \(W > a_1 + a_2 + \dots + a_n\).
• Subtask \(6\) (\(20\%\) số điểm): \(n \le 100\).
• Subtask \(7\) (\(20\%\) số điểm): Không có ràng buộc gì thêm.