Đề thi học sinh giỏi Tin học lớp 11 Bạc liêu

Bài 1: (6 điểm)
Trong đợt tổ chức đi tham quan của Đoàn thanh niên, Ban tổ chức cho N đoàn (đánh từ số 1 đến N) mỗi đoàn đi tham quan một địa điểm khác nhau. Đoàn thứ i đi thăm địa điểm ở cách Khách sạn Hoàng Đế di km (i=1,2,...,N). Đoàn thanh niên có M xe taxi đánh số từ 1 đến M (M>=N) để phục vụ việc đưa các đoàn đi tham quan. Xe thứ j có mức tiêu thụ xăng là vj đơn vị thể tích/km.
Yêu cầu: Hãy chọn N xe để phục vụ việc đưa các đoàn đi tham quan, mỗi xe chỉ phục vụ một đoàn sao cho chi phí xăng cần sử dụng là ít nhất.
Dữ liệu: File văn bản IB1.inp
- Dòng đầu tiên chứa hai số nguyên dương N, M (N,M<=200)
- Dòng thứ hai chứa các số nguyên dương d1, d2,..., dN
- Dòng thứ ba chứa các số nguyên dương v1, v2,..., vM
- Các số trên cùng một dòng được ghi khác nhau bởi dấu trắng
Kết quả: Ghi ra file văn bản OB1.out
- Dòng đầu tiên chứa tổng lượng xăng dầu cần dùng cho việc đưa các đoàn đi tham quan (không tính lượt về).
- Dòng thứ i trong số N dòng tiếp theo ghi chỉ số xe phục vụ đoàn i (i=1,2,...,N)
Ví dụ:
IB1.inp
3 4
7 5 9
17 13 15 10
OB1.out
256
2
3
4
Bài 2: (7 điểm)
Cho 2 lưới ô vuông A và B cùng kích thước MxN, mỗi ô có chỉ nhận các giá trị 0 hoặc 1 (A khác B). Các ô lưới được đánh số từ trên xuống dưới, từ trái qua phải bắt đầu từ 1. Cho phép thực hiện phép biến đổi sau đây với lưới A:
- Chọn ô (i,j) và đảo giá trị của ô đó và các ô chung cạnh với nó (0 thành 1, 1 thành 0).
Hãy xác định xem bằng cách áp dụng dãy biến đổi trên có thể đưa A về B được hay không? Nếu có hãy chỉ ra cách sử dụng một số ít nhất phép biến đổi.
Dữ liệu: File văn bản IB2.inp
- Dòng đầu tiên ghi 2 số M, N (M, N <=100)
- M dòng tiếp theo, mỗi dòng một xâu N kí tự 0, 1 ứng với dùng tương ứng của A
- Tiếp theo là một dòng trống
- M dòng cuối mỗi dòng 1 xâu N kí tự 0, 1 ứng với dòng tương ứng của B.
Kết quả: File OB2.out
- Dòng đầu số nguyên k là số lượng phép biến đổi ít nhất cần áp dụng (k=0 nếu không biến đổi được)
- Dòng thứ i trong số k dòng tiếp theo ghi 2 số nguyên xác định ô cần chọn để thực hiện phép biến đổi.
ví dụ:
IB2.inp
4 5
1 0 0 0 0
1 0 0 0 0
0 1 0 0 0
0 1 0 0 0

0 0 0 0 0
0 0 0 0 0
0 0 1 0 0
0 0 0 0 0

OB2.out

2
2 1
3 2
Bài 3: (6 điểm)
Cho 2 số nguyên dương M, N (0<M,N<=100) và 2 dãy số nguyên a1, a2,...,aN và b1, b2,..., bM. Hãy loại đi một số phần tử của 2 dãy sao cho các số còn lại của 2 dãy (giữ nguyên thứ tự cũ) tạo thành 2 dãy như nhau và độ dài k là lớn nhất.
Dữ liệu: file IB3.inp
- Dòng thứ nhất ghi số N, M
- Các dòng tiếp theo của nó chứa dãy a1, a2,...,aN và b1, b2,..., bM
Kết quả: file OB3.out
- Dòng thứ nhất ghi số k
- Các dòng tiếp theo chứa k số còn lại của 1 dãy nào đó, các số cách nhau ít nhất một dấu cách.
Ví dụ:
IB3.inp
8 12
0 0 9 2 3 7 3 1
4 4 0 5 0 9 0 3 10 4 8 3

OB3.out
5
0 0 9 3 3