Độ khó: Dễ (1/4 điểm)

Giới hạn thời gian: 1 giây · Giới hạn bộ nhớ: 256 MB

Một số nguyên dương $K$ được gọi là số đặc biệt nếu số $K^2 - 1$ chia hết cho $5$. Ví dụ: $4$ là số đặc biệt vì $4^2 - 1 = 15$, chia hết cho $5$; $7$ không phải là số đặc biệt vì $7^2 - 1 = 48$, không chia hết cho $5$.

Yêu cầu: Cho hai số nguyên dương $L, R$ $(2 \le L \le R \le 10^{18})$; hãy đếm các số đặc biệt trên đoạn $[L, R]$.

Dữ liệu (CAU1.INP):

Một dòng chứa hai số nguyên dương $L, R$.

Kết quả (CAU1.OUT):

Một số nguyên duy nhất là kết quả của bài toán.

Ví dụ

Ví dụ 1

2 8

Kết quả:

2

Giải thích ví dụ: trong đoạn $[2, 8]$ có hai số đặc biệt là $4$ ($4^2 - 1 = 15$) và $6$ ($6^2 - 1 = 35$).

Ràng buộc:

• 80% số điểm có $2 \le L \le R \le 10^6$;
• 20% số điểm còn lại không có ràng buộc gì thêm.

Độ khó: Dễ (1/4 điểm)

Giới hạn thời gian: 1 giây · Giới hạn bộ nhớ: 256 MB

Cho xâu kí tự $S$ chỉ chứa các kí tự IN HOA trong bảng chữ cái tiếng Anh.

Yêu cầu: Tìm độ dài lớn nhất của xâu con liên tiếp không chứa một trong các kí tự 'A', 'N', 'H'.

Dữ liệu (CAU2.INP):

• Dòng đầu tiên ghi số nguyên dương $T$, là số lượng xâu ($T \le 10$);
• $T$ dòng tiếp theo, mỗi dòng ghi một xâu có độ dài không quá $10^5$ kí tự.

Kết quả (CAU2.OUT):

Ghi ra $T$ dòng, mỗi dòng một số nguyên là độ dài xâu con liên tiếp tìm được theo yêu cầu, nếu không có xâu con liên tiếp thỏa mãn thì ghi ra $-1$.

Ví dụ

Ví dụ 1

3
ABRBCDAB
LCKHABWCHTHUR
ANHA

Kết quả:

5
3
-1

Giải thích: độ dài lớn nhất của các xâu con thỏa mãn tương ứng là:

• xâu 1: 5 kí tự BRBCD;
• xâu 2: 3 kí tự LCK và BWC;
• xâu 3: không có xâu con thỏa mãn.

Ràng buộc:

• 30% số điểm có xâu đầu vào chỉ có một kí tự 'A' và không có 'N', 'H';
• 30% số điểm có xâu đầu vào có một kí tự 'A', một kí tự 'H', không có kí tự 'N' và độ dài xâu $\le 10^2$;
• 40% số điểm còn lại không có ràng buộc gì thêm.

Độ khó: Trung bình (2/4 điểm)

Giới hạn thời gian: 1 giây · Giới hạn bộ nhớ: 256 MB

Cho dãy số nguyên dương $a1, a2, \dots, a_N$. Mỗi thao tác bạn được phép chọn một phần tử bất kỳ trong dãy để tăng lên $1$ đơn vị.

Yêu cầu: Thực hiện $M$ thao tác để phần tử nhỏ nhất của dãy (sau khi thực hiện $M$ thao tác) nhận giá trị lớn nhất.

Dữ liệu (CAU3.INP):

• Dòng đầu tiên gồm hai số nguyên $N$ và $M$ ($1 \le N \le 2 \times 10^5$; $0 \le M \le 10^9$);
• Dòng thứ hai gồm $N$ số nguyên $a1, a2, \dots, aN$ ($1 \le ai \le 10^9$).

Kết quả (CAU3.OUT):

Một số nguyên duy nhất là giá trị nhỏ nhất của dãy số sau khi thực hiện $M$ thao tác theo yêu cầu trên.

Ví dụ

Ví dụ 1

5 6
2 8 6 5 9

Kết quả:

6

Giải thích: nâng $2 \to 6$ (4 thao tác) và $5 \to 6$ (1 thao tác) là xong 5 thao tác, thao tác còn lại tăng một phần tử bất kỳ; dãy có giá trị nhỏ nhất là $6$. Không thể đạt $7$ vì khi đó cần $5 + 0 + 1 + 2 + 0 = 8 > 6$ thao tác.

Ràng buộc:

• 20% số điểm có $N \le 10^5$ và $M \le 1$;
• 20% số điểm có $N = 2$ và $M \le 10^2$;
• 30% số điểm có $N \le 10^3$ và $M \le 10^2$;
• 30% số điểm còn lại không có ràng buộc gì thêm.

Độ khó: Khá (3/4 điểm)

Giới hạn thời gian: 1 giây · Giới hạn bộ nhớ: 256 MB

Nhà của An cách trường học một con sông. Giữa dòng sông có $N$ hòn đá nhô lên khỏi mặt nước được đánh số thứ tự từ $1$ đến $N$ theo hướng từ nhà đến trường. Mỗi lần đi học, An phải nhảy lên các hòn đá bắt đầu từ hòn đá thứ $1$ đến hòn đá thứ $N$ để lên bờ bên kia. Với mỗi bước nhảy, nếu đang đứng ở hòn đá thứ $X$, An có thể nhảy đến hòn đá thứ $X + d$, với $d$ là ước nguyên dương của một trong $K$ số nguyên dương $a1, a2, \dots, a_K$.

Một dãy các hòn đá mà An nhảy lên để đi từ hòn đá thứ $1$ đến hòn đá thứ $N$ được gọi là một cách đi. Hai cách đi khác nhau nếu tồn tại một hòn đá An nhảy lên ở cách này nhưng không nhảy lên ở cách kia.

Yêu cầu: Hãy đếm số cách đi khác nhau mà An có thể thực hiện để đi từ hòn đá thứ $1$ đến hòn đá thứ $N$.

Dữ liệu (CAU4.INP):

• Dòng đầu tiên ghi hai số nguyên dương $N, K$;
• Dòng thứ hai gồm $K$ số $a1, a2, \dots, aK$ ($1 \le ai \le 10^6$).

Kết quả (CAU4.OUT):

Một số duy nhất là số cách khác nhau mà An có thể thực hiện được khi chia lấy dư cho $(10^9 + 7)$.

Ví dụ

Ví dụ 1

5 1
3

Kết quả:

3

Giải thích: với $a_1 = 3$, các bước nhảy hợp lệ là $d \in {1, 3}$ (các ước của $3$). Có $3$ cách đi từ hòn đá $1$ đến hòn đá $5$:

• $1 \xrightarrow{+1} 2 \xrightarrow{+1} 3 \xrightarrow{+1} 4 \xrightarrow{+1} 5$
• $1 \xrightarrow{+1} 2 \xrightarrow{+3} 5$
• $1 \xrightarrow{+3} 4 \xrightarrow{+1} 5$

Hình minh họa ba cách đi của ví dụ 1:

Lưu ý về đề gốc: bản đề thi in kết quả của ví dụ này là $4$, nhưng phần giải thích ngay bên cạnh chỉ liệt kê $3$ cách và theo đúng định nghĩa thì đáp án là $3$ (bước nhảy $d$ chỉ có thể là $1$ hoặc $3$; đếm số cách viết $4 = 1+1+1+1 = 1+3 = 3+1$). Số $4$ là kết quả của $N = 6$ (các cách viết $5 = 1+1+1+1+1 = 1+1+3 = 1+3+1 = 3+1+1$), có vẻ đề gốc ghi nhầm $N$. Trong đề này ví dụ được sửa thành kết quả 3.

Ràng buộc:

• 40% số điểm có $N \le 20$; $K = 1$ và $a_1 = 6$;
• 60% số điểm còn lại có $N \le 10^5$; $K \le 10$; $a_i \le 10^6$ (với mọi $i = 1..K$).