de-thi-chon-hoc-sinh-gioi-mon-tin-hoc-lop-8

TỔNG QUAN VỀ ĐỀ THI

Ghi chú: Thí sinh lưu chương trình với phần mở rộng tương ứng với ngôn ngữ lập trình được sử dụng (.CPP đối với C++, .PY đối với Python hoặc .PAS đối với Pascal).

BÀI 1. BƯỚC NHẢY LƯỢNG TỬ (5,0 điểm)

Tên tệp chương trình: BAI1.*

Tệp dữ liệu vào: BAI1.INP

Tệp kết quả ra: BAI1.OUT

Trong một thí nghiệm mô phỏng hạt vi mô, mức năng lượng của một hạt lượng tử tại mỗi thời điểm được biểu diễn bằng một số nguyên dương $x$. Ở mỗi chu kỳ kích hoạt, hạt có thể thực hiện một "bước nhảy năng lượng" để chuyển từ mức $x$ sang mức năng lượng mới:

$${x}_{mới}=x+lpf(x)$$

Trong đó, $lpf(x)$ là ước số nguyên tố nhỏ nhất của số nguyên dương $x$.

Ví dụ:

- Nếu $x=9$, ước số nguyên tố nhỏ nhất của $9$ là $3$, do đó sau một bước nhảy, hạt đạt mức năng lượng $9+3=12$.

- Nếu $x=12$, ước số nguyên tố nhỏ nhất của $12$ là $2$, do đó sau một bước nhảy, hạt đạt mức năng lượng $12+2=14$.

Hạt bắt đầu ở mức năng lượng ban đầu là $A$ và cần đạt tới mức năng lượng mục tiêu là $B$.

Yêu cầu: Cho hai số nguyên dương $A$ và $B$. Hãy xác định số bước nhảy ít nhất để hạt đạt được đúng mức năng lượng $B$. Nếu hạt không thể đạt tới mức năng lượng $B$ dù thực hiện bao nhiêu bước nhảy đi chăng nữa, hãy in ra $-1$.

Dữ liệu vào:

Đọc từ tệp BAI1.INP gồm một dòng duy nhất chứa hai số nguyên dương $A$ và $B$ ($1\leq A,B\leq {10}^{12}$).

Kết quả ra:

Ghi ra tệp BAI1.OUT một số nguyên duy nhất là số bước nhảy ít nhất tìm được, hoặc $-1$ nếu không thể đạt được.

Ràng buộc:

- Subtask 1 (40% số điểm): $A,B\leq {10}^{5}$.

- Subtask 2 (30% số điểm): $A,B\leq {10}^{9}$.

- Subtask 3 (30% số điểm): $A,B\leq {10}^{12}$.

Ví dụ:

BÀI 2. ĐOẠN TIN TƯƠNG PHẢN (5,0 điểm)

Tên tệp chương trình: BAI2.*

Tệp dữ liệu vào: BAI2.INP

Tệp kết quả ra: BAI2.OUT

Trạm thu phát vô tuyến ghi nhận được một chuỗi tín hiệu nhị phân mã hóa dưới dạng một xâu kí tự $S$ độ dài $N$, chỉ gồm hai loại kí tự 'A' và 'B'.

Để phân tích sự chênh lệch nhịp điệu của tín hiệu, các chuyên gia định nghĩa một đoạn tín hiệu con liên tiếp từ vị trí $i$ đến vị trí $j$ ($1\leq i\leq j\leq N$) là một đoạn tin tương phản bậc $K$ nếu:

$${count}_{A}(i,j)-{count}_{B}(i,j)=K$$

Trong đó:

- ${count}_{A}(i,j)$ là số lượng kí tự 'A' xuất hiện trong đoạn từ vị trí $i$ đến vị trí $j$.

- ${count}_{B}(i,j)$ là số lượng kí tự 'B' xuất hiện trong đoạn từ vị trí $i$ đến vị trí $j$.

- $K$ là một số nguyên cho trước (số $K$ có thể là số âm, số 0 hoặc số dương).

Yêu cầu: Cho xâu kí tự $S$ và số nguyên $K$. Hãy đếm số lượng đoạn tin con liên tiếp trong $S$ là đoạn tin tương phản bậc $K$.

Dữ liệu vào:

Đọc từ tệp BAI2.INP:

- Dòng thứ nhất chứa số nguyên $K$ ($-{10}^{5}\leq K\leq {10}^{5}$).

- Dòng thứ hai chứa xâu kí tự $S$ chỉ gồm các kí tự 'A' và 'B' ($1\leq ∣S∣\leq {10}^{5}$).

Kết quả ra:

Ghi ra tệp BAI2.OUT một số nguyên duy nhất là số lượng đoạn tin con liên tiếp thỏa mãn điều kiện.

Ràng buộc:

- Subtask 1 (40% số điểm): Độ dài xâu $∣S∣\leq 1000$.

- Subtask 2 (30% số điểm): Độ dài xâu $∣S∣\leq {10}^{5}$ và $K=0$.

- Subtask 3 (30% số điểm): Không có ràng buộc gì thêm.

Ví dụ:

BÀI 3. LIÊN MINH CHIẾN HẠM (5,0 điểm)

Tên tệp chương trình: BAI3.*

Tệp dữ liệu vào: BAI3.INP

Tệp kết quả ra: BAI3.OUT

Hạm đội phòng thủ không gian gồm $N$ chiến hạm neo đậu tại trạm chỉ huy, được đánh số từ $1$ đến $N$. Chiến hạm thứ $i$ có mức phát xạ năng lượng là một số nguyên dương ${A}_{i}$.

Để thiết lập mạng lưới lá chắn bảo vệ vững chắc, chỉ huy cần kết nối từng cặp chiến hạm $(i,j)$ với $1\leq i<j\leq N$. Hai chiến hạm chỉ có thể bắt cặp tạo thành liên minh tương thích nếu tổng mức phát xạ năng lượng của cả hai nằm trong ngưỡng an toàn $[L,R]$, nghĩa là:

$$L\leq {A}_{i}+{A}_{j}\leq R$$

Nếu tổng năng lượng nhỏ hơn $L$, lá chắn không đủ năng lượng để kích hoạt. Nếu tổng năng lượng vượt quá $R$, hệ thống sẽ bị quá tải nhiệt và tự ngắt.

Yêu cầu: Cho danh sách mức phát xạ năng lượng của $N$ chiến hạm và hai ngưỡng an toàn $L,R$. Hãy đếm số lượng cặp chiến hạm $(i,j)$ ($i<j$) có thể tạo thành liên minh tương thích.

Dữ liệu vào:

Đọc từ tệp BAI3.INP:

- Dòng thứ nhất chứa ba số nguyên dương $N,L,R$ ($2\leq N\leq {10}^{5};1\leq L\leq R\leq 2\cdot {10}^{9}$).

- Dòng thứ hai chứa $N$ số nguyên dương ${A}_{1},{A}_{2},\ldots ,{A}_{N}$ ($1\leq {A}_{i}\leq {10}^{9}$), mỗi số cách nhau bởi một dấu cách.

Kết quả ra:

Ghi ra tệp BAI3.OUT một số nguyên duy nhất là số cặp chiến hạm liên minh tương thích tìm được.

Ràng buộc:

- Subtask 1 (40% số điểm): $N\leq 2000$.

- Subtask 2 (30% số điểm): Dãy năng lượng $A$ đã được sắp xếp tăng dần (${A}_{1}\leq {A}_{2}\leq \cdots \leq {A}_{N}$).

- Subtask 3 (30% số điểm): $N\leq {10}^{5}$ và không có ràng buộc gì thêm.

Ví dụ:

BÀI 4. QUỸ ĐẠO TIA LASER (5,0 điểm)

Tên tệp chương trình: BAI4.*

Tệp dữ liệu vào: BAI4.INP

Tệp kết quả ra: BAI4.OUT

Trong một phòng thí nghiệm quang học hiện đại, các kỹ sư bố trí một phòng phẳng hình chữ nhật kín có kích thước chiều ngang là $M$ mét và chiều dọc là $N$ mét. Ta gắn căn phòng vào hệ tọa độ Đề-các:

- Bốn bức tường bao quanh nằm trên bốn đoạn thẳng: từ $(0,0)$ đến $(M,0)$, từ $(M,0)$ đến $(M,N)$, từ $(M,N)$ đến $(0,N)$ và từ $(0,N)$ đến $(0,0)$.

- Bốn góc của căn phòng lần lượt có tọa độ là: Góc 1: $(0,0)$; Góc 2: $(M,0)$; Góc 3: $(M,N)$; Góc 4: $(0,N)$.

Mặt trong của bốn bức tường được tráng gương phẳng phản xạ ánh sáng hoàn hảo. Tại mỗi góc trong bốn góc của căn phòng có lắp đặt một thiết bị cảm biến hấp thụ ánh sáng.

Một nguồn phát laser đặt tại góc $(0,0)$ bắn ra một tia sáng hướng vào trong phòng theo góc nghiêng đúng ${45}^{∘}$ so với bức tường đáy (tức là đi theo hướng vectơ $(+1,+1)$). Khi tia sáng va chạm vào một bức tường tại một điểm không phải là góc, nó sẽ phản xạ đàn hồi theo định luật phản xạ ánh sáng (góc phản xạ bằng góc tới). Khi tia sáng chạm trúng vào một trong bốn góc của căn phòng, nó sẽ bị cảm biến hấp thụ và tắt ngay lập tức.

Yêu cầu: Cho kích thước căn phòng $M$ và $N$. Hãy:

1. Xác định tọa độ $(x,y)$ của góc mà tia sáng sẽ chạm vào và kết thúc hành trình.

2. Đếm tổng số lần tia sáng đã phản xạ vào các bức tường trước khi chạm vào góc đó.

Dữ liệu vào:

Đọc từ tệp BAI4.INP gồm một dòng duy nhất chứa hai số nguyên dương $M$ và $N$ ($1\leq M,N\leq {10}^{9}$).

Kết quả ra:

Ghi ra tệp BAI4.OUT gồm hai dòng:

- Dòng thứ nhất ghi hai số nguyên $x$ và $y$ cách nhau một dấu cách, biểu thị tọa độ của góc mà tia laser chạm vào cuối cùng.

- Dòng thứ hai ghi một số nguyên duy nhất là tổng số lần tia laser đã phản xạ trên các bức tường.

Ràng buộc:

- Subtask 1 (40% số điểm): $M,N\leq 1000$.

- Subtask 2 (30% số điểm): $M,N\leq {10}^{6}$.

- Subtask 3 (30% số điểm): $M,N\leq {10}^{9}$.

Ví dụ:

--------- HẾT ---------

Họ và tên thí sinh: ............................................................................ Số báo danh: .......................................

Cán bộ coi thi không giải thích gì thêm.