Đề TS 10 LQĐ Đà Nẵng 2024

Số Ra-One là số mà hiệu của tổng các chữ số ở vị trí chẵn và tổng các chữ số ở vị trí lẻ là bằng 1.

Ví dụ số \(234563\) là số \(Ra-One\), vì \((2+4+6) - (3+5+3) = 1\).

Còn số \(123456\) không phải số \(Ra-One\), vì \((1+3+5) - (2+4+6) = -4 ≠ 1\)

Tìm số lượng số \(Ra-One\) từ \(A\) đến \(B\).

Input

• Hai số \(A, B\).

Output

• Số lượng số Ra-One tìm được.

Input

1 10

Output

1

Input

10 100

Output

9

Giải thích:

• VD1: Chỉ có 1 số \(Ra-One\) duy nhất là \(10\)
• VD2: Các số \(Ra-One\) là \(10, 21, 32, 43, 54, 65, 76, 87, 98\).

Giới hạn: \(1 ≤ A≤ B≤ 10^8\).

Nguồn: https://www.spoj.com/problems/RAONE

Số Chuẩn_1 là số mà tổng các chữ số ở vị trí lẻ trừ cho tổng các chữ số ở vị trí chẳn có kết quả bằng \(1\). Ví dụ: số \(234563\) là số Chuẩn_1, vì \((2+4+6) - (3+5+3) = 1\). Còn số \(123456\) không phải số Chuẩn_1, vì \((1+3+5) - (2+4+6)= -4\neq 1\).

Yêu cầu: Tìm số lượng số Chuẩn_1 từ \(A\) đến \(B\).

Input

• Một dòng chứa hai số nguyên \(A\) và \(B\) (\(1 \le A\le B\le 10^8\)).

Output

• Ghi ra số lượng số Chuẩn_1 tìm được.

Example

1 10

1

10 99 

8

Cho một xâu \(S\) chỉ gồm các kí tự thường trong bảng chữ cái tiếng Anh. Hãy tìm ra tất cả các từ vựng có trong xâu \(S\). Một từ vựng có được bằng cách ghép một số kí tự liên tiếp lấy từ xâu \(S\), giữ nguyên thứ tự của chúng, thỏa mãn một trong hai điều kiện sau:

• Bắt đầu bằng một nguyên âm (là các chữ cái: a, e, i, o, u) và kết thúc bằng một phụ âm (là các chữ cái còn lại).
• Bắt đầu bằng một phụ âm và kết thúc bằng một nguyên âm.

Yêu cầu: Tìm số lượng từ vựng có trong xâu \(S\) theo quy tắc trên.

Input

• Một dòng chứa xâu \(S\) \((|S| \leq 10^{6})\).

Output

• Ghi ra một số nguyên là kết quả tìm được.

Scorning

• Subtask \(1\) (\(40\%\) số điểm): \(|S| \leq 10^{4}\).
• Subtask \(2\) (\(60\%\) số điểm): không có rằng buộc gì thêm.

Example

adceba

9

Nobita được Doraemon tặng một chiếc túi ma thuật có thể tăng sức mạnh của người dùng sau mỗi bước đi và một số bảo bổi. Mỗi bảo bối có trọng lượng \(C\) và giá trị phép thuật \(H\). Nobita chỉ có thể di chuyển nếu chỉ số sức mạnh của mình lớn hơn hoặc bằng tổng trọng các bảo bối trong túi. Để thử tài của Nobita, Doraemon xếp các bảo bối trên một đường thăng và yêu cầu Nobita di chuyển dọc theo đường thăng. Nobita chỉ được phép tiên lên, chỉ có thể lấy bảo bối tại vị trí đang đứng cho vào túi hoặc không lấy. Mỗi bước đi, Nobita sẽ tăng thêm \(X\) chỉ số sức mạnh. Ở mỗi lần thử thách có \(M\) bảo bối, Nobita xuất phát tại vị trí bảo bối thứ nhất, chỉ số sức mạnh lúc này là 0 và cái túi không chứa bảo bối nào. Mỗi bước đi Nobita sẽ tiến tới vị trí bảo bối tiếp theo. Hãy giúp Nobita lấy được các bảo bối có tổng giá trị phép thuật là cao nhất và đảm bảo cậu vẫn có thể di chuyển bình thường. Biết rằng tổng giá trị phép thuật của bảo bối ở tất cả các lần thử thách không lớn hơn \(10^5\).

Yêu cầu: Hãy cho biết tổng giá trị phép thuật lớn nhất của các bảo bối mà Nobita lấy được ở mỗi lần thử thách là bao nhiêu.

Input

• Dòng đầu tiên chứa số nguyên \(t\) (\(1≤t≤10^3\)) là số bộ test tương ứng với số lần thử thách.
• Các dòng tiếp theo tương ứng với \(t\) bộ test. Mỗi bộ test chứa dữ liệu như sau:
  • Dòng đầu của mỗi bộ test chứa hai số nguyên dương \(M\) (\(1 \le M\le50\)) và \(X\) (\(1\le X\le 10^8\)).
  • \(M\) dòng tiếp theo mỗi dòng chứa hai số nguyên dương, dòng thứ \(i\) chứa hai số nguyên dương \(C_i\) (\(0 \le C_i \le 10^8\)) và \(H_i\) (\(1 \le H\le 10^3\)).

Output

• Ghi ra \(t\) số nguyên mỗi số nằm trên một dòng tương ứng với tổng giá trị phép thuật lớn nhất của bảo bối mà Nobita có được ở mỗi lần thử thách.

Scorning

• Có \(30\%\) số test tương ứng với giá trị phép thuật bảo bối giảm dần, trọng lượng tăng dần;
• Có \(30\%\) số test tương ứng với các bảo bối có trọng lượng bằng nhau và (\(t,M<10\));
• Có \(40\%\) test tiếp theo không có giới hạn gì thêm.

Example

1
5 2
2 1
0 2
3 5
5 2
3 2

9

Một dãy số nguyên có \(M\) phần tử, giá trị trung tâm của dãy được xác định theo cách sau:

• Vị trí trung tâm tính bằng công thức \((M+1) \text{ div } 2\).
• Sắp xếp dãy số theo thứ tự không giảm.
• Giá trị trung tâm chính là giá trị tại vị trí trung tâm sau khi sắp xếp.

Yêu cầu: Cho một dãy có \(N\) phần tử và một số nguyên dương \(K\). Hãy cho biết dãy con liên tục có ít nhất \(K\) phần tử có giá trị trung tâm lớn nhất là bao nhiêu.

Input

• Dòng thứ nhất chứa hai số nguyên dương \(N\) và \(K\) (\(1 \le K\le N\le 10^5\)).
• Dòng thứ hai chứa \(N\) số nguyên dương \(a_1, a_2, a_3, ...,,a_N\) (\(1 ≤ a_i ≤ N\)).

Output

• Ghi ra số nguyên dương duy nhất thỏa mãn yêu cầu đề bài.

Scorning

6 2
1 2 3 4 5 6

5

7 3
1 6 4 5 7 8 3 

7