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

Đề thi tuyển sinh lớp 10 chuyên Tin - Khánh Hòa, năm học 2024 - 2025. Bài 1 (2,00 điểm).

Sau khi học sinh đã đăng kí danh sách tham gia trại hè, nhà trường cần đặt phòng khách sạn theo nhu cầu của học sinh. Theo thông tin đăng kí nhận được thì có $a$ học sinh muốn ở phòng riêng (một mình một phòng) và có $b$ học sinh không có yêu cầu gì, tùy theo sắp xếp của nhà trường. Biết rằng mỗi phòng chỉ ở tối đa $3$ học sinh.

Yêu cầu: Hãy tính số lượng phòng ít nhất mà nhà trường cần đặt.

Input

• Gồm hai số nguyên $a$ và $b$ $(0 \le a, b \le 10^9)$.

Output

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

Giới hạn

• $70\%$ số test tương ứng $70\%$ số điểm có $0 \le b \le 10^6$.
• $30\%$ số test tương ứng $30\%$ số điểm còn lại không có ràng buộc gì thêm.

Lưu ý: Đề gốc dùng tệp BAI1.INP/BAI1.OUT, trên web các bạn đọc dữ liệu từ bàn phím và in kết quả ra màn hình.

Sample Input

1 4

Sample Output

3

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

Đề thi tuyển sinh lớp 10 chuyên Tin - Khánh Hòa, năm học 2024 - 2025. Bài 2 (3,00 điểm).

Trong hội trại năm nay, Tí được lớp giao nhiệm vụ tham gia trò chơi giải mật thư tìm kho báu. Mật thư có $n$ kí tự chỉ gồm hai loại kí tự là A và B. Trong mật thư, nếu số lần chuỗi con AA xuất hiện nhiều hơn số lần xuất hiện của chuỗi con BB thì đáp án của mật thư là số lần xuất hiện chuỗi con AA và ngược lại.

Tí vô tình làm ướt mật thư nên một số kí tự có thể bị nhòe mực, lúc này kí tự nào bị nhòe thì kí tự đó sẽ chuyển thành kí tự *.

Yêu cầu: Hãy giúp Tí tìm ra một số lớn nhất có thể là đáp án của mật thư nếu nó không bị ướt.

Input

• Dòng đầu tiên chứa số nguyên dương $n$ là độ dài của mật thư $(1 \le n \le 10^6)$.
• Dòng thứ hai chứa $n$ kí tự A, B hoặc * được ghi liên tiếp không chứa dấu cách.

Output

• Một số nguyên duy nhất là đáp án của bài toán.

Giới hạn

• $50\%$ số test tương ứng $50\%$ số điểm với mật thư chỉ gồm hai kí tự A và B.
• $50\%$ số test tương ứng $50\%$ số điểm còn lại không có ràng buộc gì thêm.

Lưu ý: Đề gốc dùng tệp BAI2.INP/BAI2.OUT, trên web các bạn đọc dữ liệu từ bàn phím và in kết quả ra màn hình.

Sample Input 1

5
AABBB

Sample Output 1

2

Sample Input 2

4
A*BB

Sample Output 2

2

Giải thích

• Ví dụ 1: chuỗi AA xuất hiện $1$ lần, chuỗi BB xuất hiện $2$ lần. Vậy đáp án là $2$.
• Ví dụ 2: nếu kí tự * là B thì chuỗi BB xuất hiện $2$ lần, còn chuỗi AA không xuất hiện lần nào. Ngược lại nếu * là A thì AA xuất hiện $1$ lần và BB cũng xuất hiện $1$ lần. Vậy đáp án là $2$.

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

Đề thi tuyển sinh lớp 10 chuyên Tin - Khánh Hòa, năm học 2024 - 2025. Bài 3 (2,50 điểm).

Sở thích của Tí và Tèo là giải những bài toán liên quan tới dãy số. Lần này Tí ghi ra một dãy số gồm $n$ số nguyên trên một dòng và một số nguyên dương $k$ rồi yêu cầu Tèo tìm dãy con có đúng $k$ phần tử liên tiếp thỏa mãn các yêu cầu sau:

1. Tổng các phần tử trong dãy con là lớn nhất.
2. Nếu có nhiều dãy con thỏa mãn yêu cầu (1) thì chọn dãy con có nhiều số chẵn nhất.
3. Nếu có nhiều dãy con thỏa mãn yêu cầu (2) thì chọn dãy con có chỉ số của phần tử đầu tiên nhỏ nhất.

Tèo loay hoay cả buổi mà vẫn chưa giải được.

Yêu cầu: Bạn hãy giúp Tèo giải bài toán trên.

Input

• Dòng đầu tiên chứa hai số nguyên $n$ và $k$ $(1 \le k \le n \le 10^6)$.
• Dòng thứ hai chứa $n$ số nguyên $a1, a2, \ldots, an$ $(|ai| \le 10^9;\ 1 \le i \le n)$.

Output

• Hai số nguyên trên cùng một dòng lần lượt là chỉ số của phần tử đầu tiên và chỉ số của phần tử cuối cùng trong dãy con tìm được.

Giới hạn

• $50\%$ số test tương ứng $50\%$ số điểm có $1 \le k \le n \le 10^3$.
• $50\%$ số test tương ứng $50\%$ số điểm còn lại không có ràng buộc gì thêm.

Lưu ý: Đề gốc dùng tệp BAI3.INP/BAI3.OUT, trên web các bạn đọc dữ liệu từ bàn phím và in kết quả ra màn hình.

Sample Input 1

5 2
2 3 -8 13 -20

Sample Output 1

1 2

Sample Input 2

5 2
2 -3 8 13 -20

Sample Output 2

3 4

Giải thích

• Ví dụ 1: hai dãy con $(2, 3)$ và $(-8, 13)$ cùng có tổng lớn nhất là $5$ và cùng có $1$ số chẵn, nên chọn dãy con bắt đầu sớm hơn: từ vị trí $1$ đến $2$.
• Ví dụ 2: dãy con $(8, 13)$ có tổng lớn nhất là $21$.

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

Đề thi tuyển sinh lớp 10 chuyên Tin - Khánh Hòa, năm học 2024 - 2025. Bài 4 (2,50 điểm).

Số chính phương là số mà nếu lấy căn bậc hai của nó thì được một số nguyên dương. Hay nói cách khác, bình phương của một số nguyên dương là một số chính phương. Ví dụ: $9$ là số chính phương vì $\sqrt{9} = 3$ (hay $3^2 = 9$), nhưng $10$ thì không phải số chính phương vì $\sqrt{10} \approx 3{,}16228$.

Yêu cầu: Cho $n$ số nguyên dương $x1, x2, \ldots, xn$. Tương ứng với mỗi $xi$ $(1 \le i \le n)$, hãy cho biết có nhiều nhất bao nhiêu số chính phương khác nhau mà tổng của chúng không vượt quá $x_i$.

Input

• Dòng đầu chứa số nguyên dương $n$ $(1 \le n \le 10^5)$.
• Dòng thứ hai chứa $n$ số nguyên dương $x1, x2, \ldots, xn$ $(1 \le xi \le 10^{18};\ 1 \le i \le n)$.

Output

• Gồm $n$ số nguyên trên cùng một dòng, trong đó số thứ $i$ là đáp án cần tìm tương ứng với $x_i$.

Giới hạn

• $50\%$ số test tương ứng $50\%$ số điểm có $1 \le n \le 10^3;\ 1 \le x_i \le 10^9$.
• $50\%$ số test tương ứng $50\%$ số điểm còn lại không có ràng buộc gì thêm.

Lưu ý: Đề gốc dùng tệp BAI4.INP/BAI4.OUT, trên web các bạn đọc dữ liệu từ bàn phím và in kết quả ra màn hình.

Sample Input

2
14 10

Sample Output

3 2

Giải thích

• Với $x_1 = 14$ ta chỉ có thể chọn nhiều nhất $3$ số chính phương là $1, 4$ và $9$ vì $1 + 4 + 9 \le 14$.
• Với $x_2 = 10$ ta chỉ có thể chọn nhiều nhất $2$ số chính phương là $1$ và $4$ hoặc $1$ và $9$ vì $1 + 4 \le 10$ hoặc $1 + 9 \le 10$.