Bài kiểm tra đầu vào

Viết chương trình nhập vào điểm trung bình \(GPA\) của một học sinh (\(0 \le GPA \le 100\)). In ra màn hình kết quả xếp loại học lực của học sinh đó dựa trên các tiêu chí sau:

• \(GPA \ge 90\): Xuat sac
• \(GPA \ge 80\): Gioi
• \(GPA \ge 60\): Kha
• \(GPA \ge 50\): Dat
• \(GPA < 50\): Chua dat

Input

• Một số nguyên duy nhất là điểm trung bình \(GPA\) (\(0 \le GPA \le 100\)).

Output

• Một dòng duy nhất là kết quả xếp loại tương ứng (không có dấu).

Example

65

Kha

Nhập vào bốn số nguyên phân biệt \(a, b, c, d\). In ra màn hình số lớn thứ nhì trong bốn số đã nhập.

Input

• Một dòng duy nhất chứa bốn số nguyên phân biệt \(a, b, c, d\) (giá trị tuyệt đối không quá \(10^9\)).

Output

• In ra một số nguyên duy nhất là số lớn thứ nhì trong bốn số đã nhập.

Example

1 5 3 7

5

-10 20 0 15

15

Cho dãy số \(1, 4, 9, 16, 25, \dots\). Nhập vào số tự nhiên \(n\). Hãy in ra \(n\) số hạng đầu tiên của dãy số trên.

Input

• Một số tự nhiên \(n\) (\(n \le 10^6\)).

Output

• In ra \(n\) số hạng đầu tiên của dãy, mỗi số cách nhau một khoảng trắng.

Example

5

1 4 9 16 25

Các số nguyên tố nhỏ hơn \(10\) gồm: \(2, 3, 5, 7\). Tổng nguyên tố của một số là tổng các chữ số là số nguyên tố của nó.

Ví dụ: Số \(31012007\) có tổng nguyên tố là: \(3 + 2 + 7 = 12\).

Viết chương trình nhập vào số nguyên \(N\). In ra màn hình tổng nguyên tố của số đó.

Input

• Một số nguyên dương \(N\) \((1 \leq N \leq 10^{18})\).

Output

• In ra một số nguyên duy nhất là tổng nguyên tố của số \(N\).

Example

31012007

12

Nhập vào một dãy \(N\) số nguyên \(A_{1},A_{2},...,A_{N}\).

Hãy in ra màn hình Trung bình cộng các phần tử âm.

Input

• Dòng đầu tiên chứa số nguyên \(N\).
• \(N\) dòng tiếp theo chứa \(N\) số nguyên \(A_{1},A_{2},...,A_{N}\).

Output

• In ra Trung bình cộng các phần tử âm lấy \(2\) số lẻ sau phần thập phân, nếu trong dãy không có số âm nào thì in ra \(−1\).

Constraints

• \(1 \leq n \leq 10000\)
• \(|A_{i}| \leq 10^{9}\)

Example

7
7
6
-4 
19 
-22
51 
-82 

-36.00

Nhập vào một dãy \(N\) số nguyên \(A_{1},A_{2},...,A_{N}\).

Hãy in ra màn hình chỉ số phần tử dương đầu tiên và cuối cùng.

Input

• Dòng đầu tiên chứa số nguyên \(N\).
• \(N\) dòng tiếp theo chứa \(N\) số nguyên \(A_{1},A_{2},...,A_{N}\).

Output

• In ra chỉ số phần tử dương đầu tiên và cuối cùng, nếu ko có phần tử dương nào thì in ra \(2\) số \(−1 −1\).

Constraints

• \(1 \leq n \leq 10000\)
• \(|A_{i}| \leq 10^{9}\)

Example

7
7 -6 -4 19 -22 51 -82 

1 6

Số fibonacci là số có dạng:

\(F_1 = 1\)

\(F_2 = 1\)

\(F_N = F_{N-1} + F_{N-2}\)

Nhập vào số nguyên dương \(N\). In ra số fibonacci thứ \(N\).

Input

• Nhập vào số nguyên dương \(N\) (\(1 \leq N \leq 40\)).

Output

• In ra số fibonacci thứ \(N\).

Example

6

8

Cho một bảng số nguyên kích thước nxn. Hãy sắp xếp lại bảng số theo hình ziczac.

Input gồm

• Dòng 1: Số nguyên dương n (m, n ≤ 10^3)
• n dòng tiếp theo, mỗi dòng có n số (|a[i][j]| <=10^3)

Output: Bảng số sau khi đã xếp theo hình ziczac

Ví dụ:

Sample Input

3

2 4 10

5 4 2

1 2 3

Sample Ouput

1 2 2

4 3 2

4 5 10

Cho mảng \(A\) gồm \(N\) số nguyên và \(Q\) truy vấn. Mỗi truy vấn gồm hai số nguyên \(L\) và \(R\). Nhiệm vụ của bạn là in ra tổng các phần tử của mảng \(A\) trong đoạn từ chỉ số \(L\) đến \(R\).

Input

• Dòng 1: Hai số nguyên \(N\) và \(Q\) (\(1 \le N, Q \le 2 \cdot 10^5\)).
• Dòng 2: \(N\) số nguyên \(A_1, A_2, \dots, A_N\) (\(1 \le A_i \le 10^9\)).
• \(Q\) dòng tiếp theo: Mỗi dòng gồm 2 số \(L, R\) (\(1 \le L \le R \le N\)).

Output

• Với mỗi truy vấn, in ra tổng đoạn \([L, R]\) trên một dòng.

Example

8 4
3 2 4 5 1 1 5 3
2 4
5 6
1 8
3 3

11
2
24
4

Scoring

• Subtask 1 (\(50\%\) số điểm): \(N, Q \le 1000\).
• Subtask 2 (\(50\%\) số điểm): Ràng buộc gốc \(N, Q \le 2 \cdot 10^5\).

Cho một bảng số kích thước \(N \times N\). Có \(Q\) truy vấn, mỗi truy vấn yêu cầu tính tổng các số nằm trong hình chữ nhật con được xác định bởi góc trái trên \((x_1, y_1)\) và góc phải dưới \((x_2, y_2)\).

Input

• Dòng 1: Hai số nguyên \(N\) và \(Q\) (\(1 \le N \le 1000, 1 \le Q \le 2 \cdot 10^5\)).
• \(N\) dòng tiếp theo: Mỗi dòng gồm \(N\) số nguyên biểu diễn bảng số.
• \(Q\) dòng tiếp theo: Mỗi dòng gồm 4 số \(x_1, y_1, x_2, y_2\) (\(1 \le x_1 \le x_2 \le N, 1 \le y_1 \le y_2 \le N\)).

Output

• Với mỗi truy vấn, in ra tổng hình chữ nhật con tương ứng.

Example

4 3
1 2 3 4
5 6 7 8
1 1 1 1
2 2 2 2
1 1 2 2
2 2 3 3
1 1 4 4

14
15
48

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(N \le 100, Q \le 1000\).
• Subtask \(2\) (\(70\%\) số điểm): Không có ràng buộc gì thêm.

Cho dãy số \(A\) có \(N\) số nguyên. Hãy đếm số cặp \((i,j)\) sao cho \(A_i + A_j = 0\), với \(i < j\).

Input

• Dòng đầu tiên chứa một số nguyên dương \(N\) \((1 \leq N \leq 2*10^5)\)
• Dòng thứ hai chứa dãy số \(A\) gồm \(N\) số nguyên cách nhau bởi một ký tự khoảng trống. \((|A_i| \leq 10^9)\)

Output

• In ra một số nguyên duy nhất, là số cặp phần tử trong dãy \(A\) mà có tổng là 0.

Scoring

• Subtask \(1\) (\(25\%\) số điểm): \(N \leq 10^4\), \(|A_i| \leq 10^6\).
• Subtask \(2\) (\(60\%\) số điểm): \(N \leq 2*10^5\), \(|A_i| \leq 10^6\).
• Subtask \(3\) (\(100\%\) số điểm): \(N \leq 2*10^5\), \(|A_i| \leq 10^9\).

Example

3
-2 0 2

1

6
-2 -1 0 0 1 2

3

Cho một mảng gồm \(n\) số nguyên dương \(a_{1}, a_{2}, a_{3},..., a_{n}\). Hỏi có bao nhiêu cặp số \(i < j\) và \(a_{i} = a_{j}\).

Lưu ý: Số lượng này có thể rất lớn nên sử dụng kiểu long long.

Input

• Dòng thứ nhất là chiều dài \(n\) của mảng \((1 \leq n \leq 10^{5})\)
• Dòng thứ hai gồm \(n\) số nguyên \(a_{1}, a_{2}, a_{3},..., a_{n}\) \((1 \leq a_{i} \leq 10^{5})\), mỗi số cách nhau một khoảng trắng.

Output

• Gồm 1 dòng duy nhất là số nguyên xác định số lượng các cặp bằng nhau.

Example

5
8 2 9 8 1  

1

7
6 2 4 2 4 3 4

4

Cho số nguyên dương \(n\) và dãy số \(a\) gồm \(n\) số nguyên \(a_1, a_2, ..., a_n\). Một dãy con liên tiếp của dãy số \(a\) có dạng \(a_i, a_{i+1}, …, a_j\) với \(1 \leq i \leq j \leq n\), tổng của dãy con liên tiếp \(a_i, a_{i+1}, …, a_j\) là \(a_i, a_{i+1}, …, a_j\)
Em hãy đếm số lượng dãy con liên tiếp của dãy số a đã cho có tổng các phần tử của dãy con này chia hết cho số nguyên dương \(k\).

INPUT

• Dòng thứ nhất chứa hai số nguyên dương \(n\) và \(k\) \((1 \leq n \leq 10^6, 1 \leq k \leq 10^9)\). Các số trên cùng một dòng được phân tách bởi ít nhất một khoảng trắng.
• Dòng thứ hai chứa \(n\) số nguyên \(a_1, a_2, \dots, a_n\) \((|a_i| \leq 10^9, 1 \leq i \leq n)\). Các số trên cùng một dòng được phân tách bởi ít nhất một khoảng trắng.

Output

• In ra một số duy nhất là số lượng dãy con có tổng các phần tử chia hết cho \(k\).

Example

5 3
2 -6 1 9 -3

7

Ràng buộc

• Subtask \(1\) (\(50\%\) số điểm): Có \(n\) \((n \leq 10^3)\),
• Subtask \(2\) (\(50\%\) số điểm): Có \(n\) \((n \leq 10^6)\)

Vào một buổi sáng, anh Bo sắp một đàn bò gồm \(n\) con bò để vắt sữa. Anh dự kiến là vào sáng hôm đó, con bò thứ \(i\) có khả năng sẽ vắt được \(a_i\) lít sữa. Tuy nhiên đàn bò của anh có đặc tính là cứ mỗi lần vắt sữa một con, những con còn lại trông thấy sợ quá nên sẽ bị giảm sản lượng mỗi con \(1\) lít sữa.

Nếu vắt sữa con bò thứ nhất, \(n-1\) con còn lại bị giảm sản lượng. Sau đó vắt sữa con bò thứ hai thì \(n-2\) con còn lại bị giảm sản lượng... Bạn hãy giúp anh Bo tính xem thứ tự vắt sữa bò như thế nào để số lượng sữa vắt được là nhiều nhất nhé.

Lưu ý: Sản lượng sữa của một con bò không thể xuống dưới mức \(0\).

Input

• Dòng thứ nhất là số nguyên \(n\) (\(1 \le n \le 10^5\)) là số lượng con bò.
• Dòng thứ hai gồm \(n\) số nguyên \(a_1, a_2, \dots, a_n\) (\(1 \le a_i \le 10^9\)) là sản lượng sữa ban đầu của các con bò.

Output

• Một số nguyên duy nhất xác định số lít sữa nhiều nhất mà anh Bo có thể vắt được.

Example

4
4 4 4 4

10

4
2 1 4 3

6