Tuyển sinh 10 chuyên Tin Khánh Hòa 2024

Nguồn: ClueOJ statement pages printed to PDF and merged in exam order; not an original scan

Chuyển nhập/xuất tệp sang stdin/stdout khi chạy trên website.

Câu 1. Bài 1

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

Hai số nguyên $a$ và $b$ ( $0 \leq a, b \leq 109$ ).

OUTPUT

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

SAMPLE INPUT

1 4

SAMPLE OUTPUT

SUBTASKS

$70%$ test tương ứng với $70%$ số điểm có $0 \leq b \leq 106$ .

$30%$ test tương ứng với $30%$ số điểm còn lại không có ràng buộc gì thêm.

---

Ghi chú về bản chuyển thể

Nhập từ stdin và in ra stdout, không cần tạo tệp .INP/.OUT.

Trạng thái lời giải: C++ đã qua bộ kiểm thử cục bộ; chưa xác nhận AC trên OJ.

Câu 2. Bài 2

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ự nhòe bị thay thế bởi 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 \leq n \leq 106$ ).

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

Chỉ gồm một số nguyên duy nhất là đáp án của bài toán.

SAMPLE INPUT 1

5
AABBB

SAMPLE OUTPUT 1

Giải thích:

Chuỗi AA xuất hiện $1$ lần. Chuỗi BB xuất hiện $2$ lần. Vậy đáp án bài toán là $2$ .

SAMPLE INPUT 2

4 
A*BB

SAMPLE OUTPUT 2

Giải thích:

Nếu kí tự * là kí tự 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 kí tự * là kí tự A thì chuỗi AA xuất hiện $1$ lần và chuỗi BB cũng xuất hiện $1$ lần. Vậy đáp án bài toán là $2$ .

SUBTASKS

$50%$ test tương ứng $50%$ số điểm với mật thư chỉ gồm hai kí tự A và B .

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

---

Ghi chú về bản chuyển thể

Nhập từ stdin và in ra stdout, không cần tạo tệp .INP/.OUT.

Trạng thái lời giải: C++ đã qua bộ kiểm thử cục bộ; chưa xác nhận AC trên OJ.

Câu 3. Bài 3

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:

Tổng các phần tử trong dãy con là lớn nhất.

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.

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 \leq k \leq n \leq 106$ ).

Dòng thứ hai chứa $n$ số nguyên $a 1, a 2, ..., a n$ ( $|a i | \leq 109$ , $1 \leq i \leq 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.

SAMPLE INPUT

5 2 
2 -3 8 13 -20

SAMPLE OUTPUT

3 4

SUBTASKS

$50%$ test tương ứng $50%$ số điểm có $1 \leq k \leq n \leq 103$ .

$50%$ test tương ứng $50%$ số điểm không có ràng buộc gì thêm.

---

Ghi chú về bản chuyển thể

Nhập từ stdin và in ra stdout, không cần tạo tệp .INP/.OUT.

Trạng thái lời giải: C++ đã qua bộ kiểm thử cục bộ; chưa xác nhận AC trên OJ.

Câu 4. Bài 4

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 $32 = 9$ ), nên 9 là số chính phương. 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 $x 1, x 2, ..., x n$ . Tương ứng với mỗi $x i$ ( $1 \leq i \leq 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 \leq n \leq 105$ ).

Dòng thứ hai chứa $n$ số nguyên dương $x 1, x 2, ..., x n$ ( $1 \leq x i \leq 1018$ , $1 \leq i \leq n$ ).

OUTPUT

$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 của $x i$ .

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, 9$ vì $1 + 4 + 9 \leq 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 \leq 10$ hoặc $1 + 9 \leq 10$ .

SUBTASKS

$50%$ test tương ứng với $50%$ số điểm có $1 \leq n \leq 103, 1 \leq x i \leq 109$ .

$50%$ test tương ứng với $50%$ số điểm còn lại không có ràng buộc gì thêm.

---

Ghi chú về bản chuyển thể

Nhập từ stdin và in ra stdout, không cần tạo tệp .INP/.OUT.

Trạng thái lời giải: C++ đã qua bộ kiểm thử cục bộ; chưa xác nhận AC trên OJ.

Cấu trúc đề và tiến độ