Đề thi học sinh giỏi môn Tin 12 - Sở GD&ĐT Long An

Chia sẻ: Gu Tin | Ngày: | Loại File: PDF | Số trang:10

Thêm vào BST

Báo xấu

383
lượt xem 73
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Đề thi học sinh giỏi môn Tin học lớp 12 của sở giáo dục và đào tạo tỉnh Long An dành cho các bạn học sinh lớp 12 giúp các em ôn tập lại kiến thức đã học và đồng thời giáo viên cũng có thêm tư liệu tham khảo trong việc ra đề thi.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Đề thi học sinh giỏi môn Tin 12 - Sở GD&ĐT Long An

Sở Giáo dục và Đào tạo Kỳ thi Tin học trẻ tỉnh Long An lần thứ 17 LONG AN Ngày thi : 17/3/2013 Thời gian: 150 phút (không kể phát đề) Bảng C – THPT ĐỀ CHÍNH THỨC Lưu ý: Thí sinh tạo thư mục là số báo danh của mình, làm bài và lưu với tên tập tin là bai1.pas, bai2.pas, bai3.pas vào thư mục số báo danh vừa tạo. Ví dụ thí sinh có số báo danh B52 thì tạo thư mục B52 rồi lưu bai1.pas, bai2.pas, bai3.pas vào thư mục B52. Bài 1: (6 điểm) Một xâu chữ cái được gọi là xâu số nếu sau khi xoá một vài kí tự ta thu được một trong các xâu sau: ONE, TWO, THREE, FOUR, FIVE, SIX, SEVEN, EIGHT hoặc NINE. Các xâu ONE, TWO, THREE, FOUR, FIVE, SIX, SEVEN, EIGHT, NINE được gọi là các từ số (tương ứng với các số nguyên 1, 2, 3, 4, 5, 6, 7, 8, 9). Ví dụ:  BOUNCE và ANNOUNCE là hai xâu số vì hai xâu này có chứa từ số ONE.  ENCODE không phải là xâu số, vì dù có chứa các kí tự O, N và E, nhưng vị trí các kí tự O, N và E trong xâu này không đúng thứ tự. Yêu cầu: Viết chương trình kiểm tra một xâu kí tự chữ cái in hoa được nhập vào từ bàn phím xem có phải là xâu số hay không. Nếu xâu được nhập vào là xâu số thì xuất ra màn hình một số nguyên tương ứng với từ số chứa trong xâu này. Nếu xâu được nhập vào không phải là xâu số thì xuất ra màn hình “KHONG”. Ví dụ: Dữ liệu nhập vào từ bàn phím Dữ liệu xuất ra màn hình BOUNCE 1 ENCODE KHONG Bài 2: (7 điểm) Một dãy số nguyên A: a1, a2,..., aN được gọi là dãy chia hết hoàn toàn nếu A có ít nhất 2 phần tử và mọi phần tử aj đều chia hết cho tất cả các phần tử ai đứng trước nó (1 ≤ i < j ≤ N). Một dãy con của A là một cách chọn ra trong A một số phần tử giữ nguyên thứ tự. Yêu cầu: Viết chương trình nhập vào một dãy số nguyên A: a1, a2,..., aN. Tìm dãy con chia hết hoàn toàn của A có độ dài lớn nhất. Ví dụ 1: Dãy A: 3, 5, 9, 7, 15, 18, 35, 54. Dãy con chia hết hoàn toàn dài nhất là: 3, 9, 18, 54. Ví dụ 2: Dãy A: 6, 9, 15. Không tìm được dãy con chia hết hoàn toàn. Dữ liệu vào: Cho trong file văn bản MULSEQ.IN gồm 2 dòng:  Dòng đầu tiên chứa số nguyên dương N (1 ≤ n ≤ 5000), là số lượng phần tử của dãy A.  Dòng thứ hai gồm N số nguyên a1, a2,..., aN ( -10000 ≤ ai ≤ 10000), các số được viết cách nhau ít nhất một dấu cách. Dữ liệu ra: Ghi ra file văn bản MULSEQ.OU: - Nếu tìm được dãy con chia hết hoàn toàn thì file MULSEQ.OU gồm 2 dòng: o Dòng đầu ghi độ dài của dãy con chia hết hoàn toàn dài nhất tìm được. o Dòng thứ hai ghi các phần tử được chọn vào dãy con này. - Nếu không tìm được dãy con chia hết hoàn toàn thì file MULSEQ.OU ghi số -1. Ví dụ 1 Ví dụ 2 MULSEQ.IN MULSEQ.OU MULSEQ.IN MULSEQ.OU 8 4 3 -1 3 5 9 7 15 18 35 54 3 9 18 54 6 9 15 Trang 1 - đề thi gồm có 2 trang ..
Bài 3: (7 điểm) Có M đoàn học sinh của các trường đến tham dự kì thi THT2013. Các trưởng đoàn đang xếp hàng tại khu vực nhà chờ để chờ đến lượt làm thủ tục đăng kí dự thi cho đoàn của trường mình. Có N bàn làm thủ tục đăng kí dự thi tại khu vực tiếp tân. Nhân viên tại bàn thứ k mất Tk giây để hoàn thành thủ tục đăng kí cho một đoàn bất kì. Bắt đầu giờ làm việc (tại thời điểm 0), tất cả các bàn đều có nhân viên trực sẵn sàng làm thủ tục và các trưởng đoàn đã xếp thành một hàng dọc tại khu vực nhà chờ. Một người chỉ có thể đến một bàn đang rỗi để làm thủ tục khi tất cả người phía trước mình trong hàng đợi đã rời khỏi hàng (có thể đang làm thủ tục ở một bàn nào đó hoặc đã làm xong thủ tục). Người ở đầu hàng đợi có thể chọn đến làm thủ tục tại một trong các bàn đang rỗi hoặc chờ một bàn đang bận cho đến khi nó rỗi. Tổng thời gian hoàn thành việc đăng kí cho tất cả các đoàn chính là khoảng thời gian từ thời điểm bắt đầu làm việc đến thời điểm trưởng đoàn cuối cùng làm xong thủ tục dự thi. Thật tuyệt vời là tất cả các trưởng đoàn đều là những chuyên gia tin học, vì vậy họ đều chọn đến làm thủ tục tại những bàn sao cho thời gian hoàn thành đăng kí dự thi cho tất cả các đoàn là ít nhất. Nhiệm vụ của bạn là giúp ban tổ chức tìm ra tổng thời gian ít nhất này (có thể xem thời gian di chuyển từ nhà chờ đến khu vực tiếp tân không đáng kể). Ví dụ: Có 6 đoàn và 2 bàn đăng kí dự thi với thời gian xử lí công việc là 7 giây và 10 giây. Tại thời điểm 0, hai trưởng đoàn đến đăng kí tại hai bàn. Tại thời điểm 7, bàn thứ nhất rỗi và trưởng đoàn thứ 3 đến làm thủ tục tại bàn này. Tại thời điểm 10, trưởng đoàn thứ 4 đến bàn thứ hai. Tại thời điểm 14, trưởng đoàn thứ 5 đến làm thủ tục tại bàn thứ nhất. Tại thời điểm 20, bàn thứ 2 rỗi, nhưng trưởng đoàn thứ 6 quyết định chờ đến thời điểm 21, đến bàn thứ nhất làm thủ tục. Theo cách này, thời gian hoàn thành thủ tục đăng kí cho tất cả các đoàn là 28 giây (Nếu trưởng đoàn thứ 6 không chờ mà quyết định đến bàn thứ nhất ở thời điểm 20 thì thời gian hoàn thành thủ tục đăng kí cho tất cả các đoàn là 30 giây). Dữ liệu vào: Cho trong file văn bản MOMENT.IN gồm N+1 dòng:  Dòng đầu tiên chứa 2 số nguyên dương N (1≤ N ≤ 100 000) – số bàn làm thủ tục đăng kí và M (1≤M≤1 000 000 000)- số đoàn tham dự kì thi.  N dòng tiếp theo, mỗi dòng gồm một số nguyên dương Tk – thời gian hoàn thành thủ tục đăng kí cho một đoàn học sinh của từng bàn (1 ≤ Tk ≤ 109, các số được viết cách nhau ít nhất một dấu cách.) Dữ liệu ra: Ghi ra màn hình một số nguyên duy nhất, là thời gian (tính bằng giây) ít nhất hoàn thành việc đăng kí cho tất cả các đoàn. Ví dụ 1: Ví dụ 2: Dữ liệu vào Dữ liệu vào 26 7 10 7 3 10 8 3 6 9 2 4 Dữ liệu ra Dữ liệu ra 28 8 ------------HẾT------------ (Giám thị coi thi không giải thích gì thêm) Trang 2 - đề thi gồm có 2 trang ..
Sở Giáo dục và Đào tạo Kỳ thi Tin học trẻ tỉnh Long An lần thứ 17 LONG AN Ngày thi : 17/3/2013 Thời gian: 150 phút (không kể phát đề) Bảng C – THPT ĐỀ CHÍNH THỨC HƯỚNG DẪN CHẤM Câu 1: (6 đ) Nhập được chuỗi cho 1 điểm Dữ liệu vào Dữ liệu ra Điểm EIGHT 8 1,0 EXERCISE KHONG 1,0 DRIFTWOOD 2 1,0 SERVICEMAN 7 1,0 INSIGNIFICANCE 9 1,0 Bài 2: (7 điểm) Nhập dữ liệu được 1.0 điểm Dữ liệu vào Dữ liệu ra Điểm Dữ liệu cho trong tập tin MULSEQ.IN1 MULSEQ.OU1 1,0 + 0,5 Dữ liệu cho trong tập tin MULSEQ.IN2 MULSEQ.OU2 1,0 +0,5 Dữ liệu cho trong tập tin MULSEQ.IN3 MULSEQ.OU3 1,0 +0,5 Dữ liệu cho trong tập tin MULSEQ.IN4 -1 1,5 Bài 3: (7 điểm) Nhập dữ liệu được 1.0 điểm Dữ liệu vào Dữ liệu ra Điểm Dữ liệu cho trong tập tin moment.in1 55 2,0 Dữ liệu cho trong tập tin moment.in2 1446 1,5 Dữ liệu cho trong tập tin moment.in4 77148156 1,5 Dữ liệu cho trong tập tin moment.in6 72115316 1,0 Lưu ý: Giải quyết trường hợp đồng điểm: Giám khảo xem xét thuật giải của thí sinh để giải quyết -----HẾT----- .
Sở Giáo dục và Đào tạo Kỳ thi Tin học trẻ tỉnh Long An lần thứ 17 LONG AN Ngày thi : 17/3/2013 Thời gian: 150 phút (không kể phát đề) Bảng C – THPT ĐỀ CHÍNH THỨC Lưu ý: Thí sinh tạo thư mục là số báo danh của mình, làm bài và lưu với tên tập tin là bai1.pas, bai2.pas, bai3.pas vào thư mục số báo danh vừa tạo. Ví dụ thí sinh có số báo danh B52 thì tạo thư mục B52 rồi lưu bai1.pas, bai2.pas, bai3.pas vào thư mục B52. Bài 1: (6 điểm) Một xâu chữ cái được gọi là xâu số nếu sau khi xoá một vài kí tự ta thu được một trong các xâu sau: ONE, TWO, THREE, FOUR, FIVE, SIX, SEVEN, EIGHT hoặc NINE. Các xâu ONE, TWO, THREE, FOUR, FIVE, SIX, SEVEN, EIGHT, NINE được gọi là các từ số (tương ứng với các số nguyên 1, 2, 3, 4, 5, 6, 7, 8, 9). Ví dụ:  BOUNCE và ANNOUNCE là hai xâu số vì hai xâu này có chứa từ số ONE.  ENCODE không phải là xâu số, vì dù có chứa các kí tự O, N và E, nhưng vị trí các kí tự O, N và E trong xâu này không đúng thứ tự. Yêu cầu: Viết chương trình kiểm tra một xâu kí tự chữ cái in hoa được nhập vào từ bàn phím xem có phải là xâu số hay không. Nếu xâu được nhập vào là xâu số thì xuất ra màn hình một số nguyên tương ứng với từ số chứa trong xâu này. Nếu xâu được nhập vào không phải là xâu số thì xuất ra màn hình “KHONG”. Ví dụ: Dữ liệu nhập vào từ bàn phím Dữ liệu xuất ra màn hình BOUNCE 1 ENCODE KHONG Bài 2: (7 điểm) Một dãy số nguyên A: a1, a2,..., aN được gọi là dãy chia hết hoàn toàn nếu A có ít nhất 2 phần tử và mọi phần tử aj đều chia hết cho tất cả các phần tử ai đứng trước nó (1 ≤ i < j ≤ N). Một dãy con của A là một cách chọn ra trong A một số phần tử giữ nguyên thứ tự. Yêu cầu: Viết chương trình nhập vào một dãy số nguyên A: a1, a2,..., aN. Tìm dãy con chia hết hoàn toàn của A có độ dài lớn nhất. Ví dụ 1: Dãy A: 3, 5, 9, 7, 15, 18, 35, 54. Dãy con chia hết hoàn toàn dài nhất là: 3, 9, 18, 54. Ví dụ 2: Dãy A: 6, 9, 15. Không tìm được dãy con chia hết hoàn toàn. Dữ liệu vào: Cho trong file văn bản MULSEQ.IN gồm 2 dòng:  Dòng đầu tiên chứa số nguyên dương N (1 ≤ n ≤ 5000), là số lượng phần tử của dãy A.  Dòng thứ hai gồm N số nguyên a1, a2,..., aN ( -10000 ≤ ai ≤ 10000), các số được viết cách nhau ít nhất một dấu cách. Dữ liệu ra: Ghi ra file văn bản MULSEQ.OU: - Nếu tìm được dãy con chia hết hoàn toàn thì file MULSEQ.OU gồm 2 dòng: o Dòng đầu ghi độ dài của dãy con chia hết hoàn toàn dài nhất tìm được. o Dòng thứ hai ghi các phần tử được chọn vào dãy con này. - Nếu không tìm được dãy con chia hết hoàn toàn thì file MULSEQ.OU ghi số -1. Ví dụ 1 Ví dụ 2 MULSEQ.IN MULSEQ.OU MULSEQ.IN MULSEQ.OU 8 4 3 -1 3 5 9 7 15 18 35 54 3 9 18 54 6 9 15 Trang 1 - đề thi gồm có 2 trang ..
Bài 3: (7 điểm) Có M đoàn học sinh của các trường đến tham dự kì thi THT2013. Các trưởng đoàn đang xếp hàng tại khu vực nhà chờ để chờ đến lượt làm thủ tục đăng kí dự thi cho đoàn của trường mình. Có N bàn làm thủ tục đăng kí dự thi tại khu vực tiếp tân. Nhân viên tại bàn thứ k mất Tk giây để hoàn thành thủ tục đăng kí cho một đoàn bất kì. Bắt đầu giờ làm việc (tại thời điểm 0), tất cả các bàn đều có nhân viên trực sẵn sàng làm thủ tục và các trưởng đoàn đã xếp thành một hàng dọc tại khu vực nhà chờ. Một người chỉ có thể đến một bàn đang rỗi để làm thủ tục khi tất cả người phía trước mình trong hàng đợi đã rời khỏi hàng (có thể đang làm thủ tục ở một bàn nào đó hoặc đã làm xong thủ tục). Người ở đầu hàng đợi có thể chọn đến làm thủ tục tại một trong các bàn đang rỗi hoặc chờ một bàn đang bận cho đến khi nó rỗi. Tổng thời gian hoàn thành việc đăng kí cho tất cả các đoàn chính là khoảng thời gian từ thời điểm bắt đầu làm việc đến thời điểm trưởng đoàn cuối cùng làm xong thủ tục dự thi. Thật tuyệt vời là tất cả các trưởng đoàn đều là những chuyên gia tin học, vì vậy họ đều chọn đến làm thủ tục tại những bàn sao cho thời gian hoàn thành đăng kí dự thi cho tất cả các đoàn là ít nhất. Nhiệm vụ của bạn là giúp ban tổ chức tìm ra tổng thời gian ít nhất này (có thể xem thời gian di chuyển từ nhà chờ đến khu vực tiếp tân không đáng kể). Ví dụ: Có 6 đoàn và 2 bàn đăng kí dự thi với thời gian xử lí công việc là 7 giây và 10 giây. Tại thời điểm 0, hai trưởng đoàn đến đăng kí tại hai bàn. Tại thời điểm 7, bàn thứ nhất rỗi và trưởng đoàn thứ 3 đến làm thủ tục tại bàn này. Tại thời điểm 10, trưởng đoàn thứ 4 đến bàn thứ hai. Tại thời điểm 14, trưởng đoàn thứ 5 đến làm thủ tục tại bàn thứ nhất. Tại thời điểm 20, bàn thứ 2 rỗi, nhưng trưởng đoàn thứ 6 quyết định chờ đến thời điểm 21, đến bàn thứ nhất làm thủ tục. Theo cách này, thời gian hoàn thành thủ tục đăng kí cho tất cả các đoàn là 28 giây (Nếu trưởng đoàn thứ 6 không chờ mà quyết định đến bàn thứ nhất ở thời điểm 20 thì thời gian hoàn thành thủ tục đăng kí cho tất cả các đoàn là 30 giây). Dữ liệu vào: Cho trong file văn bản MOMENT.IN gồm N+1 dòng:  Dòng đầu tiên chứa 2 số nguyên dương N (1≤ N ≤ 100 000) – số bàn làm thủ tục đăng kí và M (1≤M≤1 000 000 000)- số đoàn tham dự kì thi.  N dòng tiếp theo, mỗi dòng gồm một số nguyên dương Tk – thời gian hoàn thành thủ tục đăng kí cho một đoàn học sinh của từng bàn (1 ≤ Tk ≤ 109, các số được viết cách nhau ít nhất một dấu cách.) Dữ liệu ra: Ghi ra màn hình một số nguyên duy nhất, là thời gian (tính bằng giây) ít nhất hoàn thành việc đăng kí cho tất cả các đoàn. Ví dụ 1: Ví dụ 2: Dữ liệu vào Dữ liệu vào 26 7 10 7 3 10 8 3 6 9 2 4 Dữ liệu ra Dữ liệu ra 28 8 ------------HẾT------------ (Giám thị coi thi không giải thích gì thêm) Trang 2 - đề thi gồm có 2 trang ..
Sở Giáo dục và Đào tạo Kỳ thi Tin học trẻ tỉnh Long An lần thứ 17 LONG AN Ngày thi : 17/3/2013 Thời gian: 150 phút (không kể phát đề) Bảng C – THPT ĐỀ CHÍNH THỨC HƯỚNG DẪN CHẤM Câu 1: (6 đ) Nhập được chuỗi cho 1 điểm Dữ liệu vào Dữ liệu ra Điểm EIGHT 8 1,0 EXERCISE KHONG 1,0 DRIFTWOOD 2 1,0 SERVICEMAN 7 1,0 INSIGNIFICANCE 9 1,0 Bài 2: (7 điểm) Nhập dữ liệu được 1.0 điểm Dữ liệu vào Dữ liệu ra Điểm Dữ liệu cho trong tập tin MULSEQ.IN1 MULSEQ.OU1 1,0 + 0,5 Dữ liệu cho trong tập tin MULSEQ.IN2 MULSEQ.OU2 1,0 +0,5 Dữ liệu cho trong tập tin MULSEQ.IN3 MULSEQ.OU3 1,0 +0,5 Dữ liệu cho trong tập tin MULSEQ.IN4 -1 1,5 Bài 3: (7 điểm) Nhập dữ liệu được 1.0 điểm Dữ liệu vào Dữ liệu ra Điểm Dữ liệu cho trong tập tin moment.in1 55 2,0 Dữ liệu cho trong tập tin moment.in2 1446 1,5 Dữ liệu cho trong tập tin moment.in4 77148156 1,5 Dữ liệu cho trong tập tin moment.in6 72115316 1,0 Lưu ý: Giải quyết trường hợp đồng điểm: Giám khảo xem xét thuật giải của thí sinh để giải quyết -----HẾT----- .
Sở Giáo dục và Đào tạo Kỳ thi Tin học trẻ tỉnh Long An lần thứ 17 LONG AN Ngày thi: 17/3/2013 Bảng A: Cấp tiểu học Thời gian: 90 phút (không kể thời gian phát đề) ĐỀ CHÍNH THỨC Phần I: Yêu cầu chung (1.0 điểm) Em hãy tạo thư mục số báo danh của mình vào ổ đĩa D:\ Ví dụ: Em có số báo danh là A01 thì tạo thư mục D:\A01 Phần II: (7.0 điểm) Em hãy sử dụng chương trình Paint để vẽ chủ đề: “Con đường đến trường em”. Lưu tập tin vào thư mục số báo danh mà em đã tạo ở phần I với tên HINHVE.BMP Phần III: Bài toán Dùng phần mềm OpenOffice.org Writer để ghi lời giải của 02 bài toán sau và lưu vào thư mục số báo danh mà em đã tạo ở phần I với tên BAITOAN Bài 1. (6.0 điểm) Trò chơi xoá số Cho một số tự nhiên có 15 chữ số: 652831568497951. Yêu cầu: Xoá khỏi số trên 10 chữ số để số thu được là số nhỏ nhất có thể. Lưu ý: Học sinh ghi lại tiến trình xoá để thu được kết quả (mỗi lượt xoá một số): Ví dụ: Lượt 1: xoá số 6 (652831568497951) ->52831568497951 Lượt 2: xoá số 8 (52831568497951) ->5231568497951 ----------- Bài 2: (6.0 điểm) Ngày xưa, ở một vương quốc xa xôi nọ, có một Hoàng tử vô cùng hiếu thảo. Ngày kia, vua cha lâm bệnh nặng, Hoàng tử đã đi khắp nơi tìm thầy thuốc giỏi chữa bệnh cho đức vua. Động lòng trước tấm lòng hiếu thảo của Hoàng tử, Bụt hiện ra trao cho Hoàng tử một cuộn giấy và một tấm bản đồ. Cuộn giấy có ghi dòng kí tự sau: IIIIIIIVVVIVIIVIIIIXXXIXIIXIIIXIVXV Tấm bản đồ như hình bên Bụt nói với Hoàng tử: “Hiện tại con đang đứng ở vị trí có hình  trên I V   I bản đồ. Mỗi ô vuông trong bản đồ chứa một trong các kí tự I, V, X, . Từ một ô, con chỉ có thể bước tới ô bên trái hoặc phải hoặc bên trên hoặc bên dưới của ôI I I  I hiện thời. Con hãy đọc các kí tự ghi trong cuộn giấy theo thứ tự từ trái sang phải vàX V V  I bước vào các ô trên bản đồ có kí tự tương ứng, mỗi ô có thể đi qua nhiều lần. Khi gặp kí tự  trên bản đồ, con có thể lấy được một lọ thuốc cho đức vua. I     Đường đi của con kết thúc khi con không tìm thấy ô nào trên bản đồ để bước  I   I tới” Ví dụ: Từ ô có hình  , Hoàng tử có thể đi từng bước như sau: dưới – dưới- phải-phải-trên- trên- trên – trên – trái. Qua 8 bước đi này, Hoàng tử có thể lấy được 3 lọ thuốc cho đức vua. Dựa vào dòng kí tự trên cuộn giấy và tấm bản đồ, em hãy giúp Hoàng tử tìm ra một đường đi để lấy được nhiều lọ thuốc nhất.  Chú ý: cách trình bày lời giải Đường đi từng bước: ... Số lọ thuốc lớn nhất lấy được là: ... -----HẾT-----
SỞ GIÁO DỤC VÀ ĐÀO TẠO KÌ THI CHỌN HỌC SINH GIỎI LỚP 12 VÒNG 2 LONG AN Ngày thi: 10/11/2011 Môn thi: TIN HỌC ĐỀ CHÍNH THỨC Thời gian: 180 phút (không kể thời gian phát đề) Câu 1: (6 điểm) DAYSO.PAS Cho dãy số nguyên A gồm n phần tử a 1,a2, .., an, tìm số cặp chỉ số (i, j) thỏa mãn: S= ai+ai+1+ai+2+… + a j-1+a j đạt giá trị lớn nhất (với 1 ≤ i < j ≤ n). Dữ liệu: Vào từ file văn bản DAYSO.INP - Dòng đầu là số nguyên dương n (2 ≤ n ≤ 10 5) - Dòng tiếp theo chứa n số nguyên a 1, a2, .., an (|ai|
2 5 Thật không may là vẫn Lối vào chưa có chàng trai nào hoàn hành nhiệm vụ nhà 3 vua đã trao và công chúa Phòng công chúa vẫn phải trông chờ, hy 1 4 vọng một khi nào đó sẽ có kết cục tốt đẹp. Tại sao bạn lại không thử vận may của mình xem sao? Bạn có thể lập trình để trợ giúp cho nàng công chúa tội nghiệp ấy. Yêu cầu: Chỉ ra dãy phòng cần ghé xem trên đường đi tới phòng công chúa và tiêu hết đúng số tiền trong túi được trao. Dữ liệu vào đảm bảo có lời giải. Nếu có nhiều lời giải thì chỉ cần nêu một trong số đó. Dữ liệu: Vào từ file văn bản CASTLE.INP:  Dòng đầu tiên có 5 số nguyên n, m, e, p, b, 1≤n≤100, 1≤m≤4950, 1≤e,p≤n, 1≤b≤1000, trong đó n - số phòng, m - số hành lang, các phòng được đánh số từ 1 đến n, e – phòng vào lâu đài, p- phòng có công chúa, b - số Bytealer trong túi;  Dòng thứ 2 chứa n số nguyên dương c1, c2,..., cn, 1≤ci≤1000, ci - tiền cần trả để vào xem phòng i;  m dòng tiếp theo: mỗi dòng chứa một cặp số nguyên dương x, y, (xy, 1≤x,y≤n),cho biết có hành lang nối 2 phòng x và y. Các số trên một dòng các nhau ít nhất một dấu cách. Kết quả: Đưa ra file văn bản CASTLE.OUT dãy số nguyên xác định các phòng cần ghé từ, đi từ e đến p. Ví dụ: CASTLE.INP CASTLE.OUT 5 6 3 4 9 3 2 4 1 2 3 4 5 2 4 5 4 1 5 1 2 2 3 3 1 Câu 3: (7 điểm) CHIEUSANG.PAS Một đoạn đường thẳng có N trạm, người ta muốn đặt các đèn tại một số trạm để có thể chiếu sáng được tất cả các trạm. Trên thị trường có M loại đèn, loại thứ i có giá là Ti và có khả năng chiếu sáng với bán kính Ri. Một trạm được đặt đèn i thì nó có khả năng chiếu sáng cho chính nó và các trạm ở bên trái và bên phải nếu khoảng cách từ trạm đặt đèn tới các trạm bên trái và bên phải nhỏ hơn hoặc bằng Ri. Công việc của bạn là lập trình tìm cách mua các đèn và đặt vào một số trạm để cho tất cả các trạm đều được chiếu sáng với ít tiền nhất. Trang 2 | 3
Dữ liệu: Vào từ file văn bản CHIEUSANG.INP có dạng: - Dòng thứ nhất là hai số N, M (N ≤ 10000, M ≤ 10). - Dòng thứ 2 chứa 2 nguyên là giá tiền và khả năng chiếu sáng của đèn thứ 1,…, dòng thứ M+1 là giá tiền và khả năng chiếu sáng của đèn thứ M. Như vậy M dòng kế tiếp, mỗi dòng chứa hai số nguyên dương. Dòng thứ i+1 là giá tiền Ti và khả năng chiếu sáng Ri của đèn thứ i. (Ti ≤ 30000, Ri ≤ 10 9). - Dòng thứ M+2 có một số nguyên dương - là toạ độ của trạm thứ 1,…, dòng thứ M+N+1 có một số nguyên dương – là toạ độ của trạm thứ N. Như vậy, N dòng tiếp theo, mỗi dòng một số nguyên dương mô tả vị trí (toạ độ) của N trạm. Dòng thứ i+M+1 chứa giá trị d i là toạ độ của trạm thứ i (0 ≤ di ≤ 109). Trong ví dụ bên dưới: dòng thứ nhất là N=6 trạm, M=2 loại đèn; dòng thứ 2 là giá tiền và khả năng chiếu sáng của loại đèn thứ nhất, dòng thứ 3 là giá tiền và khả năng chiếu sáng của loại đèn thứ hai; 6 dòng tiếp theo là toạ độ của 6 trạm. Kết quả: Đưa ra file văn bản CHIEUSANG.OUT có dạng: - Dòng thứ nhất gồm hai số nguyên: số thứ nhất là số tiền ít nhất và số thứ 2 là số đèn W cần dựng. - W dòng tiếp theo, mỗi dòng hai số là tên trạm và loại đèn đặt tại trạm đó. Ví dụ: CHIEUSANG.INP CHIEUSANG.OUT Giải thích 62 84 Số tiền ít nhất là 8, cần 21 21 dựng 4 đèn tại các trạm 2, 100 10 41 4, 5, 6 và chỉ sử dụng loại 1 51 đèn thứ 1 2 61 3 10 20 30 -----HẾT----- Thí sinh không được sử dụng tài liệu. Giám thị không giải thích gì thêm Họ tên thí sinh:…………………………………SBD……………………………………. Giám thị 1:…………………………………Giám thị 2:………………………………….. Trang 3 | 3