Tin học trẻ Bắc Giang 2023

Số tròn chục là số có chữ số hàng đơn vị là chữ số \(0\).

Cho hai số tự nhiên \(L\) và \(R\). Hãy đếm xem có bao nhiêu số tròn chục lớn hơn \(L\) và nhỏ hơn \(R\).

Input

• Nhập vào số tự nhiên \(L, R\) \((1 \leq L < R \leq 10^{12})\). Mỗi số trên một dòng.

Output

• Ghi ra kết quả của bài toán.

Scoring

• Nếu chương trình chạy đúng những trường hợp \(R \leq 10^{6}\), thí sinh sẽ được 80 điểm;
• Nếu chương trình chạy đúng những trường hợp \(R \leq 10^{12}\), thí sinh sẽ được 100 điểm.

Example

5
31

3

Tít và Mít đang chơi một trò chơi như sau: Tít chọn các số tự nhiên từ \(A\) đến \(B\), Mít chọn các số tự nhiên từ \(C\) đến \(D\). Hãy lập trình để đếm xem có bao nhiêu số chỉ có một trong hai bạn chọn.

Input

• Nhập vào bốn số tự nhiên \(A, B, C, D\) \((1 \leq A, B, C, D \leq 10^{9}, A < B, C < D)\), Mỗi số trên một dòng.

Ouput

• Ghi ra số lượng số chỉ có một trong hai bạn chọn.

Scoring

• Nếu chương trình chạy đúng những trường hợp \(A, B, C, D \leq 10^{6}\), thí sinh sẽ được \(70\) điểm.
• Nếu chương trình chạy đúng tất cả các trường hợp, thí sinh sẽ được \(100\) điểm.

Example

3
6
4
9

4

7
8
1
4

6

1
3
1
3

0

Cho dãy số có quy luật như sau: \(1, 2, 2, 3, 3, 3, 4, 4, 4, 4, 5, 5, \ldots\).

Cho một số tự nhiên \(N\), hãy tìm số thứ \(N\) của dãy số trên (các số được đánh thứ tự từ \(1\)).

Input

• Nhập vào số tự nhiên \(N\) \((N \leq 10^{15})\)

Output

• Ghi ra kết quả của bài toán.

Scoring

• Nếu chương trình chạy đúng những trường hợp \(N \leq 10^{6}\), thí sinh sẽ được \(60\) điểm.
• Nếu chương trình chạy đúng những trường hợp \(N \leq 10^{10}\), thí sinh sẽ được \(80\) điểm.
• Nếu chương trình chạy đúng những trường hợp \(N \leq 10^{15}\), thí sinh sẽ được \(100\) điểm.

Example

5

3

Ví dụ về cách giải nén số \(2035\) như sau: có \(2\) số \(0\), có \(3\) số \(5\), vậy khi giải nén số \(2035\) ta được số \(00555\).

Cho một số tự nhiên \(N\) có số lượng chữ số là chẵn. Giải nén số \(N\) được số \(S\). Hãy tìm chữ số thứ \(K\) của số \(S\) tính từ trái sang phải.

Input

• Nhập vào số tự nhiên \(N\) (\(N\) có không quá \(18\) chữ số) và một số tự nhiên \(K\). Mỗi số trên một dòng.

Output

• In ra kết quả của bài toán. Dữ liệu đảm bảo luôn có kết quả (\(K\) không vượt quá số lượng chữ số của \(S\)).

Example

2035
4

5

220314
3

4

Với số tự nhiên \(n\) cho trước, hãy viết biểu thức xác định số chẵn \(m\) lớn nhất giống \(n\) ở tất cả các chữ số còn lại, trừ chữ số hàng đơn vị có thể giống hoặc khác.

Ví dụ với \(n=256\), biểu thức cần viết phải đưa ra giá trị \(m=258\).

Input

• Một dòng duy nhất chứa số nguyên dương \(n\ (0 < n ≤ 10^9)\);

Output

• Chứa số tự nhiên \(m\) theo yêu cầu.

Example

256

258

Quang tô màu các ô vuông để vẽ cây thông. Thân cây thông là hình vuông độ trộng 1 ô. Kể từ đỉnh xuống, cứ cách một ô Quang vẽ một cành lá, mỗi cành lá là môt hình vuông nằm ngang độ cao 1 ô, phân chìa ra khỏi thân mỗi cành ở bên phái và bên trái là như nhau. Cành lá thứ \(i\) có phân chìa ra mỗi bên là \(i\) ô. Cành lá cuôi cùng cách mặt đất 1 ô. Cây thông Quang vẽ có \(n\) cành. Hãy xác định số ô vuông tạo ra cây thông.

Input

• Một dòng chứa số nguyên dương \(n\ (0 < n ≤ 10^9)\);

Output

• Một số nguyên là số ô vuông tao ra cây thông.

Example

5

41

Cho \(2\) số nguyên \(A\) và \(B\). Tìm số nguyên \(M\) nằm giữa \(A\) và \(B\) sao cho khoảng cách giữa \(A \times M\) và \(B \times M\) là nhỏ nhất. \(M\) phải khác \(A\) và \(B\)

Input

• Gồm 1 dòng duy nhất chứa hai số nguyên \(A\) và \(B\) \((-10^{9} \leq A \leq B - 2 \leq 10^{9})\)

Output

• Gồm 1 dòng duy nhất chứa số nguyên \(M\) cần tìm.

Example

1 3

2

Thuận quyết định làm một thương nhân buôn bán đồ cổ để lo cho gia đình. Anh ấy cần nhập về một lượng hàng hóa để bắt đầu công vịệc buôn bán của mình. Tại chợ có \(n\) món đồ Thuận có thể mua. Thuận có thể chọn mua món đồ thứ \(i\) với giá \(a_{i}\) và cậu ấy có thể bán lại món đồ đó với giá \(b_{i}\).

Việc mua bán ở đây khá thuận lợi. Nhờ uy tín của bản thân, Thuận được các bên cho phép nhận hàng trước. Thuận có thể nhận tiền bán món đồ \(b_{i}\) trước khi bán nó, miễn là sau cùng Thuận có đưa vật phẩm \(i\) cho bên mua. Việc này đảm bảo minh bạch, vì Thuận phải kí hợp đồng rõ ràng với các bên.

Sở dĩ có sự chênh lệch về giá vì Thuận mua và bán ở hai chợ khác nhau.

Trước khi đi chợ và trở thành một thương nhân như kế hoạch, Thuận cần dự trù số tiền mình cần mang theo. Anh đặt ra \(m\) câu hỏi, câu hỏi thứ \(j\) là: "Giả sử rằng Thuận cầm đi \(k_{j}\) đồng, và buôn bán các món đồ theo mức giá như trên, thì cuối cùng Thuận có thể mua được tối đa bao nhiêu món đồ?"

Hãy lập trình để tính đáp án cho câu hỏi trên.

Input

• Dòng thứ nhất chứa hai số nguyên dương \(n, m\) \((n, m \leq 3 \times 10^{5})\) - lần lượt là số món đồ và số câu hỏi
• Dòng thứ hai chứa \(n\) số nguyên \(a_{i}\) \((0 \leq a_{i} \leq 10^{9})\).
• Dòng thứ ba chứa \(n\) số nguyên \(b_{i}\) \((0 \leq b_{i} \leq 10^{9})\).
• Dòng thứ tư chứa \(m\) số nguyên \(k_{j}\) \((0 \leq k_{j} \leq 10^{15})\).

Output

• Với mỗi câu hỏi, in ra đáp án trên một dòng riêng - số món đồ lớn nhất có thể mua.

Scoring

• Subtask \(1\) (\(40\%\) số điểm): \(n \times m \leq 10^{7}\).
• Subtask \(2\) (\(40\%\) số điểm): \(a_{i} \geq b_{i}\)
• Subtask \(3\) (\(20\%\) số điểm): không có ràng buộc gì thêm.

Example

7 3
4 3 7 5 5 2 4
1 1 8 1 6 2 5
0 3 7

5
6
7

Trường THPT Chuyên Lê Quý Đôn đang tổ chức một cuộc thi giải mã thu hút rất nhiều sự quan tâm của các bạn học sinh, đặc biệt là các bạn có đam mê với lập trình. Đề bài của vòng đầu tiên được ban tổ chức đưa ra như sau:

Ban đầu, hệ thống mã hoá sinh ra một xâu gồm \(3 \times k\) ký tự, đầu tiên là \(k\) ký tự L, tiếp theo là \(k\) ký tự Q và cuối cùng là \(k\) ký tự D. Sau đó, hệ thống sẽ thêm một số ký tự L, Q hoặc D vào những vị trí bất kỳ trong xâu cho đến khi xâu có độ dài \(n\). Sau đó, hệ thống sẽ cho người dùng biết \(n\), \(k\) và xâu sau khi đã biến đổi. Người giải mã cần chọn ra một xâu con gồm các ký tự liên tiếp và đếm số lượng ký tự cần xoá ít nhất để thu được xâu ban đầu mà hệ thống sinh ra. Nếu kết quả của người chơi trùng khớp với kết quả của hệ thống thì người đó sẽ được xem là hoàn thành vòng thi và nhận được tấm vé đến vòng tiếp theo.

Là một người đã có nhiều kinh nghiệm với lập trình, liệu bạn có thể giành được tấm vé này chứ?

Input

• Dòng đầu tiên chứa hai số nguyên \(n\) và \(k\) \(\left(3 \leq n \leq 10^{7}, 1 \leq k \leq \left \lfloor \dfrac{n}{3} \right \rfloor \right)\).
• Dòng tiếp theo chứa một xâu độ dài \(n\) chỉ gồm các ký tự L, Q và D.

Output

• Một dòng duy nhất chứa một số nguyên là kết quả của bạn. Trường hợp đặc biệt: nếu không thể chọn ra xâu con nào để thu được xâu ban đầu mà hệ thống sinh ra, bạn cần in ra -1

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(n \leq 21\).
• Subtask \(2\) (\(30\%\) số điểm): \(n \leq 3 \times 10^{3}\).
• Subtask \(3\) (\(30\%\) số điểm): \(n \leq 2 \times 10^{5}\).
• Subtask \(4\) (\(20\%\) số điểm): Không có ràng buộc gì thêm.

Example

10 2
LLDLQDQDDL

2