Máy chủ tạo khóa mã hóa cần sinh ra các cặp khóa công khai và khóa bí mật. Số lượng cặp khóa khả thi là số lượng các cặp số nguyên dương (A, B) sao cho tích A * B nhỏ hơn hoặc bằng một giá trị giới hạn N cho trước. Bạn hãy viết chương trình đếm xem có tất cả bao nhiêu cặp khóa (A, B) thỏa mãn điều kiện này. (Lưu ý: cặp (1, 2) và cặp (2, 1) được tính là 2 cặp khác nhau).

Input: Số nguyên dương N (1 <= N <= 10^7).

Output: Số lượng cặp (A, B) thỏa mãn.

Ví dụ:

Input:

3

Output:

5

(Giải thích: Các cặp là (1,1), (1,2), (1,3), (2,1), (3,1)).

Học Công Nghệ thi đấu robot với trường bạn. Mỗi bên tung ra N con robot. Robot của trường mình có sức mạnh Ai, robot trường bạn có sức mạnh Bi. Hai con robot đấu tay đôi, con nào có sức mạnh lớn hơn thì thắng 1 điểm (Hòa hoặc thua được 0 điểm). Thầy giáo biết trước mảng sức mạnh của đội bạn. Bằng chiến thuật sắp xếp thứ tự xuất quân (Hy sinh robot yếu nhất của mình để cầm chân robot mạnh nhất của địch), hãy tính số điểm tối đa trường mình có thể đạt được.

Dữ liệu vào:

Dòng 1: Số N (1 <= N <= 10^5).

Dòng 2: N số nguyên mảng A (Sức mạnh trường mình).

Dòng 3: N số nguyên mảng B (Sức mạnh trường bạn).

Kết quả ra: Số điểm (số trận thắng) tối đa.

Ví dụ:

Input:

3
2 7 11
10 20 9

Output:

1

Dọc theo tuyến đường sắt có N trạm phát sóng. Trạm thứ i có thể phủ sóng một đoạn từ kilomet thứ Li đến kilomet thứ Ri. Hãy tìm tọa độ kilomet nguyên nào trên tuyến đường được phủ sóng bởi nhiều trạm phát nhất. Nếu có nhiều tọa độ cùng đạt mức phủ sóng lớn nhất, in ra tọa độ nhỏ nhất.

Input:

Dòng 1: N (1 <= N <= 10^5).

N dòng tiếp theo: Li, Ri (1 <= Li <= Ri <= 10^5).

Output: Tọa độ có nhiều trạm phủ sóng nhất.

Ví dụ:

Input:

3
1 5
2 8
4 6

Output:

4

(Giải thích: Tại tọa độ 4 và 5, cả 3 trạm đều phủ sóng. Số nhỏ nhất là 4).

Cho dãy số A[] gồm có N phần tử, các phần tử trong mảng chỉ là 0 1 hoặc 2. Hãy sắp xếp các phần tử trong mảng theo thứ tự tăng dần.

Định dạng đầu vào: Dòng đầu tiên là số nguyên N. Dòng tiếp theo gồm N số nguyên A[i]

Ràng buộc: 1≤ N ≤ 10^7; 0 ≤ A[i] ≤ 2

Định dạng đầu ra: In ra mảng được sắp xếp tăng dần.

Input:

5
1 1 0 2 1

Output:

0 1 1 1 2

Nhân dịp kênh YouTube của HCN được 100 triệu subscribers, chủ kênh HCN giấu tên quyết định mở một cuộc giveaway lớn nhất trong lịch sử. Cụ thể, sẽ có n subscribers được chọn và mỗi subscriber này sẽ nhận được một mã số ai và một hộp quà có giá trị là bi (1≤i≤n).

Kênh YouTube HCN được thành lập để truyền tải những thông điệp nhân văn nên nhân dịp giveaway này, Chủ kênh đã lập quỹ giấu tên để mọi người có thể cùng giúp đỡ và tạo điều kiện cho những người có hoàn cảnh khó khăn. Chủ kênh định nghĩa một cặp subscribers là cặp "may mắn" nếu tổng giá trị hai mã số của cặp này lớn hơn tổng giá trị hai hộp quà mà cặp này đang sở hữu. Nói cách khác, cặp (i, j) (1 ≤ i, j ≤ n) là cặp "may mắn" nếu ai + aj > bi + bj. Với mỗi cặp "may mắn" mà chủ kênh tìm được, chủ kênh sẽ quyên góp 1 USD vào quỹ từ thiện giấu tên.

Hãy giúp chủ kênh tính số tiền mà anh ấy sẽ quyên góp vào quỹ từ thiện của mình.

Input:

• Dòng đầu tiên chứa số nguyên dương n (n ≥ 2);

• Dòng thứ hai chứa n số nguyên a1, a2,..., an (1 ≤ ai ≤ 10, 1 ≤ i ≤n);

• Dòng thứ ba chứa n số nguyên b1, b2,..., bn (1 ≤ bi ≤10°, 1 ≤i ≤n).

Output: In ra kết quả là số tiền (đơn vị USD) mà chủ kênh sẽ quyên góp vào quỹ giấu tên trong sự kiện giveaway này.

Input:

4
3 2 4 5
2 3 6 4

Output:

1

Giải thích: Cặp (1,4) là cặp subscribers "may mắn".

Input:

4
3 2 4 5
2 2 6 4

Output:

3

Giải thích: Các cặp (1,2), (1, 4), (2, 4) là các cặp subscribers "may mắn".

Cho số nguyên dương N. Hãy đếm xem có bao nhiêu cách phân tích N thành tổng của các số nguyên dương. Các cách hoán vị của nhau được tính là một cách (ví dụ 1+2 và 2+1 là giống nhau).

Dữ liệu vào:

Dòng 1: Số nguyên N (1 <= N <= 100).

Dữ liệu ra:

Số cách phân tích.

Ví dụ:

Input:

4

Output:

5

Để vượt qua cánh cửa ma thuật, bạn cần trả đúng một lượng vàng là S. Bạn đang có N loại đồng xu, loại thứ i có giá trị Vi và bạn có chính xác Ci đồng xu loại đó. Bạn có bao nhiêu cách để lấy ra các đồng xu sao cho tổng giá trị của chúng đúng bằng S? Hai cách lấy được coi là khác nhau nếu số lượng đồng xu của ít nhất một loại là khác nhau. In kết quả lấy dư cho 10^9+7.

Input:

Dòng 1: N, S (1 <= N <= 100, 1 <= S <= 10^4).

N dòng tiếp theo: Mỗi dòng 2 số nguyên Vi, Ci (1 <= Vi <= 1000, 1 <= Ci <= 100).

Output: Số cách tạo ra tổng S modulo 10^9+7.

Ví dụ:

Input:

2 5
1 3
2 2

Output:

2

(Giải thích: Cần tổng = 5. Cách 1: dùng 3 xu loại 1 (tổng 3) và 1 xu loại 2 (tổng 2). Cách 2: dùng 1 xu loại 1 (tổng 1) và 2 xu loại 2 (tổng 4)).

Cho dãy số A chỉ gồm các số 1, 2, 3.

Hãy tìm độ dài của đoạn con liên tiếp ngắn nhất chứa đủ cả ba số 1, 2 và 3.

Nếu không có, in ra 0.

Input:

• Dòng 1: N.

• Dòng 2: N số nguyên A[i].

Giới hạn:

• 1 <= N <= 2*10^5

• A[i] thuộc {1, 2, 3}

Output:

• Độ dài ngắn nhất hoặc 0.

Ví dụ 1:

Input:

5
1 2 2 3 1

Output:

3

Ví dụ 2:

Input:

4
1 1 2 2

Output:

0

Một đoạn con được gọi là "Cân bằng" nếu số lượng số chẵn bằng số lượng số lẻ.

Tuy nhiên, bài này dùng cửa sổ trượt: Hãy tìm độ dài đoạn con dài nhất sao cho chênh lệch giữa (số lượng số chẵn) và (số lượng số lẻ) không vượt quá K.

Input:

• Dòng 1: N, K.

• Dòng 2: N số nguyên A[i].

Giới hạn:

• 1 <= N <= 10^4

• 0 <= K <= N

• 1 <= A[i] <= 10^9

Output:

• Độ dài dài nhất thỏa mãn.

Ví dụ 1:

Input:

5 1
1 1 1 2 2

Output:

5

Ví dụ 2:

Input:

3 0
1 1 1

Output:

0