Bài tập 2 con trỏ

Cô giáo trường tiểu học \(X\) đang dạy \(n\) học sinh tập xe đạp, các học sinh được đánh số từ \(1\) tới \(n\), học sinh thứ \(𝑗\) có trọng lượng là \(a_𝑗\). Có một xe đạp duy nhất với tải trọng là \(m\), hai học sinh chỉ có thể cùng lên xe nếu tổng trọng lượng của hai học sinh không vượt quá \(m\).

Cô giáo tự hỏi có bao nhiêu cách chọn hai học sinh khác nhau cho cùng lên xe, sau nhiều giờ tính toán không có kết quả, cô quyết định hỏi các chuyên gia lập trình giải bài toán Counting Student Pairs (CSP)

Yêu cầu: Đếm số cặp chỉ số \(i, j\) trong đó \(i < j\) và \(a_i + a_j \leq m\)

Input

• Dòng 1 chứa hai số nguyên dương \(n, m\ (m \leq 10^6)\)
• Dòng 2 chứa \(n\) số nguyên dương \(a_1, a_2, \ldots, a_n\) (\(\forall{i}: a_i \leq 10^6\))

Output

Ghi một số nguyên duy nhất là đáp số

Scoring

• Subtask #1 (\(60\%\) số điểm): \(n \leq 10^4\).
• Subtask #2 (\(20\%\) số điểm): \(n \leq 10^5\).
• Subtask #3 (\(20\%\) số điểm): \(n \leq 10^6\).

Example

5 6
1 2 3 4 5

6

Một ngày lướt fb, TN thấy một đôi couple chia sẻ bài bói toán online, rằng đôi couple kia hợp nhau thế nào, yêu nhau ra sao, vân vân và mây mây. Tò mò không biết âm dương ngũ hành, yêu nhau hợp tình nghĩa không, TN cũng bảo Ami cùng mình tham gia bói toán online. Nhưng Ami đời nào tin những thuật toán tào lao ấy? “Bởi vì không một thuật toán nào định nghĩa được tình yêu cả” – Ami nói. Cậu bèn dẫn TN đến cặp thầy bói nổi danh thiên hạ - zerolifes và huy_yeu_minh_nghia. Hai lúc nào cũng hơn một mà :)).

Sau khi xem chỉ tay, tướng số, ngũ hành, chiêm tinh, zerolifes không nói không rằng. Anh đọc liên tục 1 câu thần chú chỉ toàn những con số vô nghĩa nhưng không giảm. Đột nhiên zerolife dừng lại, huy_yeu_minh_nghia hét lên một số :”30”. “Nhưng 30 là gì ? Không lẽ 2 vị này cao thâm đến mức biết ngày mình và TN quen nhau sao ?”, Ami thầm nghĩ, “Hay 30 là số tỉ USD mà sau này mình tậu được ? Không, không thể ít như vậy được.” Không thể kìm nén, Ami thỉnh cầu 2 vị cao nhân. Zerolifes nói :”Đơn giản thôi, âm dương hòa hợp, trong cương có nhu, trong nhu có cương, cậu hãy ghi nhớ dãy số của ta và số mà huy_yeu_minh_nghia vừa đọc, hãy đếm xem trong dãy số của ta có bao nhiêu cặp số có tổng đúng bằng k. Nếu số cặp càng lớn, khả năng hai người bền lâu càng nhiều.” Tất nhiên, Ami không dám làm ngay lập tức, vì sợ sự thật có thể làm cậu suy sụp.

Tóm lại, có một dãy gồm \(n\) số nguyên dương không giảm \(a_1,\) \(a_2,\) \(a_3,\) \(…,\) \(a_n\) và một số \(k,\) Ami muốn đếm số cặp \((i,\) \(j)\) không trùng nhau mà \(a_i\) \(+\) \(a_j\) \(=\) \(k,\) lưu ý rằng \((i,\) \(j)\) và \((j,\) \(i)\) được tính là \(1\) cặp.

Input

• Dòng đầu gồm \(2\) số nguyên dương \(n\) và \(k\) \((n\) \(\leq\) \(10^6,\) \(k\) \(\leq\) \(10^9).\)
• Dòng thứ hai gồm \(n\) số nguyên dương không giảm \(a_1,\) \(a_2,\) \(a_3,\) \(…,\) \(a_n\) \((a_i\) \(\leq\) \(10^9).\)

Output

• Hãy in ra một số nguyên là kết quá của bài toán.

Example

4 6
1 1 5 5

4

6 5
1 1 1 4 5 5

3

Cho dãy số \(A\) gồm \(n\) phần tử nguyên dương \(A_1,A_2,…,A_n\). Mỗi phần tử có giá trị không vượt quá \(10^9\) và \(n≤ 10^5\). Một cặp số được gọi là cặp tương đồng với \(x\), nếu cặp số này có tổng bằng số \(x\) cho trước nào đó.

Yêu cầu: Hãy đếm xem trong dãy số \(A\) có bao nhiêu cặp số (\(A_i;A_j\)) tương đồng với \(x\) (có nghĩa là \(A_i+ A_j=x\)) với \(i<j\).

Input

• Dòng đầu tiên chứa dãy số \(n,x\) (\(n≤10^5,x≤10^6\)).
• Dòng thứ 2 chứa \(n\) phần tử của dãy số \(A\) (\(A_i≤10^9\)).

Output

• Ghi ra một số nguyên là cặp đôi tương đồng của dãy số.

Example

7 6
1 2 4 3 4 5 3 

4

Khôi vừa viết một ứng dụng hẹn hò mang tên Fake love. Ứng dụng đang có \(n\) bạn nữ, \(m\) bạn nam đang sử dụng, biết rằng 2 người nam nữ sẽ chỉ thấy hợp nhau nếu độ chênh lệch cân nặng của họ không vượt quá \(k\). Qua một số thuật toán, ứng dụng của của Khôi sẽ xếp các nam nữ hợp nhau thành các couple. Vì muốn biết ứng dụng của mình đã tối tưu chưa, nên Khôi hỏi bạn có nhiều nhất bao nhiêu couple có thể có (1 nam chỉ có ghép thể với 1 bạn nữ, ngược lại cũng vậy).

Input

• \(n, m, k(1 \leq n, m\leq 2*10^5, 0 \leq k \leq 10^9)\).
• \(n\) số nguyên, \(1 \leq a_i\leq10^9\) cân nặng của các bạn nữ.
• \(m\) số nguyên, \(1 \leq b_i\leq10^9\) cân nặng của các bạn nam.

Output

• số couple.

Example

4 3 5
60 45 80 60
30 60 75 

2

Gần đến tết Tân Sửu 2021, \(n\) bạn học sinh lớp A5 khóa 16-19 đang họp lớp và quyết định rằng Chủ nhật tuần này sẽ đi chơi công viên Châu Phi.

Ở trò chơi "Tàu lượn siêu tốc", mỗi hàng của tàu sẽ chứa tối đa hai chỗ ngồi, và tổng cân nặng hai chỗ ngồi này có giá trị không quá \(x\).

Vậy khi đến chơi tàu lượn siêu tốc, tàu lượn trên phải có ít nhất bao nhiêu hàng ngồi để tất cả các bạn A5 có thể lên chơi 1 lúc.

Input

• \(n, x(1 \leq n\leq 2*10^5, 1 \leq x \leq 10^9)\).
• \(n\) số nguyên, \(1 \leq a_i \leq x\) cân nặng của bạn thứ i .

Output

• số hàng ngồi

Example

4 10
7 2 3 9 

3

Cho dãy số \(A\) gồm \(n\) phần tử nguyên dương \(A_1, A_2, …, A_n\). Mỗi phần tử có giá trị không vượt quá \(10^9\) và \(1 \lt n \leq 5000\). Một bộ ba số được gọi là bộ số tam giác, nếu ba số này tạo thành ba cạnh của một tam giác nào đó.

Yêu cầu: Hãy đếm xem trong dãy \(A\) có bao nhiêu bộ số tam giác (\(A_i, A_j, A_k\)) với \(i, j, k\) đôi một khác nhau.

Input

• Dòng đầu là số \(n\).
• Dòng tiếp theo là các phần tử của dãy \(A\), mỗi phần tử cách nhau một dấu cách.

Output

• Ghi ra số lượng bộ số tam giác.

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(n \leq 100\).
• Subtask \(2\) (\(30\%\) số điểm): \(100 \lt n \leq 1000\).
• Subtask \(3\) (\(40\%\) số điểm): \(1000 \lt n \leq 5000\).

Example

5
4 3 1 5 7 

3

Cho một mảng số nguyên \(A\) có \(N\) phần tử, mảng này đã được sắp xếp tăng dần. Hãy tìm vị trí của hai phần tử khác nhau bất kỳ sao cho tổng của chúng có giá trị là \(X\). Nếu trong dãy \(A\) không tồn tại hai phần tử khác nhau có tổng là \(X\) thì in ra "No solution".

Input

• Dòng đầu chứa 2 số nguyên \(N\) và \(X\).
• Dòng tiếp theo chứa \(N\) số nguyên \(A_i\).

Output

• Hai vị trí \(i\) và \(j\) khác nhau sao cho tổng ở hai vị trí này có giá là \(X\). In vị trí phần tử nhỏ hơn trước phần tử lớn hơn.
• Nếu không tồn tại in ra "No solution".

Constants

• \(2 \leq N \leq 10^6\) và \(0 \leq A_i, X \leq 10^9\)

Example

6 16
2 3 5 7 9 12

4 5

Bạn có \(2\) mảng số nguyên không âm được sắp xếp theo thứ tự không giảm \(a\) gồm \(n\) phần tử và \(b\) gồm \(m\) phần tử.

Hãy ghép \(a\) và \(b\) thành một mảng số nguyên \(c\) gồm \(n + m\) phần tử.

Hãy cho biết mảng \(c\) theo thứ tự không giảm.

Constants

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

Example

6 7
1 6 9 13 18 18
2 3 8 13 15 21 25

1 2 3 6 8 9 13 13 15 18 18 21 25

Bạn có \(2\) mảng số nguyên không âm được sắp xếp theo thứ tự không giảm \(a\) gồm \(n\) phần tử và \(b\) gồm \(m\) phần tử.

Mảng \(c\) gồm \(m\) phần tử được xác định như sau:

\(c_i\) = số phần tử trong mảng \(a\) có giá trị nhỏ hơn \(b_i\)

Hãy xác định mảng \(c\)

Constants

• \(1 \leq n, m \leq 10^5\)

• \(0 \leq a_i, b_i \leq 10^9\)

Example

6 7
1 6 9 13 18 18
2 3 8 13 15 21 25

1 1 2 3 4 6 6

Bạn có \(2\) mảng số nguyên không âm được sắp xếp theo thứ tự không giảm \(a\) gồm \(n\) phần tử và \(b\) gồm \(m\) phần tử.

Đếm số cặp \((i, j)\) sao cho \(a_i = b_j\).

Input

• Dòng đầu tiên chứa hai số nguyên dương \(n\) và \(m\) (\(1 \leq n, m \leq 10^5\)).
• Dòng thứ hai chứa \(n\) số nguyên của mảng \(a\) (\(0 \leq a_i \leq 10^9\)).
• Dòng thứ ba chứa \(m\) số nguyên của mảng \(b\) (\(0 \leq b_i \leq 10^9\)).

Output

• In ra một số nguyên duy nhất là số cặp \((i, j)\) thỏa mãn điều kiện đề bài.

Example

8 7
1 1 3 3 3 5 8 8
1 3 3 4 5 5 5

11