Đề thi chọn đội tuyển Học sinh giỏi Quốc Gia tỉnh Quảng Trị năm 2012 - 2013 môn Tin học

TỔNG QUAN BÀI THI VÒNG 1

Hãy lập trình giải các bài toán sau với thời gian thực hiện mỗi chương trình với mỗi test không quá 1 giây.

Câu 1: (6 điểm) SỐ NHỎ NHẤT.

Cho một số nguyên dương k và một xâu kí tự S . Xâu S chỉ gồm các kí tự là các chữ cái Latinh từ ‘a’..’z’ và các chữ số từ ‘0’..’9’, trong đó có ít nhất k kí tự là chữ số.

Yêu cầu: Hãy xóa bỏ các kí tự cần thiết trong xâu S để k kí tự còn lại tạo thành một số có k chữ số và có giá trị nhỏ nhất, số tìm được đó cho phép có số 0 ở đầu.

Dữ liệu: Đọc vào từ tệp văn bản MIN.INP gồm 2 dòng:

- Dòng thứ nhất chứa số nguyên dương k (k ≤ 10);

- Dòng thứ hai chứa xâu S có độ dài nhỏ hơn 250 kí tự.

Kết quả: Ghi ra tệp MIN.OUT gồm một dòng ghi số tìm được thỏa mãn yêu cầu đã nêu.

Câu 2: (7 điểm) SỬA HÀNG RÀO.

Mèo Tom vừa chuyển đến ngôi nhà mới bên một bãi biển xinh đẹp của miền Trung. Mọi thứ trong ngôi nhà đều rất vừa ý với chú mèo, ngoại trừ bức tường rào màu xanh bao quanh ngôi nhà. Bức tường rào được ghép lại từ N thanh gỗ xếp liền nhau, chiều cao của các thanh gỗ là các số nguyên dương a₁, a₂, ...a_N. Sau khi tham khảo ý kiến của kiến trúc sư, Tom quyết định thay đổi chiều cao của các thanh gỗ của bức tường rào thành b₁, b₂, ...b_N (Không nhất thiết a phải đổi thành b). Chuột Jerry, một chủ thầu xây dựng tài ba, cho biết chi phí tăng chiều cao của một thanh gỗ bất kì lên một đơn vị là X miếng pho-mát và chi phí giảm chiều cao của một thanh gỗ bất kì xuống một đơn vị là Y miếng pho-mát.

Yêu cầu: Hãy tính chi phí thấp nhất cần phải sửa hàng rào theo ý muốn của mèo Tom là bao nhiêu miếng pho-mát?

Dữ liệu: Đọc vào từ tệp văn bản REP.INP có cấu trúc như sau:

- Dòng đầu ghi lần lượt ba số N, X, Y (3 ≤ N ≤ 10⁴ ;0 ≤ X, Y ≤ 10³)

- N dòng tiếp theo, dòng thứ i ghi lần lượt hai số a_i và b_i (0 ≤ a_i, b_i ≤ 10²)

- Các số trên cùng một dòng cách nhau một dấu cách.

Kết quả: Ghi ra tệp văn bản REP.OUT gồm một số duy nhất là chi phí tìm được.

Câu 3: (7 điểm) CHỌN BẢO BỐI.

Atêna, đứa con được thần Dớt sinh ra từ đầu của mình, là một vị nữ thần của Trí tuệ, Tri thức và Chiến trận. Nàng đã sáng tạo ra N loại bảo bối khác nhau. Bảo bối thứ i có trọng lượng w_i và sức mạnh chiến đấu là p_i (i = 1..N). Số lượng mỗi loại bảo bối là không hạn chế.

Trước mỗi trận chiến, để giành được chiến thắng, Atêna cần chọn M bảo bối để mang theo sao cho tổng trọng lượng đúng bằng W và tổng sức mạnh đúng bằng P. Nếu không chọn được thì trận chiến được hoãn lại và khi đó M được đặt bằng 0.

Yêu cầu: Hãy xác định giá trị M nhỏ nhất là bao nhiêu?

Dữ liệu: Đọc vào từ tệp văn bản WPM.INP có cấu trúc như sau:

- Dòng đầu ghi lần lượt ba số N, P, W (3 ≤ N ≤ 20 ;1 ≤ P, W ≤ 150)

- N dòng tiếp theo, dòng thứ i ghi lần lượt hai số p_i và w_i (1 ≤ p_i, w_i ≤ 150)

- Các số trên cùng một dòng cách nhau một dấu cách.

Kết quả: Ghi ra tệp văn bản WPM.OUT gồm một số duy nhất là giá trị M tìm được.