S GD&ĐT NINH BÌNHỞĐ THI CH N H C SINH GI I L P 12 THPTỀ Ọ Ọ Ỏ Ớ
K thi th nh t - ỳ ứ ấ Năm h c 2012 – 2013ọ
MÔN: TIN H CỌ
Ngày thi: 09/10/2012
(Th i gian làm bài:180 phút )ờ
Đ thi g m 04 câu, trong 02 trangề ồ
T ng quan đ thi:ổ ề
Câu Tên file bài làm Tên file Input Tên file Otput Th i gian ch yờ ạ
1 NUMBER.PAS NUMBER.INP NUMBER.OUT 1 giây/test
2GOMBI.PAS GOMBI.INP GOMBI.OUT 1 giây/test
3 TRIANGLE.PAS TRIANGLE.INP TRIANGLE.OUT 2 giây/test
4 PASCAL.PAS PASCAL.INP PASCAL.OUT 1 giây/test
Ghi chú: Thí sinh ph i đt tên file bài làm, file Input, file Output theo quy đnh nh trên.ả ặ ị ư
Câu 1: Ch s th N.ữ ố ứ
Khi vi t các s t nhiên tăng d n t 1, 2, 3,… liên ti p nhau, ta nh n đc m t dãy các ch sế ố ự ầ ừ ế ậ ượ ộ ữ ố
th p phân vô h n, đo n đu tiên c a dãy s là: 1234567891011121314151617181920...ậ ạ ạ ầ ủ ẽ
Yêu c uầ: Hãy tìm ch s th N c a dãy s vô h n trên.ữ ố ứ ủ ố ạ
D li u:ữ ệ Cho trong file NUMBER.INP g m m t nguyên d ng N (N < 10ồ ộ ươ 6).
K t qu :ế ả Ghi k t qu ra file NUMBER.OUT.ế ả
Ví d : ụ
NUMBER.OUT NUMBER.OUT Gi i thích k t quả ế ả
21 5 Ch s th 21 trong dãy là ch s 5ữ ố ứ ữ ố
Câu 2: Gom bi.
Có N cái h p đánh s t 1 t i N và N viên bi cũng đánh s t 1 t i N. Ban đu bi s i đt trongộ ố ừ ớ ố ừ ớ ầ ố ặ
h p đánh s i (i = 1..N). V i m t c p s nguyên (u, v) cho tr c, b n ph i th c hi n thao tácộ ố ớ ộ ặ ố ướ ạ ả ự ệ
chuy n t t c các bi cùng h p v i bi có s u vào h p ch a bi s v.ể ấ ả ộ ớ ố ộ ứ ố
Yêu c u:ầ Cho s N và danh sách M thao tác c n ph i th c hi n. Hãy xác đnh s l ng bi l n nh tố ầ ả ự ệ ị ố ượ ớ ấ
trong m t h p sau khi đã th c hi n đ M thao tác chuy n bi.ộ ộ ự ệ ủ ể
D li u:ữ ệ Cho trong file GOMBI.INP
Dòng 1 là hai s N, M (2 ≤ N ≤ 500; 1 ≤ M ≤ 1000).ố
M dòng ti p theo, m i dòng ch a hai s nguyên u v th hi n m t thao tác c n th c hi nế ỗ ứ ố ể ệ ộ ầ ự ệ
K t qu :ế ả Ghi ra file GOMBI.OUT m t s nguyên là s l ng bi trong h p có nhi u bi nh t sau khiộ ố ố ượ ộ ề ấ
th c hi n các thao tác.ự ệ
Ví d :ụ
GOMBI.INP GOMBI.OUT Gi i thích: Các h p có bi sau m i l nả ộ ỗ ầ
chuy n.ể
7 4
1 3
2 6
1 6
1 2
4 Ban đu: (1) (2) (3) (4) (5) (6) (7)ầ
Chuy n 1 3: (2) (1 3) (4) (5) (6) (7)ể
Chuy n 2 6: (1 3) (4) (5) (2 6) (7)ể
Chuy n 1 6: (4) (5) (1 2 3 6) (7)ể
Chuy n 1 2: (4) (5) (1 2 3 6) (7)ể
Câu 3: Tam giác cân.
Cho h tr c t a đ Oxy, trên đó có đánh d u ệ ụ ọ ộ ấ n đi m (3 ≤ ển ≤ 1500). Đi m th i có t a đ (ể ứ ọ ộ xi,
yi) (i = 1 ÷ n), các t a đ là s nguyên có giá tr tuy t đi không v t quá 10ọ ộ ố ị ệ ố ượ 9.
Đ THI CHÍNH TH CỀ Ứ
Yêu c uầ: Xác đnh s tam giác cân có ba đnh là ba đi m trong s n đi m đã cho.ị ố ỉ ể ố ể
D li uữ ệ : Cho trong file TRIANGLE.INP:
Dòng đu tiên ch a s nguyên ầ ứ ố n.
Dòng th ứi trong n dòng sau ch a 2 s nguyên ứ ố xi và yi.
K t quế ả: Ghi ra file TRIANGLE.OUT s tam giác cân tìm đc.ố ượ
Ví dụ:
TRIANGLE.INP TRIANGLE.OUT
4
0 0
1 1
1 0
0 1
4
Chú ý: Trong 60% s test có n < 200.ố
Câu 3(6 đi m): Tam giác PASCAL. ể
Tam giác Pascal là m t cách s p x p các h s khi khai tri n nh th c Newton vào m t hình cóộ ắ ế ệ ố ể ị ứ ộ
d ng tam giác theo t ng hàng, các hàng đc đánh s b t đu t 0, hàng th n (n ≥ 0) c a tam giácạ ừ ượ ố ắ ầ ừ ứ ủ
bao g m các h s trong khai tri n c a (x + y)ồ ệ ố ể ủ n vi t l n l t t trái sang ph i.ế ầ ượ ừ ả
Dòng 0: (x + y)0 = 1
Dòng 1: (x + y)1 = 1.x + 1.y
Dòng 2: (x + y)2 = 1.x2 + 2.xy + 1.y2
Dòng 3: (x + y)3 = 1.x3 + 3.x2y + 3.xy2 + 1.y3
…
D i đây các hàng t 0 đn 16 c a Tam giác Pascal:ướ ừ ế ủ
Yêu c u:ầ Cho s t nhiên n. Hãy tính ố ự s l ng s h ng là s lố ượ ố ạ ố ẻ trên dòng th n ức a tam giácủ
Pascal.
D li u:ữ ệ Cho trong file PASCAL.INP c u trúc nh sau: dòng đu là s nguyên k < 10 là s l ngấ ư ầ ố ố ượ
s n, k dòng ti p theo m i dòng ghi m t s n (1< n < 2.10ố ế ỗ ộ ố 9)
K t qu :ế ả Ghi ra file PASCAL.OUT k dòng, m i dòng m t s nguyên là k t qu bài toán t ng ngỗ ộ ố ế ả ươ ứ
v i m t s n trong file d li u theo đúng th t .ớ ộ ố ữ ệ ứ ự
Ví d :ụ
PASCAL.INP PASCAL.OUT
3
3
8
11
4
2
8
Chú ý: Trong 40 % s test có n < 30; trong 70% s test có n < 5000.ố ố
-----------------------------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 nh t - ỳ ứ ấ 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: 10 test, m i test đúng cho 0,5 đi m.ỗ ể
Câu2: 10 test, m i test đúng cho 0,5 đi m.ỗ ể
Câu3: 10 test đu, m i test đúng cho 0,3 đi m. 10 test sau, m i test đúng cho 0,2 đi m.ầ ỗ ể ỗ ể
Câu 4: 10 test, m i test đúng cho 0,5 đi m.ỗ ể
Bài 1:
Const fi ='number.inp';
fo ='number.out';
cs:array[1..8] of longint = (9, 180, 2700, 36000, 450000, 5400000, 63000000, 720000000);
Var n : longint;
f,g :text;
Function num(n:longint):char;
var k, so, mu : longint;
s : string;
Begin
k:=1; mu:=1;
while (k<9)and(cs[k]<n) do
begin
n:=n-cs[k];
inc(k); mu:=mu*10;
end;
if mu=1 then so:=n div k
else so:=n div k+mu+ord(n mod k>0)-1;
str(so,s);s:=s[k]+s;
num:=s[n mod k+1];
End;
BEGIN
assign(f,fi); reset(f);
assign(g,fo); rewrite(g);
while not seekeof(f) do
begin
readln(f,n);
writeln(g,num(n));
end;
close(f);
close(g);
END.
Bài 2:
const fi = 'Gombi.Inp';
fo = 'Gombi.Out';
nmax =10000;
var cha,u,v:array[1..nmax]of longint;
n,m:longint;
procedure nhap;
var f:text;
i:longint;
begin
assign(f,fi);
reset(f);
readln(f,n,m);
for i:=1 to m do
readln(f,u[i],v[i]);
close(f);
for i:=1 to n do cha[i]:=-1;
end;
procedure Join(u,v:longint);
begin
While cha[u]>0 do u:=cha[u];
While cha[v]>0 do v:=cha[v];
if u = v then exit;
if cha[u]<cha[v] then
begin
cha[u]:=cha[u]+cha[v];
cha[v]:=u;
end
else
begin
cha[v]:=cha[v]+cha[u];
cha[u]:=v;
end;
end;
procedure xuly;
var i,j,max:longint;
f:text;
begin
for i:=1 to m do Join(u[i],v[i]);
max:=0;
for i:=1 to n do if cha[i]<max then max:=cha[i];
assign(f,fo);
rewrite(f);
write(f,-max);
close(f);
end;
begin
nhap;
xuly;
end.
Bài 3:
const fi='Triangle.inp';
fo='Triangle.out';
max=1500;
type td=record
x,y:int64;
end;
mang=array[1..max+1] of extended;
var f,g:text;
a:array[1..max+1] of td;
kc:mang;