Luyện tập set, map

Cho dãy \(a\), số nguyên \(n\) phần tử, đếm số số xuất hiện trong dãy đó.

Input

• Dòng đầu gồm số nguyên n (\(1 \leq n \leq 200000\))
• Dòng thứ 2 gồm n số nguyên (\(-10^9 \leq a_{i} \leq 10^{9}\))

Output

• Kết quả.

Example

5
1 3 2 3 2

3

Cho một set \(\mathcal{X}\).

Các bạn có thể vào link này để tìm hiểu về CTDL \(set\) trong C++. (link đã chết) (Update 3/12/2022: link đã sống lại)(Update 5/4/2025: Link lại chết rồi)

Nhập nhiều dòng, mỗi dòng nhập hai số nguyên \(\Gamma\) và \(\Delta\).

Ở mỗi lần nhập, hãy đưa vào set số nguyên lớn hơn trong hai số \(\Gamma\) và \(\Delta\). Nếu \(\Gamma = \Delta\), đưa vào set \(1\) trong \(2\) số đó.

Nhập hai số \(0\) (cách nhau 1 dấu cách) để kết thúc quá trình nhập.

Yêu cầu: In ra set \(\mathcal{X}\) sau khi nhập xong, mỗi số trên \(1\) dòng, theo thứ tự tăng dần.

Example

3 2
4 4
8 9
0 0

3
4
9

92 17
92 19
0 0

92

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

Cho n số nguyên a[1], a[2], ..., a[n].

In ra số xuất hiện nhiều lần nhất và số lần xuất hiện của nó.

Nếu có nhiều kết quả in ra số xuất hiện nhiều lần nhất có giá trị nhỏ nhất

Input:

Dòng 1: số nguyên dương n \((n \le 10^5)\)

Dòng 2: n số nguyên a[1], a[2], ..., a[n] \((-10^{16} \le \texttt{a[i]} \le 10^{16})\)

Output:

In ra số nhỏ nhất xuất hiện nhiều lần nhất và số lần xuất hiện của nó.

Sample Input

5
1 2 1 2 3

Sample Output

1 2

Cho n số nguyên a[1], a[2], ..., a[n].

In ra các số xuất hiện trong mảng theo thứ tự tăng dần và số lần xuất hiện của chúng.

Input:

Dòng 1: số nguyên dương n \((n <= 10^5)\)

Dòng 2: n số nguyên a[1], a[2], ..., a[n] ( -10^{16} <= a[i] <= 10^{16} \ )

Output:

Mỗi dòng in ra: số xuất hiện trong mảng và số lần xuất hiện của chúng.

Sample Input

 5
1 2 1 2 3

Sample Output

1 2
2 2 
3 1

Cho một xâu \(S\) được chỉ gồm các ký tự chữ cái thường \(‘a’… ‘z’\) được gọi là xâu chẵn nếu số lần xuất hiện của từng chữ cái trong xâu \(S\) là số chẵn.

Input

• Một dòng chứa duy nhất xâu \(S\) có số lượng ký tự không quá 255 ký tự.

Output

• Nếu xâu \(S\) là xâu chẵn thì in ra "Yes". Ngược lại thì in ra "No".

Example

adccda

Yes

adcccdaa

No

Hãy viết chương trình thực hiện nhiệm vụ sau:

Nhập vào từ bàn phím một xâu kí tự \(S\), hãy in ra số kí tự chỉ xuất hiện đúng 1 lần trong xâu \(S\).

Input

• Dòng đầu tiên và duy nhất chứa 1 xâu \(S\) (chỉ chứa các kí tự trong tập \(\{a,b,\dots z\}\), không chứa dấu cách) \((|S| \leq 255)\).

Output

• In ra số kí tự chỉ xuất hiện đúng 1 lần trong xâu \(S\).

Example

abbacdmedc 

2

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.

Dữ liệu vào

Dòng đầu tiên gồm 1 số nguyên n đại diện cho số chiếc tất (1≤n≤100000)

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 \(10^{16}\))

Kết quả

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

Sample Input

7
1 2 1 2 1 3 2

Sample Output

2

Gợi ý: Bài này các bạn đã từng làm bằng đếm phân phối rồi, nhưng với giới hạn các số \(<= 10^{16}\) thì bắt buộc phải sử dụng map mới AC được

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 tập hợp rỗng, bạn sẽ lần lượt thực hiện N thao tác. Có hai loại thao tác được thực hiện:

• Thao tác 1 có dạng (1, \(x\)) : thêm số \(x\) vào tập hợp.
• Thao tác 2 có dạng (2, \(x\)): loại bỏ một số \(x\) ra khỏi tập hợp, dữ liệu luôn đảm bảo tồn tại ít nhất một số \(x\) trước khi thực hiện thao thao tác này.

Sau mỗi lần thực hiện thao tác, hãy đưa ra ước chung lớn nhất của tập hợp này. Với trường hợp tập hợp con rỗng hãy in ra số 1.

Input

• Dòng đầu tiên một số tự nhiên \(N\) (\(1 \leq N \leq 1000\)).
• \(N\) dòng tiếp theo, mỗi dòng là gồm 2 số \(t\) và \(x\) với \(t\) là loại thao tác và \(x\) là số cần được xử lí (\(1 \leq t \leq 2\), \(1 \leq x \leq 10^{9}\)).

Output

• Gồm \(N\) dòng là ước chung lớn nhất của tập hợp sau mỗi lần thực hiện một thao tác.

Example

6  
1 8     
1 12     
1 10     
1 8     
2 8     
2 8 

8     
4     
2     
2     
2     
2

Cho một dãy gồm \(n\) số nguyên dương \(a_1,a_2,…,a_n\). Một hàm \(f\) được định nghĩa như sau:

\(f(x)=x*count_a (x)\)

với \(count_a (x)\) là số lần xuất hiện của \(x\) có trong dãy \(a\).

Yêu cầu: Hãy tìm phần tử \(a_i\) có \(f(a_i )\) lớn nhất \((1\le i\le n)\).

Input

• Dòng đầu tiên là số nguyên dương \(n (n\le 10^5 )\).
• Dòng thứ hai gồm n số nguyên dương \(a_1,a_2,…,a_n (a_i\le 10^9)\).

Output

• In ra phần tử \(a_i\) có \(f(a_i )\) lớn nhất \((1\le i\le n)\). Nếu có nhiều kết quả thỏa mãn, in ra kết quả lớn nhất.

Scoring

• 80% test: \(n\le 10^3,a_i\le 10^6\)
• 20% test: không có ràng buộc

Example

5
1 2 3 4 5

5

4
1 2 1 1

1

Trong một lớp học về lập trình mạng khoa CNTT, thầy Tuấn cho các học sinh chơi một trò chơi. Các học sinh phải viết chương trình kết nối với nhau bằng giao thức TCP qua mạng LAN và phải báo cáo lại mình đã kết nối bao nhiêu lần.

Thầy Tuấn có danh sách các lượt kết nối của các cặp học sinh. Lượt kết nối thứ \(i\) cho biết học sinh \(𝑎_𝑖\) kết nối với học sinh \(𝑏_𝑖\) và kết nối \(c_𝑖\) lần.

Hãy giúp thầy Tuấn thống kê các học sinh của mình đã kết nối chính xác bao nhiêu lần.

Input

• Dòng đầu chứa số nguyên \(𝑛 (1 ≤ 𝑛 ≤ 10^4)\) là số lượt kết nối.
• \(n\) dòng tiếp theo, dòng thứ \(i\) gồm hai string \(𝑎_𝑖, 𝑏_𝑖\) và số nguyên \(𝑐_𝑖\) cách nhau bởi các dấu cách. (\(𝑎_𝑖, 𝑏_𝑖\) là tên học sinh, chỉ gồm các kí tự latin thường và không quá 10 kí tự và \(𝑎_𝑖 ≠ 𝑏_𝑖\) , \(1 ≤ 𝑐_𝑖 ≤ 10^9\) là số lần kết nối tại thời điểm này).

Output

• Gồm nhiều dòng, mỗi dòng là tên học sinh và tổng số lần kết nối của học sinh đó, các học sinh được in ra theo thứ tự từ điển.

Example

5
fixers join 15 
yh bones 10
dragon khoi 9
khoi yh 1
dragon yh 5

bones 10
dragon 14
fixers 15
join 15
khoi 10
yh 16

Bạn được cho một dãy số \(a\) gồm \(n\) số nguyên. Nhiệm vụ của bạn là tìm số cặp số \((i,j) \ 1 \leq i \leq j \leq n\) sao cho \(a_i + a_{i+1} + ... + a_j = 0\)

Input

• Dòng đầu tiên chứa số nguyên dương \(n \ (1 \leq n \leq 10^5)\) - là số phần tử của mảng.
• Dòng thứ hai chứa \(n\) số nguyên, số thứ \(i\) là \(a_i\) \(( \mid a_i\mid \leq 10^9)\)

Output

• Số lượng cặp số \((i,j)\) thõa mãn điều kiện trên

Example

4
-3 3 -4 4

3

Cho một dãy số nguyên \(a_1, a_2, a_3, …, a_n\) và một số nguyên \(k\). Một dãy con \(1 \leq i \leq j \leq n\) được gọi là hoàn hảo nếu như \(a_i + a_{i + 1} + a_{i + 2} + … + a_j = k\).

Yêu cầu: Hãy đếm xem có bao nhiêu dãy con hoàn hảo từ dãy đã cho.

Input

• Dòng đầu tiên chứa số \(n \ (n \leq 10^5)\) và \(k \ (|k| \leq 10^4)\) cách nhau bởi dấu cách.
• Dòng tiếp theo chứa \(n\) số nguyên \(a_i \ (|a_i| \leq 10^4)\).

Output

• Một số duy nhất là kết quả tìm được.

Scoring

• Subtask \(1\) (\(50\%\) số điểm): \(n \leq 100\).
• Subtask \(2\) (\(30\%\) số điểm): \(n \leq 5000\).
• Subtask \(3\) (\(20\%\) số điểm): Không có ràng buộc gì thêm.

Example

5 5
1 2 3 4 5 

2

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

Trong buổi hòa nhạc diễn ra tại nhà văn hóa trung tâm có \(N\) khán giả được đánh số thứ tự từ 1 đến \(N\), khán giả thứ \(i (1 \le i \le N )\) có chiều cao là một số nguyên \(A_i (1\le A_i\le 10^9)\). Ban tổ chức muốn chọn ra hai khán già may mắn để trao quà với điều kiện khoảng cách giữa hai số thứ tự của hai người được chọn bằng tổng chiều cao của họ.

Yêu cầu: Hãy đếm số cách khác nhau mà ban tổ chức có thể chọn ra được hai khán giả may mắn, biết rằng hai cách là khác nhau nếu có ít nhất một người được chọn khác nhau.

Input

• Dòng đầu ghi số nguyên dương \(N\);
• Dòng thứ hai ghi lần lượt \(A_1, A_2,...,A_N\) các số cách nhau ít nhất một dấu cách.

Output

• Ghi ra một số duy nhất là số cặp khác nhau mà ban tổ chức có thể chọn được.

Scoring

• Subtask \(1\) (\(50\%\) sổ điểm ): \(2 \le N \le 2000\);
• Subtask \(2\) (\(30\%\) sổ điểm ): \(2000 \le N \le 2 \times 10^5\);
• Subtask \(3\) (\(20\%\) sổ điểm ): \(2 \times 10^5 \le N \le 2 \times 10^6\);

Example

6
2 3 3 1 3 1

3