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

Bình là người đam mê Toán học và thích tìm hiểu về các số có tính chất đặc biệt. Bình gọi số nguyên dương $X$ là số thú vị nếu hai chữ số tận cùng của $X$ tạo thành một số chia hết cho số nguyên dương $k$ cho trước.

Ví dụ, nếu $k = 12$ thì số $1236$ là số thú vị vì có hai chữ số cuối là $36$ chia hết cho $12$. Ngược lại, số $1457$ không phải là số thú vị.

Bình muốn đếm số lượng số thú vị trong đoạn $[a; b]$. Em hãy viết chương trình giúp Bình giải quyết bài toán trên.

Yêu cầu

Đưa ra số lượng số thú vị trong đoạn $[a; b]$.

Dữ liệu vào

• Dòng đầu tiên ghi hai số nguyên dương $T$ và $k$ ($T \le 10^5$, $k \le 99$);
• $T$ dòng tiếp theo, mỗi dòng ghi hai số nguyên dương $a, b$ ($10^2 \le a \le b \le 10^{18}$).

Kết quả

Ghi ra $T$ dòng, mỗi dòng tương ứng là số lượng số thú vị trong đoạn $[a; b]$.

Giới hạn

• $50\%$ số test có $T = 1$, $10^2 \le a \le b \le 10^6$;
• $40\%$ số test có $T \le 10^5$, $10^2 \le a \le b \le 10^6$;
• $10\%$ số test có $T \le 10^5$, $10^2 \le a \le b \le 10^{18}$.

Lưu ý: Tuy đề thi gốc cho phép đọc/ghi file, nhưng trên web thì mặc định là đọc dữ liệu từ bàn phím (stdin) và in kết quả ra màn hình (stdout).

Sample Input

2 11
100 200
201 300

Sample Output

11
10

Giải thích

• Từ $100 \to 200$ có $11$ số có $2$ chữ số tận cùng chia hết cho $11$;
• Từ $201 \to 300$ có $10$ số có $2$ chữ số tận cùng chia hết cho $11$.

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

Trong một buổi ngoại khóa của Câu lạc bộ Tin học, giáo viên tổ chức trò chơi tìm "Hộp quà may mắn". Các đội chơi sẽ nhận được một xâu $S$ chỉ gồm các kí tự số. Mỗi đội phải tìm được mã số của hộp quà may mắn. Mã số cần tìm là số lượng xâu con trong xâu $S$ tạo thành số đặc biệt. Số đặc biệt là số chia hết cho $97$ và có tổng các chữ số chia hết cho $3$. Chấp nhận các số có chữ số $0$ đứng đầu.

Em hãy viết chương trình tìm ra mã số của hộp quà may mắn.

Yêu cầu

Đưa ra số lượng xâu con trong xâu $S$ tạo thành số đặc biệt là mã số của hộp quà may mắn cần tìm.

Dữ liệu vào

Một dòng là xâu ký tự $S$ có độ dài $|S| \le 10^5$.

Kết quả

Một dòng ghi số lượng xâu con trong xâu $S$ tạo thành số đặc biệt.

Giới hạn

• $50\%$ số test ứng với độ dài xâu $|S| \le 300$;
• $30\%$ số test ứng với độ dài xâu $|S| \le 10^3$;
• $20\%$ số test ứng với độ dài xâu $|S| \le 10^5$.

Lưu ý: Tuy đề thi gốc cho phép đọc/ghi file, nhưng trên web thì mặc định là đọc dữ liệu từ bàn phím (stdin) và in kết quả ra màn hình (stdout).

Sample Input

2910

Sample Output

3

Giải thích

Có $3$ số đặc biệt là $291$, $2910$, $0$.

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

Thành phố A đang quy hoạch xây dựng đô thị kiểu mẫu với các tiêu chuẩn "xanh, sạch, đẹp, hiện đại", trong đó có dự án sơn các ngôi nhà liền kề trên cùng một trục đường để có màu sắc giống nhau, với chi phí cho phép là $k$. Hiện tại mỗi ngôi nhà được sơn với một màu và mỗi màu sơn được biểu diễn bằng một kí tự từ 'a' đến 'z'. Chi phí chuyển đổi màu sơn của ngôi nhà từ màu sơn $x$ sang màu sơn $y$ là khoảng cách từ vị trí kí tự biểu diễn màu sơn $x$ đến vị trí kí tự biểu diễn màu sơn $y$. Vị trí các kí tự là mã thập phân của nó trong bảng mã ASCII.

Ví dụ: Chi phí chuyển đổi từ màu sơn biểu diễn bằng kí tự 'a' sang màu sơn biểu diễn bằng kí tự 'b' là $|97 - 98| = 1$.

Hãy viết chương trình giúp ban quản lí quy hoạch đô thị giải quyết dự án trên.

Yêu cầu

Đưa ra số lượng nhiều nhất các ngôi nhà liền kề cùng màu sơn sau khi thực hiện dự án, với tổng chi phí chuyển đổi không vượt quá $k$.

Dữ liệu vào

• Dòng đầu tiên ghi số nguyên dương $k$ ($k \le 10^5$) là chi phí cho phép của dự án;
• Dòng thứ hai ghi xâu ký tự $S$ có độ dài $|S| \le 5 \times 10^5$ là xâu biểu diễn màu sơn hiện tại của các ngôi nhà.

Kết quả

Một dòng duy nhất là kết quả cần tìm.

Giới hạn

• $60\%$ số test có độ dài xâu $|S| \le 10^3$;
• $40\%$ số test có độ dài xâu $|S| \le 5 \times 10^5$.

Lưu ý: Tuy đề thi gốc cho phép đọc/ghi file, nhưng trên web thì mặc định là đọc dữ liệu từ bàn phím (stdin) và in kết quả ra màn hình (stdout).

Sample Input 1

2
babac

Sample Output 1

4

Giải thích 1

Ta thực hiện biến đổi ký tự 'b' $\to$ 'a' (hoặc 'a' $\to$ 'b') và thu được xâu mới 'aaaac' (hoặc 'bbbbc'). Tổng chi phí biến đổi là $2$. Số lượng nhiều nhất các ngôi nhà liền kề cùng màu sơn là $4$.

Sample Input 2

2
afab

Sample Output 2

2

Giải thích 2

Ta thực hiện biến đổi ký tự 'b' $\to$ 'a' (hoặc 'a' $\to$ 'b') và thu được xâu mới 'afaa' (hoặc 'afbb'). Tổng chi phí biến đổi là $1$. Số lượng nhiều nhất các ngôi nhà liền kề cùng màu sơn là $2$.

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

Bố bạn Hùng là một nhà đầu tư trong một quỹ tài chính. Chiến lược đầu tư của bố bạn là chọn đúng $k$ thời điểm để đầu tư từ chuỗi dữ liệu của thị trường gồm $n$ ngày. Mỗi ngày có một chỉ số thị trường là $ai$. Bố bạn đã xây dựng một chiến lược phân bổ trọng số $w1, w2, \dots, wk$ tương ứng với từng lần đầu tư. Hùng mong muốn giúp bố của mình lựa chọn $k$ ngày khác nhau (theo đúng thứ tự thời gian) để đầu tư sao cho tổng lợi nhuận $S$ đạt cao nhất có thể theo công thức $S = w1 \times a{i1} + w2 \times a{i2} + \dots + wk \times a{i_k}$. Ngoài ra, bạn ấy cũng muốn biết có bao nhiêu cách chọn ngày để đạt được tổng lợi nhuận lớn nhất đó.

Em hãy viết chương trình giúp bạn Hùng giải quyết mong muốn trên.

Yêu cầu

Tìm tổng lợi nhuận lớn nhất và số cách đầu tư để đạt tổng lợi nhuận lớn nhất.

Dữ liệu vào

• Dòng đầu tiên ghi hai số nguyên dương $n, k$ ($n \le 10^5$, $k \le 100$, $k \le n$);
• Dòng thứ hai ghi $n$ số nguyên dương $a1, a2, \dots, an$ ($ai \le 10^9$) là chỉ số thị trường mỗi ngày;
• Dòng thứ ba ghi $k$ số nguyên dương $w1, w2, \dots, wk$ ($wi \le 10^6$) là trọng số đầu tư.

Kết quả

Ghi ra hai dòng, dòng thứ nhất ghi tổng lợi nhuận lớn nhất và dòng thứ hai ghi số cách đầu tư để đạt được tổng lợi nhuận lớn nhất đó. Kết quả được chia lấy dư cho $10^9 + 7$ khi in ra.

Giới hạn

• $20\%$ số test: $0 < n \le 10^2$, $k = 1$;
• $40\%$ số test: $0 < n \le 10^3$, $0 < k \le 100$;
• $40\%$ số test: $0 < n \le 10^5$, $0 < k \le 100$.

Lưu ý: Tuy đề thi gốc cho phép đọc/ghi file, nhưng trên web thì mặc định là đọc dữ liệu từ bàn phím (stdin) và in kết quả ra màn hình (stdout).

Sample Input

5 3
2 8 6 3 3
5 2 6

Sample Output

70
2

Giải thích

Có $2$ cách chọn các ngày: ngày thứ $2, 3, 4$ hoặc ngày thứ $2, 3, 5$ đều cho tổng lợi nhuận là $5 \times 8 + 2 \times 6 + 6 \times 3 = 70$.