S GD&ĐT NINH BÌNHỞĐ THI CH N H C SINH GI I L P 12 THPT Ề Ọ Ọ Ỏ Ớ
K thi th hai - ỳ ứ Năm h c 2012 – 2013ọ
MÔN: TIN H CỌ
Ngày thi: 18/12/2012
(Th i gian làm bài: 180 phút)ờ
Đ thi g m 03 câu, trong 01 trangề ồ
Câu 1 (7 đi m):ể Di n tích đa giác (file bài làm: bai1.pas)ệ
Tính di n tích đa giác l i N đnh: Aệ ồ ỉ 1A2A3...AN, bi t các đnh Aế ỉ i (1 i N) có t a đ (xọ ộ i; yi).
D li u:ữ ệ File văn b n BAI1.INP:ả
Dòng 1: M t s nguyên d ng N (3 ộ ố ươ N 100).
Dòng 2: Ch a 2N s nguyên: xứ ố 1, y1, x2, y2,.., xN, yN theo th t đó, (|xứ ự i|, |yi| 100, 1 i N).
K t qu :ế ả File văn b n BAI1.OUT, ghi k t qu tìm đc sau khi làm tròn đn 3 ch s sau d uả ế ả ượ ế ữ ố ấ
ph y.ẩ
Ví d :ụ
BAI1.INP BAI1.OUT
4
0 0 0 1 1 1 1 0
1.000
Câu 2 (7 đi m): L c đ s h u t (file bài làm: bai2.pas)ể ượ ồ ố ữ ỉ
Cantor là nhà toán h c n i ti ng, m t trong nh ng ch ng minhọ ổ ế ộ ữ ứ
quan tr ng c a ông là vi c ch ra r ng l c l ng t p s h u t đúngọ ủ ệ ỉ ằ ự ượ ậ ố ữ ỉ
b ng l c l ng t p s t nhiên. C s c a ch ng minh đó là l cằ ự ượ ậ ố ự ơ ở ủ ứ ượ
đ s h u t nh hình bên. Trong l c đ này, s đu tiên là 1/1, sồ ố ữ ỉ ư ượ ồ ố ầ ố
th 2 là 1/2, s th 3 là 2/1, s th 4 là 3/1, s th 5 là 2/2…ứ ố ứ ố ứ ố ứ
Yêu c uầ: V i s nguyên d ng N, hãy tìm phân s th N trong l cớ ố ươ ố ứ ượ
đ s h u t nói trên.ồ ố ữ ỉ
D li u:ữ ệ File văn b n BAI2.INP ch a s nguyên d ng N (N ả ứ ố ươ 107).
K t qu :ế ả File văn b n ảBAI2.OUT, ghi hai s nguyên d ng là t s và m u s c a phân s tìmố ươ ử ố ẫ ố ủ ố
đc.ượ
Ví d :ụ
BAI2.INP BAI2.OUT BAI2.INP BAI2.OUT
4 3 1 8 2 3
Câu 3 (6 đi m): Dãy chia h t (file bài làm: baiể ế 3.pas)
Xét m t dãy s nguyên g m N ph n t . Vi t dãy s đó theo th t t trái sang ph i, sau đóộ ố ồ ầ ử ế ố ứ ự ừ ả
đt gi a m i c p s c nh nhau d u c ng 'ặ ữ ỗ ặ ố ạ ấ ộ +' ho c tr 'ặ ừ -', khi đó ta thu đc m t bi u th c s h c.ượ ộ ể ứ ố ọ
Ta nói dãy s là chia h t cho K n u t n t i m t cách đt d u đ thu đc bi u th c s h c chiaố ế ế ồ ạ ộ ặ ấ ể ượ ể ứ ố ọ
h t cho K. ế
Yêu c uầ: Hãy xác đnh dãy s đã cho có chia h t cho K hay không.ị ố ế
D li uữ ệ : File văn b n BAI3.INP:ả
Dòng đu là hai s nguyên N và K (2 ≤ N ≤ 10ầ ố 4, 2 ≤ K ≤ 100).
Các dòng ti p theo là dãy N s nguyên, m i s có giá tr tuy t đi không quá 10ế ố ỗ ố ị ệ ố 4.
K t quế ả: File văn b n BAI3.OUT, ghi s 0 ho c 1 t ng ng v i dãy không chia h t ho c chia h tả ố ặ ươ ứ ớ ế ặ ế
cho K.
Ví dụ:
BAI3.INP BAI3.OUT BAI3.INP BAI3.OUT
Đ THI CHÍNH TH CỀ Ứ
1/1 1/2 1/3 1/4 1/5...
2/1 2/2 2/3 2/4
3/1 3/2 3/3
4/1 4/2
5/1
...
4 7
1 2 3 5
1 4 6
1 2 3 5
0
Chú ý: - M i bài có 60% s test kích th c d li u nh .ỗ ố ướ ữ ệ ỏ
- Trong file d li u ho c k t qu , trên 1 dòng, hai giá tr c nh nhau cách nhau 1 d uữ ệ ặ ế ả ị ạ ấ
cách.
-----------------------------H t--------------------------ế
H và tên thí sinh :.....................................................................…………..S báo ọ ố
danh .............................
H và tên, ch ký: Giám th ọ ữ ị
1:.....................................................................................................................
Giám th ị
2:......................................................................................................................
H NG D N CH M THI CH N H C SINH GI I L P 12 THPT ƯỚ Ẫ Ấ Ọ Ọ Ỏ Ớ
K thi th hai - ỳ ứ Năm h c 2012 – 2013ọ
MÔN: TIN H CỌ
Ch m b ng ch ng trình t đng AMM2:ấ ằ ươ ự ộ
Câu 1: 70 test, m i test đúng cho 0,1 đi m.ỗ ể
Câu2: 70 test, m i test đúng cho 0,1 đi m.ỗ ể
Câu3: 60 test, m i test đúng cho 0,1 đi m.ỗ ể
Đáp án
Bài 1:
{$MODE ObjFPC}
const
iFn = 'bai1.inp';
oFn = 'bai1.out';
MAX_N = 100;
var
F: Text;
n: Integer;
x, y: array[0..MAX_N] of Integer;
i: Integer;
s: Real;
BEGIN
Assign(F, iFn); Reset(F);
ReadLn(F, n);
for i := 1 to n do
Read(F, x[i], y[i]);
Close(F);
x[0] := x[n]; y[0] := y[n];
for i := 1 to n do
s := s + (x[i-1]-x[i])*(y[i-1]+y[i]);
s := abs(s)/2;
Assign(F, oFn); Rewrite(F);
Write(F, s:0:3);
Close(F);
END.
Bài 2:
{$MODE ObjFPC}
const
iFn = 'bai2.inp';
oFn = 'bai2.out';
var
F: Text;
n: Integer;
d, a, b: Integer;
BEGIN
Assign(F, iFn); Reset(F);
ReadLn(F, n);
Close(F);
d := Trunc( (-1 + sqrt(1 + 8*n))/2 );
if d*(d+1) < 2*n then Inc(d);
a := n - (d-1)*d div 2;
b := d+1 - a;
Assign(F, oFn); Rewrite(F);
if Odd(d) then
Write(F, b, ' ', a)
else
Write(F, a, ' ', b);
Close(F);
END.
Bài 3:
{$MODE ObjFPC}
const
iFn = 'bai3.inp';
oFn = 'bai3.out';
MAX_N = 10000;
MAX_K = 100;
var
F: Text;
n, k: Integer;
a: array[1..MAX_N] of Integer;
t: array[0..1, 0..MAX_K-1] of Boolean;
i, i1, i2, j, z: Integer;
BEGIN
Assign(F, iFn); Reset(F);
ReadLn(F, n, k);
for i := 1 to n do
begin
Read(F, a[i]);
a[i] := (a[i] mod k + k) mod k;
end;
Close(F);
t[0, a[1]] := true;
for i := 2 to n do
begin
i1 := i and 1;
i2 := 1 - i2;
FillChar(t[i2], k, 0);
for j := k-1 downto 0 do
if t[i1, j] then
begin
t[i2, (j - a[i]+ k) mod k] := true;
t[i2, (j + a[i]) mod k] := true;
end;
end;
Assign(F, oFn); Rewrite(F);
Write(F, Ord(t[i2, 0]));
Close(F);
END.
--- H T ---Ế