Chuyên đề - Đếm phân phối

Cho một dãy gồm \(n\) số nguyên dương \(A_1,A_2,\ldots,A_n\).

Yêu cầu: Hãy in ra tất cả các số trong mảng \(A\) cùng với số lần xuất hiện của chúng.

Input

• Dòng đầu chứa số \(n\) (\(n\leq 10^5\)).
• Dòng thứ hai chứa \(n\) số nguyên dương \(A_1,A_2,\ldots,A_n\) (\(A_i\leq 10^6\)).

Output

• Gồm \(n\) dòng, mỗi dòng ghi số hạng thứ \(A_i\) và số lần xuất hiện của chúng.

Example

9
2 3 1 2 3 4 5 4 3

2 2
3 3
1 1
2 2
3 3
4 2
5 1
4 2
3 3

Cho một dãy gồm \(n\) số nguyên dương \(A_1,A_2,\ldots,A_n\)..

Yêu cầu: Hãy in ra các phần tử của mảng theo thứ tự tăng dần cùng với số lần xuất hiện của chúng, các số trùng nhau thì chỉ ghi một lần.

Input

• Dòng đầu chứa số \(n\) (\(n\leq 10^5\)).
• Dòng thứ hai chứa n số nguyên dương \(A_1,A_2,\ldots,A_n\) (\(A_i\leq 10^6\)).

Output

• Gồm \(n\) dòng, mỗi dòng ghi số hạng thứ \(A_i\) và số lần xuất hiện của chúng.

Example

9
2 3 1 2 3 4 5 4 3

1 1
2 2
3 3
4 2
5 1

Cho một mảng gồm \(n\) số nguyên dương \(a_1,\) \(a_2,\) \(a_3,\) \(...,\) \(a_n.\)

Yêu cầu : Hỏi có bao nhiêu cặp số bằng nhau ? \((\)Bao nhiêu cặp \(a_i\) \(=\) \(a_j\) với \(i\) \(\neq\) \(j,\) \((ai,\) \(aj)\) và \((aj,\) \(ai)\) chỉ được tính là \(1\) cặp\().\)

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

• 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 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

Levi mở cửa hàng bán quần áo, anh ta có \(1\) đống tất mà cần phải ghép đôi theo màu để bán. Mỗi màu có thể được biểu diễn bởi \(1\) số nguyên dương.

Yêu cầu : Hãy xác định giúp anh ta biết anh ta có thể có tối đa bao nhiêu đôi tất cùng màu.

Input

• Dòng đầu tiên gồm \(1\) số nguyên \(n\) đại diện cho số chiếc tất \((1\) \(\leq\) \(n\) \(\leq\) \(100).\)
• Dòng thứ hai gồm \(n\) số nguyên dương, mỗi số đại diện cho \(1\) màu tất \((\)các số này không lớn hơn \(100)\)

Output

• Gồm \(1\) số duy nhất là kết quả của bài toán.

Example

7
1 2 1 2 1 3 2

2

Nguồn: hackerrank

Một lớp học nọ của Boss Small có \(N\) học sinh. Một ngày đẹp trời, Boss Small nhận thấy số học sinh đi học chỉ có \(M\) người, ít hơn \(N\) nên Boss quyết định nhờ bạn điểm danh các học sinh trong lớp. Hãy viết một chương trình cho biết số thứ tự của các học sinh vắng mặt theo thứ tự tăng dần.

Biết rằng, lớp học đánh số thứ tự cho học sinh từ \(1\) cho đến \(N\).

Input

• Dòng đầu tiên chứa hai số nguyên dương lần lượt là \(N\) và \(M\) \((1 \leq M < N \leq 10^5)\)
• Dòng thứ hai chứa \(M\) số nguyên khác nhau từng đôi một, có giá trị trong đoạn \([1, N]\).

Output

• In ra một danh sách các số nguyên, là số thứ tự của những học sinh vắng mặt, theo thứ tự tăng dần.

Example

5 3
5 2 3 

1 4

2 1
2 

1

Cho một xâu ký tự \(S\) chỉ gồm các chữ cái thường a..z. Xâu đối xứng là xâu kí tự mà khi viết từ phải qua trái hay từ trái qua phải thì xâu đó không thay đổi. Ví dụ: \(madam\), \(ioi\) là các xâu đối xứng.

Yêu cầu: Với xâu ký tự \(S\) cho trước, hãy tính số ký tự bỏ đi ít nhất để các ký tự còn lại có thể sắp xếp được thành một xâu đối xứng.

Ví dụ:

• Cho xâu aammmda thì cần bỏ 2 ký tự a và m thì xâu còn lại là ammda và xếp lại thành madam là xâu đối xứng.
• Cho xâu aaabbcc thì không cần bỏ ký tự thì xâu đó xếp lại thành bcaaacb là xâu đối xứng.

Input

• Một xâu ký tự \(S\) có \(n\) ký tự (\(n \le 10^5\)) chỉ gồm các ký tự chữ cái thường a..z.

Output

• Một số nguyên là số lượng ký tự ít nhất cần bỏ để các ký tự còn lại có thể sắp xếp được thành một xâu đối xứng.

Scoring

• Subtask \(1\): (\(30\%\) số điểm): chỉ chứa 2 ký tự a và b.
• Subtask \(2\): (\(30\%\) số điểm): chỉ chứa 3 loại ký tự bất kỳ.
• Subtask \(3\): (\(40\%\) số điểm): trường hợp còn lại.

Example

aammmda

2

aaabbcc

0

Conan đang trong một vụ án cực kì hóc búa, đã có đến 2 vụ án mạng xảy ra. Tại hiện trường 2 vụ án đều để lại dòng chữ kì lạ. Có vẻ như đó chính là gợi ý mà hung thủ để lại. Hung thủ dường như đang cố thách thức vị thám tử lừng danh của chúng ta. Bằng tài năng suy luận tài tình của mình, Conan đã khám phá đã ra được gợi ý của hung thủ chính là sự tương đồng của 2 dòng chữ đó. Tuy nhiên các dòng chữ rất dài, Conan giỏi suy luận nhưng lại không giỏi lập trình. Bạn là một lập trình viên giỏi, bạn hãy giúp Conan nhé.

Yêu cầu: Cho 2 chuỗi kí tự \(a\) và \(b\). Hãy xác định xem chuỗi \(a\) và \(b\) giống nhau bao nhiêu kí tự?

Input

• Dòng thứ nhất là chuỗi kí tự \(a (1 \leq |a| \leq 10^{5})\).
• Dòng thứ hai là chuỗi kí tự \(b\) \((1 \leq |b| \leq 10^{5})\).
• Các chuỗi chỉ gồm các kí tự từ \(\texttt{a}\) \(\rightarrow\) \(\texttt{z}\), \(|x|\) là số lượng ký tự của chuỗi \(x\).

Output

• Gồm một dòng duy nhất là số lượng kí tự giống nhau.

Example

aaabb
baa

3

Cho dãy số nguyên dương gồm \(N\) phần tử \(a_1,a_2,...,a_N\). Đếm số cặp chỉ số \((i,j)\) thỏa mãn:

• \(1 \le i \le j \le n\);
• \(a_i + a_j^2=K\) với \(K\) cho trước.

Input

• Dòng đầu tiên gồm 2 số nguyên dương \(N\) và \(K\) \((N \le 10^5,K \le 10^9)\)
• Dòng thứ hai chứa \(N\) số nguyên dương \(a_1,a_2,...,a_N\) \((a_i \le 10^9)\)

Output

• In ra số cặp \((i,j)\) thỏa mãn.

Example

3 5
1 2 2 

2

Sau đây là một câu chuyện có thật do Quandeptrai bịa ra:

Quandeptrai là một chàng trai từ nhỏ đã rất đẹp trai, hào hoa, phong độ, rất nhiều cô gái theo đuổi. Một hôm, trong lúc đi chơi với bạn gái của mình(Thảo xinhgai) , cô bạn gái của Quandeptrai nhờ cậu giúp cô giải một bài tập về xâu kí tự. Khổ nỗi, Quandeptrai không giỏi môn tin lắm, cho nên cậu đã nhờ các anh em coder giải giúp cậu bài tập này:

Xâu hoàn hảo là xâu có độ dài lớn hơn hoặc bằng 2, trong đó kí tự đầu và kí tự cuối của xâu bằng nhau. Cho một xâu \(S\) có độ dài \(N\), đếm số lượng xâu hoàn hảo trong xâu \(S\).

Input

• Dòng đầu tiên là số nguyên dương \(N\) – độ dài của xâu \(S\) \((n \leq 10^6)\)

• Dòng thứ 2 là xâu S chỉ gồm các kí tự chữ cái latinh in thường.

Output

• Ghi ra một số nguyên duy nhất là số lượng xâu hoàn hảo trong xâu \(S\).

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(N\leq 10^3\)
• Subtask \(2\) (\(70\%\) số điểm): \(N\leq 10^6\)

Example

6
abcacb 

3

Một xâu được gọi là xâu đối xứng nếu đọc xâu đó từ trái sang phải hoặc đọc từ phải sang trái đều như nhau. Ví dụ: \("aba", "xyyx", "zz"\) là xâu đối xứng. Còn \("abc", "xyzy", "contest"\) không là xâu đối xứng.

Cho xâu \(s\) có độ dài \(N\) và chỉ bao gồm các chữ cái latin in thường, hãy xác đinh xem có tồn tại một xâu con liên tiếp của \(s\) có độ dài chẵn và là xâu đối xứng hay không. Nói cách khác, nếu kí hiệu \(|s|\) là độ dài của xâu \(s\), hãy xác đinh xem có tồn tại hai chỉ số \(i\) và \(j\) sao cho:

• \(1 \lt i \lt j \lt |s|\).
• \(j — i + 1\) là một số chẵn.
• \(s_i,s_{i+1},\dots,s_j\) là một xâu đối xứng.

Input

• Dòng đầu tiên ghi một số nguyên dương \(T\) - số bộ dữ liệu vào \((T \lt 5)\).
• \(T\) dòng tiếp theo, dòng thứ \(i\) chứa xâu \(s (|s| \lt 10^5)\) tương ứng với bộ dữ liệu thứ \(i\).

Output

• Với mỗi bộ dữ liệu, nếu tồn tại một xâu con liên tiếp của \(s\) có độ dài chẵn và là xâu đối xứng thì in ra "YES". Ngược lại thì in ra "NO".

Scoring

• Subtask \(1\) (\(50\%\) số điểm): \(|s| \lt 100\).
• Subtask \(2\) (\(50\%\) số điểm): không có ràng buộc gì thêm.

Example

2
abdccdac
notapalindrome 

YES
NO

kid2201 có n hộp lập phương trống, hộp thứ i có kích thước là \(a_i\).

kid2201 có thể bỏ hộp thứ i vào trong hộp thứ j nếu như:

• hộp thứ i chưa được bỏ vào bất kì hộp nào
• hộp thứ j chưa chứa bất kì hộp nào bên trong
• hộp thứ i nhỏ hơn hộp thứ j (\(a_i < a_j\))

kid2201 là một học sinh chuyên về thuật toán, muốn bỏ các hộp vào nhau sao cho số lượng hộp có thể nhìn thấy là ít nhất có thể.

Input

• Dòng đầu tiên là số nguyên \(n\) \((1\le n\le 100000)\) - số lượng hộp lập phương
• Dòng thứ hai gồm n số nguyên \(a_1, a_2, ..., a_n\) (\(1\le a_i\le 10^9\)).

Output

• In ra số lượng hộp tối thiểu có thể nhìn thấy sao khi sắp xếp các hộp vào nhau.

Example

3
1 2 3

1

4
4 3 4 2

2