LTOJ Challenge 01

Bạn được cho một số tự nhiên \(N\). Hãy tính tổng các số tự nhiên từ \(1\) đến \(N\), tuy nhiên có các phần tử mang giá trị âm, đó chính là các số có thể viết dưới dạng luỹ thừa cơ số \(2\).

Input

Dữ liệu nhập từ tệp PHANBU.INP có cấu trúc như sau:

• Dòng \(1\): Số tự nhiên \(N\).

Output

Dữ liệu ghi ra tệp PHANBU.OUT theo cấu trúc như sau:

• Dòng \(1\): Tổng tìm được.

Ràng buộc

• Subtask \(1 (80\%\) số test\()\): Có \(N \leq 10^6\).
• Subtask \(2 (20\%\) số test\()\): Có \(N \leq 10^9\).

10

25

Cho dãy \(a\) có \(n\) phần tử \(a_1,a_2,a_3,...,a_n\). Hãy đếm số lượng cặp số \((i,j)\) sao cho \(1 \leq i < j \leq n\) và \(3a_i+2a_j=S\).

Input

Dữ liệu nhập từ tệp CAPSO.INP có cấu trúc như sau:

• Dòng \(1\): Chứa hai số tự nhiên \(n\) và \(S\)
• Dòng \(2\): Chứa \(n\) số tự nhiên \(a_1,a_2,...,a_n\).

Output

Dữ liệu ghi ra tệp CAPSO.OUT theo cấu trúc như sau:
- Dòng \(1\): Số lượng cặp số tìm được.

Subtasks

• \(70\%\) số điểm có \(n \leq 10^3\)
• \(30\%\) số điểm còn lại có \(n \leq 10^6\)

Tất cả các test đều đảm bảo \(0 \leq a_i \leq 10^6, 0 \leq S \leq 10^{18}\)

5 10
1 2 1 1 2

1

Cho dãy số \(a\) có \(n\) phần tử lần lượt là \(k,k+1,k+2,...,n+k-1\). Hãy tìm chỉ số \(i\) sao cho \(x=|a_1+a_2+a_3+...+a_i-a_{i+1}-a_{i+2}-...-a_n|\) là bé nhất có thể. Ký hiệu \(|x|\) biểu diễn giá trị tuyệt đối của \(x\).

Input

Dữ liệu nhập từ tệp ARRAY.INP có cấu trúc như sau:

• Dòng đầu tiên chứa số nguyên dương \(t (1 \leq n \leq 10^4)\)
• \(t\) dòng tiếp theo, mỗi dòng chứa hai số nguyên dương \(n,k (1 \leq n,k \leq 10^9)\) lần lượt là số lượng phần tử của dãy số và điểm bắt đầu của dãy số.

Output

Dữ liệu xuất ra tệp ARRAY.OUT theo cấu trúc như sau:
- Với mỗi test case, hãy in ra kết quả |x| tìm được.

Subtask

• Subtask \(1(30\%\) số điểm\()\) có \(t \leq 10,1 \leq n,k \leq 10^6\).
• Subtask \(2(70\%\) số điểm\()\) không có ràng buộc gì thêm.

4
2 2
7 2
5 3
1000000000 1000000000

1
5
1
347369930

Một dãy ngoặc đúng là một xâu gồm các ký tự (, ), [, ], { và } định nghĩa như sau:

• Xâu rỗng (không có ký tự nào) là một dãy ngoặc đúng,
• Nếu A và B là hai dãy ngoặc đúng thì AB (xâu tạo thành bằng cách lấy xâu A nối vào trước xâu B) cũng là một dãy ngoặc đúng,
• Nếu A là một dãy ngoặc đúng thì (A), [A] và {A} cũng là những dãy ngoặc đúng.
  Những xâu không thành lập được theo quy tắc trên không phải là dãy ngoặc đúng.

Ví dụ {[()()[]()]}() là một dãy ngoặc đúng nhưng [(]) và }}}{{{ không phải là những dãy ngoặc đúng.

Input

Dữ liệu nhập từ tệp DAYNGOAC.INP có cấu trúc như sau:

• Dòng đầu tiên chứa số nguyên dương \(n (n\leq 10)\)
• \(n\) dòng tiếp theo, mỗi dòng chứa một xâu ký tự có độ dài không vượt quá \(10^6\) và chỉ chứa các ký tự (, ), [, ], { và }.

Output

Dữ liệu in ra tệp DAYNGOAC.OUT theo cấu trúc như sau:
- Ghi \(n\) dòng, mỗi dòng ghi YES/NO tương ứng với xâu tương ứng có phải là dãy ngoặc đúng hay không.

4
{[()()[]()]}()
[(])
([{}]){[()]}
{{{}}

YES
NO
YES
NO