Tối đa hóa tổng trị tuyệt đối

Cho một dãy số nguyên gồm N phần tử. Nhiệm vụ của bạn là thay đổi một số giá trị trong dãy thành 1 (hoặc giữ nguyên) sao cho tổng các trị tuyệt đối của chênh lệch giữa hai phần tử liên tiếp là lớn nhất.

Input:

• Dòng đầu tiên chứa số nguyên N (1 ≤ N ≤ 5 x 10⁵ ).
• Dòng thứ hai chứa N số nguyên A₁, A₂, ..., Aₙ (1 ≤ Aᵢ ≤10⁶ ).

Output:

• Một số nguyên duy nhất là tổng lớn nhất của trị tuyệt đối giữa hai phần tử liên tiếp sau khi biến đổi.

Ví dụ:

Input

3
1 8 9

Output

14

Ràng buộc :

• Subtask 1 (30% số điểm): n ≤ 20
• Subtask 2 (30% số điểm): n≤10³
• Subtask 3 (60% số điểm): không có ràng buộc gì thêm

Đếm số bộ thỏa mãn điều kiện

Cho một dãy số nguyên gồm N phần tử. Đếm có bao nhiêu bộ (i, j, k, t) thỏa mãn:

• 1 ≤ i < j < k < t ≤ N
• Aᵢ + Aⱼ + Aₖ + Aₜ = 0

Input:

• Dòng đầu tiên chứa số nguyên N (1 ≤ N ≤ 4000).
• Dòng thứ hai chứa N số nguyên A₁, A₂, ..., Aₙ(1 ≤ Aᵢ ≤ 1000).

Output:

• Một số nguyên duy nhất là số lượng bộ (i, j, k, t) thỏa mãn điều kiện.

  Ví dụ:

Input

5
1 2 -6 -3 0

Output

1

Ràng buộc :

• Subtask 1 (50% số điểm): n ≤ 40
• Subtask 2 (50% số điểm): không có ràng buộc gì thêm

Cắt gỗ tối ưu

Xưởng gỗ có n thanh gỗ và muốn cắt các thanh gỗ này thành k đoạn nhỏ có độ dài bằng nhau (có thể có gỗ dư).

Chúng ta muốn chiều dài của các đoạn nhỏ càng dài càng tốt, hãy tính giá trị lớn nhất của l.

Input:

• Dòng đầu tiên chứa hai số nguyên dương n và k (n ≤ 10^5, k ≤ 10⁸), lần lượt là số lượng thanh gỗ và số lượng đoạn gỗ cần thu được.
• Tiếp theo là n dòng, mỗi dòng chứa một số nguyên dương Li ( Lᵢ ≤ 10⁸) là độ dài của một thanh gỗ.

Output:

• Một số nguyên duy nhất là giá trị lớn nhất của l.
• Nếu không thể cắt được đoạn nào dài ít nhất l, in ra 0.

Ví dụ:

Input

3 7
232
124
456

Output

114

Kiểm tra số Orz

Quy ước một số Orz là số có đúng k ước.

Cho T bộ test, kiểm tra xem số n có phải là số Orz hay không.

Input:

• Dòng đầu tiên là số T (1 ≤ T ≤ 10 ⁶ ).
• Tiếp theo là T số nguyên dương n (1 ≤ n ≤ 10 ⁶ ).

Output:

• In ra T dòng, mỗi dòng in YES nếu n là số Orz, ngược lại in NO.

Ví dụ:

Input

3
4
5
6

Output

YES
NO
NO

Note: k=3

Ràng buộc :

• Subtask 1 (30% số điểm): T=1, n ≤ 10⁶
• Subtask 2 (30% số điểm): T=10³, n≤10⁶
• Subtask 3 (60% số điểm): không có ràng buộc gì thêm

minhphan là một học sinh thông minh, cần cù chịu khó nhưng khá lười biếng. Một hôm, minhphan được thầy cho bài tập như sau: Cho trước số nguyên dương ~N~ ~(N~ ~≤~ ~50)~. Hãy đếm số lượng xâu nhị phân có độ dài ~N~ mà trong xâu đó không có ~2~ kí tự ~1~ nào đứng cạnh nhau. Nhưng vì tối qua minhphan mãi chơi Free Fire đến khuya nên sáng nay bạn ấy không còn đủ tỉnh táo để làm bài tập, các bạn hãy giúp minhphan giải bài tập này nhé!

Input

• Số nguyên dương ~N~ duy nhất.

Output

• Số nguyên duy nhất là số lượng xâu nhị phân có độ dài ~N~ mà trong xâu đó không có 2 kí tự 1 nào đứng cạnh nhau.

Ví dụ

Input

3

Output

5

• Giải thích: Với ~N~ ~=~ ~3~, ta có ~5~ dãy ~000, 001, 010, 100, 101~.

Subtask:

• Subtask ~1~ (40% số điểm): ~N~ ~≤~ ~20~.
• Subtask ~2~ (60% số điểm): ~20~ ~<~ ~N~ ~≤~ ~50~.

Một số nguyên A được gọi là số gần hoàn hảo nếu thoả mãn điều kiện 2 * A ≤ K, với K là tổng các ước số của A

Ví dụ: 12 là số gần hoàn hảo vì 2 * 12 ≤ 1 + 2 + 3 + 4 + 6 + 12

INPUT

• Dòng thứ nhất là t - số bộ tests (t ≤ 10⁴)
• t dòng tiếp theo chứa 1 số nguyên dương n (n ≤ 10⁶)

OUTPUT

• Dòng đầu tiên: số lượng chữ số hoàn hảo
• Các dòng tiếp theo: các số hoàn hảo

Example

INPUT

3
8
6
7

OUTPUT

1
6

Giải thích: 2 * 6 ≤ 1 + 2 + 3 + 6

Subtask

• Subtask 1 (60% số điểm): t ≤ 2000
• Subtask 2 (40% số điểm): không có giới hạn gì thêm

Given 3 integers a, b, c (a, b, c ≤ 10⁹). Find the solutions of the equation ax² + bx + c.

Input

• The only line contain 3 integers a, b, c

Output

• The solution of the equation(take 5 digits after decimal point), if there isn't any solution then print: NO SOLUTION

Example

Input

1 -5 4

Output

4.00000 1.00000

Nhân dịp kỷ niệm 93 năm ngày thành lập Đoàn TNCS Hồ Chí Minh, Trung ương Đoàn tổ chức cuộc thi trực tuyến "Tìm hiểu về lịch sử Đoàn TNCS Hồ Chí Minh". Cuộc thi tạo cơ hội cho đoàn viên thanh niên trên cả nước tham gia và có hội nhận được những giải trị.

Trong cuộc thi này, mỗi đoàn viên thanh niên được tham gia thi một lần, sau khi hoàn thành tất cả các câu hỏi, các bạn đoàn viên thanh niên nhập một số nguyên bất kỳ là số may mắn của mình và nộp bài. Bài làm thứ ~i~ có số nguyên tương ứng là ~a~_~i~. Ban tổ chức xác định thí sinh đạt giải bằng cách tính điểm trả lời câu hỏi và thời gian làm bài. Nếu có nhiều thí sinh trùng điểm và thời gian làm bài thì Ban tổ chức tính điểm may mắn bằng cách chọn một số ~K~ ngẫu nhiên và cộng điểm may mắn cho mỗi cặp thí sinh ~i, j~ ~(i≠j)~ có ~|ai + aj| = K.~ Một thí sinh có thể được cộng điểm nhiều lần nếu có thể bắt cặp với nhiều thí sinh khác thỏa mãn điều kiện.

Nhiệm vụ của bạn là xác định xem có bao nhiêu cặp thí sinh được cộng điểm.

Input:

Dòng 1: Gồm hai số nguyên ~N~ và ~K (0 < N ≤~ ~10~^~6~~, 0 < K ≤ 10~^~18~~)~

Dòng 2: Gồm ~N~ số nguyên ~a~_~i~ ~(|ai| ≤~ ~10~^~9~ ~)~

Output:

Gồm một dòng duy nhất ghi số lượng cặp thí sinh được cộng điểm.

Ví dụ:

Input 1

7 5
4 8 4 1 4 5 -6

Output 1

4

Input 2

5 11
3 1 0 7 3

Output 2

0