Đề thi chọn đội tuyển học sinh giỏi quốc gia môn Tin học Lớp 12 - Năm học 2011-2012 - Sở GD&ĐT Ninh Bình (Có đáp án)

SỞ GD&ĐT NINH BÌNH
ĐỀ CHÍNH THỨC
ĐỀ THI CHỌN ĐỘI TUYỂN CHÍNH THỨC DỰ THI HỌC SINH GIỎI QUỐC GIA
Năm học: 2011 - 2012
Môn: Tin học
Thời gian làm bài: 180 phút.
(Đề thi gồm 03 bài trong 02 trang)
Tổng quan đề thi:
Bài
Chương trình
Input
Output
Thời gian 
Lát viền
BRICK.PAS
BRICK.INP
BRICK.OUT
01 giây/test
Trái phiếu
OBL.PAS
OBL.INP
OBL.OUT
 01 giây/test
Tăng lương
SALARY.PAS
SALARY.INP
SALARY.OUT
04 giây/test
Bài 1: Lát viền (7 điểm).
 Người ta cần lát kín đường viền trang trí trong công viên có kích thước 2 x n bằng n viên gạch kích thước 2 x 1 (trong hình dưới là các cách lát cho trường hợp n = 3).
Yêu cầu: Cho biết n, hãy xác định số cách lát khác nhau.
Dữ liệu vào: Cho trong file BRICK.INP gồm một số nguyên dương n (n < 10000).
Dữ liệu ra: Ghi ra file BRICK.OUT một số nguyên duy nhất là đáp án của bài toán.
Ví dụ:
BRICK.INP
BRICK.OUT
3
3
Bài 2: Trái phiếu (7 điểm).	 
 Rôn tốt nghiệp khoa kinh tế với bằng xuất sắc và quyết định khởi nghiệp bằng việc tham gia thị trường mua bán trái phiếu ngắn hạn của chính phủ. Nguyên tắc của thị trường trái phiếu chính phủ là nếu ngày nào bạn đăng ký tham gia thì phải mua hoặc bán đúng một trái phiếu. Trong một ngày giá bán hay mua là giống nhau. Qua nghiên cứu tìm hiểu, Rôn thấy rằng trái phiếu lên giá hàng ngày. Hiện nay mỗi trái phiếu có giá là 1, ngày mai giá mỗi trái phiếu sẽ là 2, đến ngày thứ m giá sẽ là m.
 Trong tay Rôn hiện đang có số tiền mặt là n và một số lượng trái phiếu lớn hơn k. Rôn quyết định đăng ký tham gia thị trường Trái phiếu trong k ngày liên tiếp kể từ hôm nay với quy tắc hành động hết sức đơn giản: mỗi ngày nếu còn đủ tiền mặt để mua thì sẽ mua, trong trường hợp ngược lại sẽ bán. Ví dụ, với n = 7 và k = 4, hôm nay Rôn sẽ mua và số tiền còn lại trong túi là 6, hai ngày nữa Rôn cũng sẽ mua với chi phí là 2 và 3, tiền mặt còn lại là 1. Ở ngày thứ tư Rôn bán trái phiếu và có số tiền mặt là 5.
Yêu cầu: Cho n, k (1 ≤ n, k ≤ 1015). Hãy xác định số tiền mặt Rôn có ở cuối ngày thứ k.
Dữ liệu: Vào từ file văn bản OBL.INP gồm một dòng chứa 2 số nguyên n và k.
Kết quả: Đưa ra file văn bản OBL.OUT một số nguyên là số tiền mặt Rôn có ở cuối ngày thứ k.
Ví dụ:
OBL.INP
OBL.OUT
7 4
5
Bài 3: Tăng lương (6 điểm).
 Steve là ông chủ kiêu hãnh của một công ty phần mềm lớn. Ban đầu công ty chỉ có một mình Steve. Công việc làm ăn phát đạt và công ty thuê n công nhân, lần lượt từng người, từng người một. Steve được đánh số là 0. Các công nhân khác – đánh số từ 1 đến n theo trình tự thuê. Mỗi người mới vào có một mức lương khởi điểm và chịu sự chỉ đạo của một ai đó trong công ty. Nếu lương công nhân cao hơn lương thủ trưởng trực tiếp của mình thì lương của người thủ trưởng đó được nâng lên bằng lương người dưới quyền mình. Quá trình điều chỉnh này được tiếp diễn cho đến khi đảm bảo được trong toàn công ty lương thủ trưởng không thấp hơn lương công nhân dưới quyền.
Yêu cầu: Với mỗi công nhân được tuyển chọn vào công ty hãy xác định số người phải điều chỉnh lương cho phù hợp với người mới được tuyển chọn.
Dữ liệu: Vào từ file văn bản SALARY.INP:
Dòng đầu tiên chứa số nguyên n (1 ≤ n ≤ 300 000),
Dòng thứ 2 chứa một số nguyên – lương khởi điểm của Steve,
Dòng thứ i trong n dòng sau chứa 2 số nguyên S và B – lương khởi điểm và thủ trưởng của người công nhân thứ i.
Lương khởi điểm nằm trong phạm vi từ 1 đến 109.
Kết quả: Đưa ra file văn bản SALARY.OUT n số số nguyên, mỗi số trên một dòng, là kết quả tính được đối với mỗi người.
Ví dụ: 
SALARY.INP
SALARY.OUT
7
5000
4500 0
6000 0
4000 1
5500 3
7000 4
6300 2
6300 2
0
1
0
2
4
1
0
------------------------------Hết-------------------------------
Chú ý: Giám thị coi thi không giải thích gì thêm.
Họ và tên thí sinh:.........................................................Số báo danh:..............................................
Giám thị số 1:.....................................................Giám thị số 2:.......................................................
Hướng dẫn giải
Bài1:
const
 iFn = 'brick.inp';
 oFn = 'brick.out';
type
 BigNum = QWord; {Cần cài đặt kiểu số nguyên lớn}
procedure Add(var a, b: BigNum); 
{Cần cài đặt phép cộng kiểu số nguyên lớn}
begin
 a := a + b;
end;
procedure Print(F: Text; var a: BigNum); 
{Cần cài đặt write ra file kiểu số nguyên lớn}
begin
 Write(F, a);
end;
var
 n: Integer;
 a, b, c: BigNum;
procedure readInp;
var 
 F: Text;
begin
 Assign(F, iFn); Reset(F);
 ReadLn(F, n);
 Close(F);
end;
procedure process;
var
 i: Integer;
begin
 if n = 1 then c := 1
 else
 if n = 2 then c := 2
 else
 begin
 a := 1; b := 2;
 end;
 for i:=3 to n do
 begin
 c := b; 
 add(c, b);
 a := b;
 b := c; 
 end;
end;
procedure writeOut;
var 
 F: Text;
begin
 Assign(F, iFn); Rewrite(F);
 Print(F, c);
 Close(F);
end;
BEGIN
 readInp;
 process;
 writeOut;
END.
program obl;
 const
 fi = 'obl.inp';
 fo = 'obl.out';
 max = 100000000;
 var
 n, k : int64;
 kq : int64;
 f1, f2 : text;
 procedure openf;
 begin
 assign(f1, fi);
 reset(f1);
 assign(f2, fo);
 rewrite(f2);
 end;
 procedure closef;
 begin
 close(f1);
 close(f2);
 end;
 procedure input;
 begin
 read(f1, n, k);
 end;
 procedure output;
 begin
 write(f2, kq);
 end;
 procedure process;
 var
 l, m, r : int64;
 begin
 l := 1;
 r := max;
 repeat
 m := (l + r) div 2;
 if m * (m + 1) div 2 <= n then
 l := m
 else
 r := m;
 until l + 1 = r;
 if k <= l then
 begin
 kq := n - k * (k + 1) div 2;
 exit;
 end;
 n := n - l * (l + 1) div 2;
 while k > l + 2 * n do
 begin
 l := l + 2 * n + 1;
 n := l;
 end;
 r := k - l;
 if r and 1 = 1 then
 kq := n + l + r div 2 + 1
 else
 kq := n - r div 2;
 end;
 begin
 openf;
 input;
 process;
 output;
 closef;
 end.
Bài 3:
 program salary;
const
 nfin = 'SALARY.INP';
 nfout = 'SALARY.OUT';
 maxn = 300010;
 logn = 20;
var
 pa: array[0..maxn] of longint;
 sal: array[0..maxn] of longint;
 n, u, v, cnt: longint;
 fin, fout: text;
begin
 assign(fin, nfin); reset(fin);
 assign(fout, nfout); rewrite(fout);
 readln(fin, n);
 readln(fin, sal[0]);
 for u:=1 to n do begin
 readln(fin, sal[u], v);
 pa[u]:=v;
 cnt:=0;
 while (sal[v] < sal[u]) do begin
 inc(cnt);
 sal[v]:=sal[u];
 if (v = 0) then break
 else v:=pa[v];
 end;
 writeln(fout, cnt);
 end;
 close(fout);
 close(fin);
end.
Bài 1: Chọn đội tuyển
 Ba môn thi đồng đội chính trong Hội khỏe Phù Đổng ngành Giáo Dục Ninh Bình năm nay là kéo tay trên xà, nằm sấp chống tay và nhảy ngựa gỗ. Đội tuyển của mỗi đơn vị sẽ gồm 3 vận động viên. Ở mỗi môn tất cả các thành viên trong đội đều phải tham gia thi. Điểm của các vận động viên được tính như sau: mỗi lần kéo tay trên xà được tính X điểm, mỗi lần nằm sấp chống tay được tính Y điểm và mỗi lần nhảy ngựa thành công được Z điểm. Điểm của mỗi đội là tổng điểm của cả ba thành viên. 
 Thành phố Ninh Bình có n học sinh thể lực tốt, có thể chọn đi thi. Học sinh thứ i có thể kéo tay trên xà Ai lần, nằm sấp chống tay Bi lần và nhảy ngựa Ci lần. Tuy nhiên rất khó thành lập đội tuyển vì người kéo tay tốt thì nằm sấp chống tay lại không xuất sắc, người chống tay tốt thì khả năng nhảy ngựa không cao. . .
Yêu cầu: Cho các số nguyên n, X, Y, Z, Ai, Bi, Ci ( i = 1 ÷ n, 3 ≤ n ≤ 105). Hãy chỉ ra 3 học sinh để thành lập đội tuyển có thể giành số điểm cao nhất.
Dữ liệu vào: Từ file văn bản TEAM.INP:
Dòng đầu tiên chứa 3 số nguyên X, Y, Z (1 ≤ X, Y, Z ≤ 104),
Dòng thứ 2 chứa số nguyên n,
Dòng thứ i trong n dòng sau chứa 3 số nguyên Ai, Bi, Ci (1 ≤ Ai, Bi, Ci ≤ 104).
Dữ liệu ra: Ghi ra file văn bản TEAM.OUT trên một dòng 3 số nguyên – số thứ tự của các học sinh được chọn. Các học sinh được đánh số từ 1 và có thứ tự trùng với trình tự xác định trong file input. Các số được đưa ra theo thứ tự tăng dần. Nếu có nhiều cách chọn thì đưa ra một cách chọn tùy ý.
 Ví dụ:
TEAM.INP
TEAM.OUT
2 3 2
6
3 1 4
5 1 1
2 3 2
3 2 3
2 3 2
1 4 1
3 4 5