Vector

Cho tập hợp số tự nhiên không vượt quá \(n\) (là số chẵn và cho trước)

\(S = \{1, 2, 3, 4\dots\, n-1, n\}\)

Hỏi phải lấy ít nhất bao nhiêu số từ tập hợp \(S\) để có \(2\) số sao cho tổng của chúng chia hết cho \((n + 1)\).

Rõ hơn, tìm \(x\) nhỏ nhất sao cho mọi tập con \(x\) phần tử của \(S\) tồn tại 2 số khác nhau có tổng chia hết cho \((n + 1)\).

Yêu cầu: Nhập \(n(2 \leq n \leq 10^9)\), in ra \(x\).

Example

4

3

Cho một mảng gồm \(n\) số nguyên . Tìm \(2\) chỉ số \(i,j\) thỏa mãn \(1\le i<j\le n\) và \(a[j]-a[i]\) đạt giá trị lớn nhất.

Input

• Dòng thứ nhất chứa số nguyên dương \(n(2\le n\le 10^5)\)

• Dòng thứ hai chứa \(n\) số nguyên \(a_i(-10^3\le a_i\le 10^3 \text{ }\forall 1\le i\le n)\)

Output

• Dòng thứ nhất chứa hai chỉ số \(i,j\) thỏa mãn yêu cầu bài toán

• Dòng thứ hai in ra giá trị \(a[j]-a[i]\)

  (Chú ý nếu có nhiều đáp án in ra đáp án bất kì).

Example

3
1 2 3

1 3
2

Bạn được cho một mảng gồm \(n\) số nguyên dương. Bạn cần biến đổi sao cho mảng này được sắp xếp theo trình tự tăng dần, và mọi phần tử trong mảng đều không nhỏ hơn phần tử đứng trước.

Trong mỗi lần biến đổi, bạn có thể tăng một phần tử lên một đơn vị. Hãy tìm số lần biến đổi ít nhất để thoả mản điều kiện trên.

Input

• Dòng đầu chỉ chứa số nguyên dương \(n\) là độ dài của mảng
• Dòng thứ hai gồm \(n\) số nguyên dương \(x_1, x_2, \ldots, x_n\), là các phần tử của mảng

Constraints

• \(1 \leq n \leq 2\cdot 10^5\)
• \(1 \leq x_i \leq 10^9\)

Output

• In ra số lần biến đổi ít nhất

Example

5
3 2 5 1 7

5

Có \(n\) người đăng ký và \(m\) căn hộ trống. Nhiệm vụ của bạn là phân phối các căn hộ để nhiều người có căn hộ nhất có thể.

Mỗi người đăng ký có một kích thước căn hộ mong muốn, và họ sẽ chấp nhận bất kỳ căn hộ nào có kích thước đủ gần với kích thước mong muốn.

Input

• Dòng đầu vào đầu tiên có ba số nguyên \(n\), \(m\) và \(k\): số lượng người đăng ký, số lượng căn hộ và chênh lệch tối đa cho phép.
• Dòng tiếp theo chứa \(n\) số nguyên \(a_1,a_2,\ldots,a_n\): kích thước căn hộ mong muốn của mỗi người đăng ký. Nếu kích thước mong muốn của người đăng ký là \(x\), người đó sẽ chấp nhận bất kỳ căn hộ nào có kích thước từ \(x-k\) đến \(x+k\).
• Dòng cuối cùng chứa \(m\) số nguyên \(b_1,b_2,\ldots,b_m\): kích thước của mỗi căn hộ.

Constraints

• \(1 \leq n, m \leq 2\cdot 10^5\)
• \(0 \leq k \leq 10^9\)
• \(1 \leq a_i, b_i \leq 10^9\)

Output

• In một số nguyên: số lượng người sẽ có được một căn hộ.

Example

4 3 5
60 45 80 60
30 60 75

2

Trong một lễ hội phim, \(n\) bộ phim sẽ được chiếu. Bạn biết thời gian bắt đầu và kết thúc của mỗi bộ phim. Số lượng phim tối đa bạn có thể xem trọn vẹn là bao nhiêu?

Input

• Dòng đầu vào đầu tiên có một số nguyên \(n\): số lượng bộ phim
• Sau đó có \(n\) dòng mô tả các bộ phim. Mỗi dòng có hai số nguyên \(a\) và \(b\): thời gian bắt đầu và kết thúc của một bộ phim

Constraints

• \(1 \leq n \leq 2 \cdot 10^5\)
• \(1 \leq a < b \leq 10^9\)

Output

• In một số nguyên: số lượng phim tối đa

Example

3
3 5
4 9
5 8

2

An thích những thứ be bé nhưng T lại không như vậy. Để chiều lòng T, An quyết định tặng cho nàng phần tử lớn nhất trong dãy có độ dài \(n\). Hãy giúp An tìm nó nhé!

Input

• Dòng 1: số \(n\) \((n \leq 10^5)\)
• Dòng 2: dãy gồm \(n\) số \(a_i(1 \leq a_i \leq 10^9)\)

Output

• In ra số lớn nhất

Example

5
1 3 5 7 6

7

Cảm kích vì món quà của \(A\), nhân ngày valentine trắng \(T\) quyết định trả ơn bằng phần tử nhỏ nhất có độ dài \(n\)

Input

• Dòng đầu tiên ghi số \(n\) \((n \leq 10^5)\)
• Dòng tiếp theo là các phần tử trong dãy (trị tuyệt đối không vượt quá \(10^9\))

Output

• In ra phần tử nhỏ nhất của dãy

Example

5
5 9 2 7 9

2

Nhập số nguyên dương \(N\) và \(N\) số nguyên dương. Hãy in ra số lớn nhì và số nhỏ nhì.

Input

• Dòng 1 nhập số nguyên dương \(N\)(\(4 \leq N \leq 10^4\)).
• Dòng 2 nhập \(N\) số nguyên \(A_1,A_2,...,A_N\) (\(1 \leq A_i \leq 10^4\)).

Output

• In ra số lớn nhì và số bé nhì.

Example

5
1 2 3 4 5

4 2

A là một người thầm lặng. A giữ khoảng cách với mọi người, tỏ ra vẻ lạnh lùng, thích những khoảng lặng tâm hồn. Vì vậy hãy giúp A tìm khoảng cách lớn nhất giữa 2 phần tử liên tiếp nhé.

Input

• Dòng 1 nhập số nguyên dương \(N\) (\(1 \leq N \leq 10^5\)).
• Dòng 2 nhập \(N\) số nguyên \(A_i\) (\(1 \leq i \leq N, |A_i| \leq 10^9\)).

Output

• In ra độ chênh lệch lớn nhất giữa 2 phần tử liên tiếp.

Example

5
2 8 -2 10 4

12

T rất thích những số lớn. Đặc biệt, T thích những số lớn hơn hoặc bằng \(X\). Hãy giúp bạn T đếm những số lớn hơn hoặc bằng \(X\) trong dãy số gồm \(N\) số nguyên nhé.

Input

• Dòng 1 nhập 2 só nguyên \(N\), \(X\)(\(1 \leq N \leq 10^5, |X| \leq 10^9\)).
• Dòng 2 nhập \(N\) số nguyên \(A_i\) (\(1 \leq i \leq N, |A_i| \leq 10^9\)).

Output

• In ra kết quả theo yêu cầu đề bài.

Example

5 3
2 1 3 5 4

3

Cho dãy \(a\) gồm \(n\) số, tính tổng tất cả các số trong dãy \(a\)

Input

• Dòng 1: Số \(n(1 \leq n \leq 10^5)\)
• Dòng 2: Gồm \(n\) số nguyên, số \(a_i(0 \leq a_i \leq 10^9)\)

Output

• In ra tổng các số vừa nhập

Example

4
2 3 4 5

14

Cho 1 dãy gồm \(n\) số, tính tổng các số khác 0

Input

• Dòng 1: Số \(n(1 \leq n \leq 10^5)\)
• Dòng 2: Gồm \(n\) số nguyên, mỗi số có giá trị tuyệt đối không quá \(10^9\)

Output

• In ra tổng các số khác 0 vừa nhập

Example

5
2 3 4 5 0

14

Tính trung bình cộng của 1 dãy gồm \(n\) số

Input

• Dòng 1: Số \(n(1 \leq n \leq 10^4)\)
• Dòng 2: Gồm \(n\) số nguyên, mỗi số có giá trị không quá \(10^3\)

Output

• In ra kết quả lấy đến 2 chữ số sau phần thập phân

Example

3
19 20 21

20.00

Nhập số nguyên dương \(N\) và \(N\) số nguyên dương. Hãy in ra 3 số lớn nhất theo thứ tự giảm dần.

Input

• Nhập số nguyeend ương \(N\) (\(1 \leq N \leq 10^5\)).
• Nhập \(N\) số nguyên dương \(A_i\) (\(1 \leq i \leq N, |A_i| \leq 10^9\)).

Output

• In ra độ chênh lệch lớn nhất giữa 2 phần tử liên tiếp.

Example

5
2 1 3 5 4

5 4 3

Nhập vào số nguyên dương \(n\). In ra tam giác pascal bậc \(n\)

Input

• Số nguyên dương \(x\) \((1 \leq n \leq 10)\)

Output

• In ra độ dài của đoạn con tìm được

Example

5

1
1 1
1 2 1
1 3 3 1
1 4 6 4 1

Cho một hình chữ nhật có \(n\) dòng \(m\) cột. Bé Bi muốn tìm tổng các phần tử một hình chữ nhật con của hình chữ nhật đó, hãy giúp bé Bi nhé!

Input

• Dòng đầu tiên ghi \(n\) và \(m\). \((1 \leq n, m \leq 1000)\)
• \(n\) dòng tiếp theo, mỗi dòng gồm \(m\) số nguyên cách nhau bởi dấu cách \((|a[i,j]| \leq 1000)\)
• Dòng cùng ghi tọa độ góc trái nên \((x1, y1)\) và phải dưới \((x2, y2)\) của một hình chữ nhật nhỏ hơn bên trong hình chữ nhật ban đầu \((1 \leq x1 \leq x2 \leq n, 1 \leq y1 \leq y2 \leq m)\)

Output

• In ra kết quả mà bé Bi cần

Example

2 3
1 1 9
8 2 9
1 1 2 2 

12

`

Cho một bảng hình chữ nhật gồm \(n\) dòng và \(m\) cột. Tính tổng các phần tử nằm trên tọa độ \([i,j]\) mà \(i+j\) bằng một số chẵn.

Input

• Dòng đầu tiên ghi 2 số \(n\) và \(m\). \((1 \leq n, m \leq 1000)\)
• \(n\) dòng tiếp theo, mỗi dòng \(m\) số nguyên cách nhau bởi dấu cách. \((|a[i,j]| \leq 1000)\)

Output

• Đưa ra kết quả mà đề bài yêu cầu

Example

2 3
1 1 9
8 2 9

12

Cho một bảng hình vuông gồm \(n\) dòng và \(n\) cột. Hãy tính tổng các phần tử nằm trên hai đường chéo của hình vuông

Input

• Dòng đầu tiên ghi 1 số. \((1 \leq n \leq 25)\)
• \(n\) dòng tiếp theo, mỗi dòng gồm \(n\) số nguyên cách nhau bởi dấu cách. \((|a[i,j]| \leq 5)\)

Output

• Đưa ra kết quả mà đề bài yêu cầu

Example

3
1 -2 3
-1 0 5
1 4 -3

2

Cho một bảng \(n*n\). Xét từng hình vuông đồng tâm là tâm của bảng, hãy tính tổng các số trên mỗi hình vuông đó.

Input

• Dòng đầu tiên ghi số \(n\). \((1 \leq n \leq 300)\)
• \(n\) dòng tiếp theo, mỗi dòng gồm \(n\) số nguyên cách nhau bởi dấu cách. \((|a[i,j]| \leq 1000)\)

Output

• Đưa ra kết quả mà đề bài yêu cầu

Example

3
1 1 9
8 2 9
1 4 6

2 39

Cho ma trận \(n*n\), tính tổng các phần tử nằm trên các cột lẻ và hàng lẻ

Input

• Dòng 1: số \(n\) \((n < 100)\)
• Các dòng tiếp theo gồm các số mô tả bảng \(n*n\), giá trị tuyệt đối của các số không vượt quá 1000

Output

• In ra kết quả

Example

3
1 2 3
2 3 1
2 3 3

9