Đề thi tin học trẻ tỉnh Đồng Nai, bảng C, năm 2014 - 2015

Mời các bạn tham khảo
Đề thi tin học trẻ tỉnh Đồng Nai, bảng C, năm 2014 - 2015
---

ĐỀ THI ĐÃ CHỈNH SỬA!!!

ĐỀ THI TIN HỌC TRẺ TỈNH ĐỒNG NAI 2015 BẢNG C − KHỐI THPT Thời gian làm bài: 120 phút Ngày thi:  6/6/2014 (Đề thi này gồm 02 trang, có 04 bài)

TỔNG QUAN ĐỀ THI

Bài	Tên bài	File CT	File input	File output	Điểm
1	Trồng cây	TRONGCAY.PAS	TRONGCAY.INP	TRONGCAY.OUT	6 điểm
2	Đoạn con	DOANCON.PAS	DOANCON.INP	DOANCON.OUT	6 điểm
3	Cờ vua	COVUA.PAS	COVUA.INP	COVUA.OUT	4 điểm
4	Xâu con	XAUCON.PAS	XAUCON.INP	XAUCON.OUT	4 điểm

(Thời gian chạy chương trình 01 giây)

        Bài 1.          TRONGCAY Trồng cây

Vì quên lắng nghe 'tâm tư tình cảm của nhân dân' nên thành phố Y vừa lỡ chặt hết một hàng cây xanh trên con đường X. Để khắc phục, thành phố quyết định phải trồng lại một hàng cây mới tại n vị trí trên con đường này, mỗi vị trí trồng 1 cây. Sau khi khảo sát, mỗi vị trí thuộc một trong hai loại: loại một chỉ có thể trồng được cây tùng, loại hai có thể trồng được hoặc cây tùng hoặc cây trúc vào đó. Hiện tại, thành phố đang có a cây tùng và b cây trúc. Số cây này có thể không đủ để trồng vào n vị trí.

Yêu cầu: em hãy cho biết  thành phố cần phải mua thêm ít nhất bao nhiêu cây (cả tùng và trúc) để có thể trồng đủ cho n vị trí trên con đường X.

Input

·        Dòng đầu tiên chứa ba số nguyên n, a, b là số vị trí cần trồng, số cây tùng và số cây trúc đang có (1 ≤ n, a, b ≤ 1000).

Input	Output
3 1 1 1 2 1	1

·        Dòng thứ hai chứa n số nguyên a₁, a₂, ..., a_n (1 ≤ a_i ≤ 2). Nếu a_i = 1, thì vị trí thứ i thuộc loại một (chỉ có thể trồng tùng). Nếu a_i = 2, thì vị trí thứ i sẽ thuộc loại hai (có thể trồng hoặc tùng hoặc trúc).

Output: ghi một số nguyên duy nhất - số cây (cả tùng và trúc) ít nhất cần phải mua thêm. Nếu không cần mua thêm thì ghi 0.

        Bài 2.          DOANCON Đoạn con

Cho dãy số A gồm n số nguyên a₁, a₂, …, a_n và 2 số nguyên t và c. Hỏi có bao nhiêu cách chọn ra một đoạn con gồm c phân tử liên tiếp của dãy A mà tất cả các phần tử trong đoạn con được chọn đều không lớn hơn giá trị t.

Input	Output
11 4 2 2 2 0 7 3 2 2 4 9 1 4	6

Input

·        Dòng đầu tiên ghi 3 số nguyên n (1 ≤ n ≤ 2.10⁵), t (0 ≤ t ≤ 10⁹) và c (1 ≤ c ≤ n).

·        Dòng thứ hai ghi n số nguyên a₁, a₂, …, a_n (0 ≤ a_i ≤ 10⁹)

Output: ghi một số nguyên duy nhất là số cách chọn đoạn con thỏa đề bài. Nếu không có tồn tại đoạn con thỏa đề bài thì ghi 0.

        Bài 3.          COVUA Cờ vua

Bàn cờ vua là một hình vuông kích thước 8 x 8 gồm 8 cột dọc đánh số từ a-h từ trái qua phải và 8 hàng ngang đánh số từ 1-8 từ dưới lên trên. Ô nằm trên cột c (kí tự) và hàng i (số) được kí hiệu là ô ‘ci’. Xe và Mã là 2 trong số các quân cờ, khả năng khống chế của chúng được mô tả như sau :

·        Xe: khống chế tất cả các ô thuộc cùng hàng ngang, cột dọc.

·        Mã: khống chế tất cả các ô ở đỉnh đối diện trên đường chéo của hình chữ nhật kích thước 2 x 3

Trên bàn cờ hiện đang có một quân mã và một quân xe không nằm trong tầm khống chế của nhau, bạn đang muốn đặt thêm một quân mã nữa sao cho ba quân cờ (2 mã, 1 xe) không nằm trong tầm khống chế của nhau. Hãy tìm số ô có thể để đặt thêm quân mã này.

Ví dụ: trong hình bên, ban đầu ta có quân xe tại ô g7 và quân mã tại ô d4. Các ô có dấu chấm vuông là bị quân xe khống chế, các ô có dấu chấm tròn là bị quân mã khống chế,

Trong các ô còn trống (chưa bị khống chế và chưa có quân nào đứng), ngoại trừ ô e8 và h5, các ô còn lại đều có thể đặt quân mã thứ hai. Vậy có 38 ô thỏa yêu cầu đề bài.

Input:

Input	Output
g7 d4	38

·        Dòng đầu chứa xâu gồm 2 kí tự mô tả tọa độ quân xe đứng, kí tự đầu thuộc {‘a’..’h’}, kí tự thứ hai thuộc {‘1’ .. ‘8’}

·        Dòng thứ hai chứa xâu gồm 2 kí tự mô tả tọa độ quân mã đứng, kí tự đầu thuộc {‘a’..’h’}, kí tự thứ hai thuộc {‘1’ .. ‘8’}

Output: số ô có thể đặt thêm quân mã thứ hai.

        Bài 4.          XAUCON Xâu con

Xâu a được gọi là xâu con của xâu b nếu a là một đoạn các kí tự liên tiếp trong b. Ví dụ: ‘aba’ là xâu con của xâu ‘bbaba’, nhưng không là xâu con của xâu ‘aabbaa’.

Yêu cầu: Cho hai xâu s₁, s₂. Tìm độ dài của xâu con chung ngắn nhất p của s₁ và s₂ với điều kiện p chỉ xuất hiện đúng một lần trong s₁ và đúng một lần trong s₂.

Input:

Input	Output
abcabc cabbcab	3

·        Dòng đầu ghi xâu s1

·        Dòng thứ hai ghi xâu s2

Mỗi xâu dài không quá 5000 kí tự chỉ gồm các chữ cái ‘a’…’z’.

Output: ghi độ dài của xâu con chung ngắn nhất p. Nếu không tồn tại p xuất – 1.

- HẾT -