Với cấu trúc gồm 3 chương trong thời gian làm bài 180 phút, đề thi chọn học sinh giỏi lớp 12 "Môn Tin học" năm học 2012-2013 dưới đây để củng cố lại kiến thức lý thuyết đã học và làm quen với dạng đề thi. | SỞ GIÁO DỤC & ĐÀO TẠO QUẢNG NAM KỲ THI CHỌN HỌC SINH GIỎI LỚP 12 THPT Năm học 2012-2013 Môn thi : TIN HỌC Thời gian : 180 phút (không kể thời gian giao đề) Ngàythi : 02/11/2012 (Đề này có 02 trang) Bài 1 (6 điểm- Tham quan) Một trường học có N ô tô dùng để chuyên chở học sinh tham quan. Ô tô thứ i có thể chở tối đa là bi (i=1,,N) học sinh. Để tiết kiệm chi phí vận chuyển, nhà trường muốn các xe phải được chở tối đa học sinh. Tuy nhiên, trước lúc khởi hành, học sinh vì quá háo hức nên tự lên xe mà không chờ nhà trường sắp xếp. Kết quả là có một số xe không chở tối đa học sinh như ý muốn. Yêu cầu : Hãy sắp xếp lại số học sinh sao cho số xe chở học sinh không đạt tối đa là ít nhất. Dữ liệu vào : File text, tên file là , gồm 2 dòng: ● Dòng đầu ghi số nguyên dương N (0< N≤ 10000) ● Dòng thứ i trong N dòng tiếp theo ghi hai số nguyên ai , bi là số học sinh lên xe thứ i và số người tối đa mà xe thứ i có thể chở ( 0≤ ai ≤ 50; 0< bi ≤ 50; ai ≤ bi ) Dữ liệu ra : File text, tên file là BL1. OUT, gồm một số nguyên duy nhất là số xe ít nhất không chở tối đa học sinh. Ví dụ: 4 0 1 3 5 0 2 1 2 2 Bài 2 (7 điểm- Rô bốt) Trên một bảng vuông NxN ta đặt N2 kí tự chữ cái in hoa (A, B, C,., Z). Một rô bốt xuất phát từ ô trên trái (ô (1,1)) và lần lượt đi qua các ô kề cạnh với ô đang đứng, đi đến đâu rô bốt nhặt kí tự ở ô đó. Do mỗi kí tự rô bốt chỉ được phép nhặt một lần, nên rô bốt chỉ đi đến được những ô chứa kí tự mà nó chưa nhặt lần nào. Yêu cầu : Hãy xác định số kí tự tối đa mà rô bốt nhặt được. Dữ liệu vào: File text, tên file là Dòng đầu ghi số N (0< N ≤100). N dòng tiếp theo mỗi dòng ghi N kí tự chữ cái in hoa liên tiếp nhau. Dữ liệu ra : File text, tên file là , gồm một số duy nhất là số kí tự mà rô bốt nhặt được. Ví dụ : 4 ABCA CBCD ADDB CEFD 6 Bài 3 (7 điểm- Trò chơi bốc sỏi) Một trò chơi bốc sỏi rất đặc biệt được mô tả như sau. Trên một băng hình chữ nhật được chia ra thành N ô vuông và được đánh số từ trái qua phải, bắt đầu từ 1. Trên ô vuông thứ i người ta đặt một lượng sỏi là ai (i =1, 2,, N). Người chơi được phép chọn một dãy ô bất kì (từ trái qua phải), không nhất thiết phải liên tục, theo quy luật: ô chọn đầu tiên người chơi được bốc một lượng sỏi là ai1, ô chọn tiếp theo người chơi sẽ bỏ vào ô đó một lượng sỏi là ai2, ô chọn tiếp theo người chơi sẽ được bốc một lượng sỏi là ai3, . và cứ tiếp tục như thế cho đến ô chọn cuối cùng. Giả sử theo thứ tự từ trái qua phải, người chơi lựa chọn các ô được đánh số là i1, i2, ., ik . Khi đó số sỏi mà người chơi có được sẽ là: ai1 - ai2 + ai3 - .+ (-1)k-1aik Yêu cầu: Hãy tính số lượng sỏi nhiều nhất có thể đạt được từ một lượt chơi. Dữ liệu vào: File text, tên file là Dòng đầu tiên chứa số nguyên dương N ( 0< N ≤ 106 ) là số lượng ô của băng. Dòng thứ hai chứa N số nguyên dương ai (ai ≤ 103). Các số liên tiếp trên cùng một dòng được ghi cách nhau ít nhất một dấu cách. Dữ liệu ra: File text, tên file là , gồm một số nguyên duy nhất là số sỏi mà người chơi có được trong một lượt chơi. Ví dụ : 7 4 8 2 4 1 3 7 16 ----------------------------------------------Hết----------------------------------------------------- Hạn chế kỹ thuật: - Ghi tên tập tin bài làm tương ứng là: BAI1.*, BAI2.* và BAI3.* (trong đó * là phần mở rộng tùy thuộc ngôn ngữ Pascal hoặc C++ ) - Thời gian chạy trên máy mỗi bài không quá 30 giây cho mỗi bộ dữ liệu.
