Chương 2. Danh sách (Mảng 1 chiều)
Trên một con đường có ~n~ toà nhà. Mỗi toà nhà được sơn bằng một màu Đỏ, Vàng, Xanh hoặc Tím. Người ta muốn sơn lại một số toà nhà (bằng một trong các màu Đỏ, Vàng, Xanh, Tím) sao cho không có hai toà nhà liên tiếp có cùng màu sơn.
Yêu cầu: Tìm số nhà cần sơn lại ít nhất.
Input
- Dòng đầu tiên chứ số nguyên dương ~n (1 \le n \le 10^5)~;
- Dòng thứ hai chứa ~n~ ký tự, mỗi ký tự đại diện cho một toà nhà thuộc một trong ba loại D, V, X.
Output
Ghi ra số lượng nhà cần sơn lại ít nhất
Ví dụ
Sample Input
14
VVXDDDTXVTXDVX
Sample Output
2
Điểm: 10
Cho dãy số nguyên dương ~a_1, a_2, ..., a_n~. Dãy số ~a_i, a_{i+1}, ..., a_j~ thoả mãn ~a_i < a_{i+1} < ... < a_j~, với được gọi là dãy con không giảm của dãy số đã cho và khi đó số ~j-i+1~ được gọi là độ dài của dãy.
Cho dãy số ~u~ xác định bởi: ~u_1 = 1; u_2 = 3; U_k = U_{k-1} + k (k \ge 3)~
Yêu cầu: Trong số các dãy con tăng dần của dãy số đã cho mà các phần tử của nó đều thuộc dãy số ~u~. Hãy tìm dãy con có độ dài lớn nhất.
Input
- Dòng đầu tiên chứa một số nguyên dương ~n (n \le 10^5)~
- Dòng thứ hai chứa n số nguyên dương ~a_i (a_i \le 10^8)~ mô tả dãy số
Output
Ghi ra số nguyên ~d~ là độ dài của dãy con tăng dần tìm được (quy ước rằng nếu không có dãy con nào thoả mãn điều kiện đặt ra thì ~d = 1~)
Ví dụ
Sample Input
8
2 2007 6 6 15 16 3 21
Sample Output
3
Điểm: 10
Cho dãy A gồm n số nguyên ~a_1, a_2, ..., a_n~.
Yêu cầu: Tìm độ dài dãy con liên tiếp dài nhất mà các phần tử âm dương xen kẽ.
Input
- Dòng đầu tiên chứa số n ~(n \le 10^5)~
- Dòng thứ hai chứa ~n~ phần tử của dãy A có giá trị tuyệt đối không vượt quá ~10^9~
Output
Ghi ra số lượng dãy con dài nhất và độ dài dãy con tìm được
Ví dụ
Sample Input
10
1 -5 2 0 -6 2 -9 -5 3 7
Sample Output
2 3
Giải thích
Dãy con đan dấu có độ dài dài nhất là 3. Có 2 dãy con độ dài 3 là 1, -5, 2 và -6, 2, -9
Điểm: 10
Cho dãy A gồm n số nguyên ~a_1, a_2, .. a_n~
Yêu cầu: Tìm độ dài dãy con liên tiếp dài nhất, mà các phàn tử gồm toàn số nguyên tố.
Input
- Dòng đầu tiên chứa số ~n (n \le 10^4)~
- Dòng thứ hai chứa n phần tử của dãy A có giá trị tuyệt đối không vượt quá ~10^9~
Output
Ghi ra số lượng dãy con dài nhất và độ dài dãy con tìm được
Ví dụ
Sample Input
10
12 11 7 3 8 8 17 29 2 1
Sample Output
2 3
Điểm: 10
Cho dãy A gồm n số nguyên ~a_1, a_2, .. a_n~
Yêu cầu: Tìm độ dài dãy con liên tiếp dài nhất, mà các phàn tử gồm toàn số nguyên tố.
Input
- Dòng đầu tiên chứa số ~n (n \le 5~ x ~10^5)~
- Dòng thứ hai chứa n phần tử của dãy A có giá trị tuyệt đối không vượt quá ~10^6~
Output
Ghi ra số lượng dãy con dài nhất và độ dài dãy con tìm được
Ví dụ
Sample Input
10
12 11 7 3 8 8 17 29 2 1
Sample Output
2 3
Cho dãy a gồm n số nguyên ~a_1, a_2, ..., a_n~. Đưa ra số lần xuất hiện của các giá trị trong dãy.
Input
- Dòng đầu tiên chứa số nguyên dương ~n~ ~(1 \le n \le 2~x~10^5)~
- Dòng thứ hai chứa ~n~ số nguyên không âm ~a_1, a_2, ..., a_n~ (~0 \le a_i \le 10^6~)
Output
Với mỗi giá trị, đưa ra số lần xuất hiện của giá trị đó trong dãy, theo thứ tự tăng dần.
Ví dụ
Sample Input
7
2 2 7 2 2 7 7
sample Output
2 4
7 3
Cho dãy ~a~ gồm ~n~ số nguyên ~a_1, a_2, ..., a_n~.
Yêu cầu: Hãy đưa ra giá trị có số lần xuất hiện nhiều nhất trong dãy
Input
- Dòng đầu tiên chứa số nguyên dương ~n (1 \le n \le 2~x~10^5~)
- Dòng thứ hai chứa ~n~ số nguyên không âm ~a_1, a_2, ..., a_n (0 \le a_i \le 10^6)~
Output
Ghi ra số có số lần xuất hiện nhiều nhất trong dãy. Đưa ra giá trị nhỏ nhất nếu có nhiều kết quả.
Ví dụ
Sample Input
8
2 2 7 2 2 3 7 7
Sample Output
2
Cho xâu S. Hãy đếm xem xâu S có bao nhiêu kí tự chữ cái, chữ số khác nhau.
Input
Một dòng duy nhất chứa xâu S tối đa 255 ký tự.
Output
Ghi ra tổng số chứ cái, chữ số khác nhau trong S (chữ cái in thường, in hoa là không phân biệt)
Ví dụ
Sample Input
Abcdea 96hjab
Sample Output
9
Điểm: 10
Cho một dãy gồm n số nguyên, hãy đếm xem có bao nhiêu số xuất hiện đúng 2 lần trong dãy..
Input
- Dòng 1: Số nguyên n (~1 \le n \le 10^5~)
- Dòng 2: n số nguyên ~a_1, a_2, ..., a_n~
Output
In ra số lượng giá trị xuất hiện đúng 2 lần.
Ví dụ
Sample Input
7
1 2 3 4 2 3 3
Sample Output
1
Điểm: 10
Cho một dãy gồm n số nguyên, hãy tìm độ dài của dãy con tăng liên tiếp dài nhất.
Một dãy con tăng liên tiếp là dãy thoả mãn:
a[i] < a[i+1]
và các phần tử phải đứng cạnh nhau trong mảng.
Input
- Dòng 1: Số nguyên n (~1 \le n \le 10^5~)
- Dòng 2: n số nguyên ~a_1, a_2, ..., a_n~
Output
In ra độ dài dãy tăng liên tiếp dài nhất.
Ví dụ
Sample Input
8
1 2 3 2 3 4 5 1
Sample Output
4
Điểm: 10
Cho một mảng gồm n số nguyên. Bạn được phép đổi vị trí các phần tử trong mảng (hoán đổi tự do). Hãy kiểm tra xem có thể sắp xếp lại mảng sao cho các vị trí chẵn (tính từ 0) chứa số chẵn và các vị trí lẻ chứa số lẻ hay không.
Input
- Dòng đầu tiên chứa số nguyên ~n (1 \le n \le 1000)~
- Dòng thứ hai chứa n số nguyên ~a_1, a_2, ..., a_n (|a_i| \le 10^6)~
Output
- In ra "YES" nếu có thể sắp xếp lại như yêu cầu
- In ra "NO" nếu không thể
Ví dụ
Sample Input
6
2 1 4 3 6 5
Sample Output
YES
Giải thích
vì ta có thể sắp: 2 1 4 3 6 5 chỉ số chẵn là 2 4 6 (đều chẵn), chỉ số lẻ là 1 3 5 (đều lẻ)
Bạn được cho một chuỗi DNA - là một xâu chỉ gồm các ký tự A, C, G và T. Nhiệm vụ của bạn là tìm độ dài của chuỗi con liên tiếp dài nhất mà chỉ gồm một loại ký tự duy nhất.
Input
Dòng duy nhất chứa một chuỗi gồm ~n~ ký tự (mỗi ký tự là A, C, G hoặc T)
Output
In ra một số nguyên duy nhất: Độ dài của chuỗi con liên tiếp dài nhất chỉ gồm một ký tự duy nhất.
Ràng buộc ~1 \le n \le 10^6~
Ví dụ
Sample Input
ATTCGGGA
Sample Output
3
Điểm: 10
Cho ~n~ số nguyên, với mỗi số, bạn cần đếm xem nó có bao nhiêu ước số.
Ví dụ: Với ~x = 18~, đáp án là 6, vì ước số của 18 là: 1, 2, 3, 6, 9, 18
Dữ liệu vào:
Dòng đầu tiên chứa số nguyên n
~n~ dòng tiếp theo, mỗi dòng chứa một số nguyên ~x~
Dữ liệu ra
Với mỗi số ~x~, in ra số lượng ước số của nó, mỗi kết quả trên một dòng.
Ràng buộc:
~1 \le n \le 10^5~
~1 \le x \le 10^6~
Ví dụ
Sample Input
3
16
17
18
Sample Output
5
2
6
Điểm: 10
Cho dãy A gồm n phần tử.
Yêu cầu: Hãy chia dãy A thành nhiều đoạn con liên tiếp nhất có tổng bằng nhau?
Input
- Dòng đầu chứa số ~n~ ~(1 \le n \le 10^3)~
- Dòng thứ hai chứa ~n~ phần tử của dãy số ~A~ ~(0 \le A_i \le 10^9)~
Output
Số lượng đoạn con lớn nhất có thể chia
Ví dụ
Sample Input
10
0 4 1 0 5 5 1 4 0 0
Sample Output
4
Điểm: 10
Nhập vào mảng A có N phần tử là các số nguyên, hãy liệt kê các chỉ số i trong mảng thỏa mãn: Tổng các phần tử bên trái i và tổng các phần tử bên phải i là số nguyên tố.
Nếu không tìm được vị trí nào thoả mãn, in ra 0
Ràng buộc: ~1 \le N \le 10^3; -10^6 \le A[i] \le 10^6~
Input
5
53 5 69 47 19
Output
3
Điểm: 10
Cho mảng các số nguyên A gồm N phần tử, hãy liệt kê các số là số Fibonacci có trong mảng
Ràng buộc: ~1 \le N \le 10^6; 0 \le A[i] \le 10^{18}~
Input
6
2 3 4 8 9 10
Output
2 3 8
Điểm: 10
Cho mảng A gồm N phần tử là số nguyên, tìm ước chung lớn nhất của tất cả các phần tử trong mảng (là số lớn nhất mà tất cả các số trong mảng đều chia hết)
Ràng buộc: ~1 \le N \le 10^6, 0 \le A[i] \le 10^6~
Input
6
2 4 6 8 10 8
Output
2
Điểm: 10
Cho mảng số nguyên A gồm N phần tử, hãy tìm độ chênh lệch nhỏ nhất giữa 2 phần tử bất kỳ trong mảng
Input
- Dòng đầu tiên là số nguyên dương N
- Dòng thứ hai gồm N các số nguyên
Ràng buộc
~1 \le N \le 1000; 0 \le A[i] \le 10^6~
Output
In ra độ chênh lệch nhỏ nhất giữa 2 phần tử bất kỳ trong mảng
Ví dụ
Sample Input
5
4 1 6 2 10
Sample Output
1
Sample Input 2
6
-5 1 -2 7 4 -3
Sample Output 2
1
Cho mảng A[] gồm N số nguyên không âm và số K. Nhiệm vụ của bạn là hãy chia mảng A[] thành hai mảng con có kích cỡ K và N-K sao cho hiệu giữa tổng hai mảng con là lớn nhất.
Ví dụ : mảng A[] = {8, 4, 5, 2, 10}, K=2 ta có kết quả là 17 vì mảng A[] được chia thành hai mảng {4, 2} và { 8, 5,10} có hiệu của hai mảng con là 23-6=17 là lớn nhất.
Input
- Dòng đầu tiên là 2 số N và K
- Dòng thứ hai là N số trong mảng A
Giới hạn
- ~1 \le k \le N \le 10^5~
- ~0 \le A[i] \le 10^7~
Output
In ra hiệu lớn nhất có thể
Ví dụ
Sample Input
5 2
8 4 5 2 10
Sample Output
17
Điểm: 10
Cho mảng số nguyên A[] gồm N phần tử, kiểm tra xem mảng có đối xứng hay không?
Input
- Dòng đầu tiên là số nguyên dương N
- Dòng thứ 2 gồm N số nguyên viết cách nhau một vài khoảng trắng
Giới hạn
- ~1 \le N \le 10^6~
- ~0 \le A[i] \le 10^6~
Output
In ra YES hoặc NO tương ứng với mảng đối xứng hoặc không.
Ví dụ
Sample Input
5
1 2 3 2 1
Sample Output
YES
Sample Input 2
6
1 2 3 2 1 1
Sample Output 2
NO
Điểm: 20
Cho mảng A gồm N phần tử, hãy tìm 2 chỉ số i, j khác nhau sao cho ~0 \le i < j < N~ và trị tuyệt đối của tổng của 2 phần tử A[i] và A[j] đạt giá trị lớn nhất.
Input
- 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
- ~2 \le N \le 10^6~
- ~10^9 \le A[i] \le 10^9~
Output
In ra đáp án của bài toán là chỉ số i và j thoả mãn
Sample Input 1
5
-1 -2 -3 10 -5
Sample Output 1
0 3
Sample Input 2
5
-1 -2 -3 8 -5
Sample Output 2
2 4
Điểm: 20
Cho dãy số A[] gồm có N phần tử. Ở mỗi thao tác bạn có thể tăng các phần tử trong mảng lên 1 vài đơn vị, hãy xác định số đơn vị tối thiểu cần thêm vào các phần tử trong mảng sao cho mảng trở thành một dãy tăng chặt. Ví dụ dãy 1 2 3 7 8 là một dãy tăng chặt, nhưng dãy 1 2 2 7 8 không phải là một dãy tăng chặt.
Input
- 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 \le N \le 10^6~,
- ~0 \le A[i] \le 10^6~
Output
In ra số đơn vị tối thiểu cần thêm vào các phần tử trong mảng để dãy tăng chặt
Ví dụ
Sample Input
5
3 2 7 8 1
Sample Output
10
Điểm: 20
Bạn được cho tất cả các số nguyên từ 1 đến n, ngoại trừ một số bị thiếu. Nhiệm vụ của bạn là tìm ra số bị thiếu đó.
Input
- Dòng đầu tiên chứa một số nguyên n — số lượng số cần có (bao gồm cả số bị thiếu).
- Dòng thứ hai chứa n - 1 số nguyên khác nhau, mỗi số nằm trong đoạn từ 1 đến n.
Output
In ra số nguyên duy nhất bị thiếu
Ràng buộc
~2 \le n \le 2~x~10^5~
Ví dụ
Sample Input
5
2 3 1 5
Sample Output
4
Điểm: 20
Tèo và Tý vào Trung tâm thương mại để mua đồ. Khi vào siêu thị, 2 bạn thấy một thang cuốn và ở các bậc thang được đánh số thứ tự từ 1 đền n, trên mỗi bậc thang có ghi một số nguyên dương. Tuy nhiên, do thang cuốn liên tục lặp lại nên các bậc thang cũng lặp lại theo đúng trật tự. Tý đố Tèo tính tổng của m bậc thang liên tiếp bắt đầu từ bậc thang thứ k, nếu Tèo tính đúng sẽ được Tý mua cho một món quà trong Trung tâm thương mại.
Hãy giúp Tèo tính toán tổng này để nhận được quà từ Tý.
Yêu cầu: Nhập vào từ bàn phím
- Dòng thứ nhất chứa các số nguyên dương n, m, k cách nhau bởi dấu cách (~m, k \le 10^8; n \le 10^6~)
- Dòng thứ hai chứa n số nguyên dương ~a_1, a_2, a_3, ...a_n~ cách nhau bởi dấu cách là các số ghi trên các bậc thang từ bậc thứ nhất đến bậc thứ n của tháng cuối (~1 \le a_i \le 10^9~)
Kết quả: In ra màn hình số nguyên dương duy nhất là kết quả bài toán chia lấy dư cho ~10^9 + 7~
Input
6 8 3
3 4 2 1 4 5
Output
22
Giải thích
8 số nguyên liên tiếp bắt đầu từ vị trí số 3 là 2 1 4 5 3 4 2 1
Kết quả: (2 + 1 + 4 + 5 + 3 + 4 + 2 + 1) mod ~10^7~ = 22
Điểm: 20
Nhập vào một mảng A gồm các số nguyên có N phần tử, hãy chuyển các số dương lên đầu mảng theo cách làm xáo trộn ít nhất.
Ràng buộc: ~0 < N \le 10^6; -10^6 \le A[i] \le 10^6~
Dữ liệu vào gồm 2 dòng, dòng thứ nhất là số lượng N phần tử, dòng thứ 2 lần lượt là N phần tử trong mảng A.
Input 01
5
-1 2 -3 4 5
Output 01
5 2 4 -3 -1
Input 02
5
1 2 -2 3 -5
Output 01
1 2 3 -2 -5
Điểm: 20
Nhập vào một mảng các số nguyên dương A có N phần tử, in ra số nguyên dương nhỏ nhất chưa xuất hiện trong mảng.
Ràng buộc: ~0 < N \le 10^6; 0 < A[i] \le 10^6~
Dữ liệu vào gồm 2 dòng, dòng thứ nhất là số lượng N phần tử, dòng thứ 2 lần lượt là N phần tử trong mảng A.
Input 01
8
3 3 4 6 6 7 8 9
Output 01
5
Lưu ý: Số nguyên dương cần in phải nằm trong khoảng từ min tới max + 1 của mảng
Input 02
9
2 2 3 4 5 6 7 8 9
Output 01
10
Điểm: 20
Cho mảng A có n phần tử nguyên dương, hãy tìm dãy con liên tiếp có k phần tử và có tổng các phần tử là lớn nhất
Ràng buộc: ~1 \le N, K \le 10^7; 1 \le A[i] \le 10^9~
In ra tổng lớn nhất và dãy con có tổng lớn nhất.
Sample Input
6 3
3 2 1 6 -5 12
Sample Output
13
6 -5 12
Giải thích: Tổng bằng 13 và dãy con đó là 6, -5, 12.
Điểm: 20
Nhập vào một mảng A có N phần tử, in ra giá trị lớn thứ hai của mảng và chỉ số của các số hạng đạt giá trị lớn hai trong mảng.
Input
Dòng thứ nhất Nhập N, từ dòng thứ 2 sẽ lần lượt nhập N phần tử của mảng A
Output
In ra phần tử lớn thứ hai và vị trí của các phần tử lớn thứ hai trong mảng A
Ràng buộc: ~0 < N \le 10^6, -10^6 \le A[i] \le 10^6~
Ví dụ
Sample Input
9
4 3 4 2 2 4 2 3 4
Sample Output
3 2 8