Chương 2. Danh sách (Mảng 1 chiều)

Giới hạn thời gian: 1.0s / Giới hạn bộ nhớ: 256M

Điểm: 10

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

Giới hạn thời gian: 1.0s / Giới hạn bộ nhớ: 256M

Đ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

Giới hạn thời gian: 1.0s / Giới hạn bộ nhớ: 256M

Đ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


Giới hạn thời gian: 1.0s / Giới hạn bộ nhớ: 256M

Đ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

Giới hạn thời gian: 1.0s / Giới hạn bộ nhớ: 256M

Đ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

Giới hạn thời gian: 1.0s / Giới hạn bộ nhớ: 256M

Điểm: 10

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

Giới hạn thời gian: 1.0s / Giới hạn bộ nhớ: 256M

Điểm: 10

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

Giới hạn thời gian: 1.0s / Giới hạn bộ nhớ: 256M

Điểm: 10

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

Giới hạn thời gian: 1.0s / Giới hạn bộ nhớ: 256M

Đ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

Giới hạn thời gian: 1.0s / Giới hạn bộ nhớ: 256M

Đ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

Giới hạn thời gian: 1.0s / Giới hạn bộ nhớ: 256M

Đ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ẻ)


Giới hạn thời gian: 1.0s / Giới hạn bộ nhớ: 256M

Điểm: 10

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

Giới hạn thời gian: 1.0s / Giới hạn bộ nhớ: 256M

Đ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

Giới hạn thời gian: 1.0s / Giới hạn bộ nhớ: 256M

Đ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

Giới hạn thời gian: 1.0s / Giới hạn bộ nhớ: 256M

Đ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

Giới hạn thời gian: 1.0s / Giới hạn bộ nhớ: 256M

Đ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

Giới hạn thời gian: 1.0s / Giới hạn bộ nhớ: 256M

Đ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

Giới hạn thời gian: 1.0s / Giới hạn bộ nhớ: 256M

Đ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

Giới hạn thời gian: 1.0s / Giới hạn bộ nhớ: 256M

Điểm: 10

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

Giới hạn thời gian: 1.0s / Giới hạn bộ nhớ: 256M

Đ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

Giới hạn thời gian: 1.0s / Giới hạn bộ nhớ: 256M

Đ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

Giới hạn thời gian: 1.0s / Giới hạn bộ nhớ: 256M

Đ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

Giới hạn thời gian: 1.0s / Giới hạn bộ nhớ: 256M

Đ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

Giới hạn thời gian: 1.0s / Giới hạn bộ nhớ: 256M

Đ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


Giới hạn thời gian: 1.0s / Giới hạn bộ nhớ: 256M

Đ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

Giới hạn thời gian: 1.0s / Giới hạn bộ nhớ: 256M

Đ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

Giới hạn thời gian: 1.0s / Giới hạn bộ nhớ: 256M

Đ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.


Giới hạn thời gian: 1.0s / Giới hạn bộ nhớ: 256M

Đ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