Đề thi chọn học sinh giỏi vòng 2 tham dự kì thi học sinh giỏi quốc gia lớp 12 THPT năm 2015 môn Tin học - Sở GD&ĐT Ninh Bình (Có đáp án)

SỞ GD&ĐT NINH BÌNH
ĐỀ THI CHÍNH THỨC
ĐỀ THI CHỌN HSG VÒNG 2 THAM DỰ KÌ THI
HSG QUỐC GIA LỚP 12 THPT NĂM 2015
MÔN: TIN HỌC
Ngày thi 01/11/2014
Thời gian 180 phút không kể thời gian phát đề
(Đề thi gồm 04 câu, trong 03 trang)
Tổng quan đề thi:
Bài
Chương trình
Input
Output
Thời gian
1- Mua quà
BUYGIFTS.PAS
BUYGIFTS.INP
BUYGIFTS.OUT
1giây/test
2- Sơn hàng rào
PAINT.PAS
PAINT.INP
PAINT.OUT
1giây/test
3- CITY
CITY.PAS
CITY.INP
CITY.OUT
1giây/test
4- BUS
BUS.PAS
BUS.INP
BUS.OUT
1giây/test
Câu 1. Mua quà (6 điểm) 
Tý là một học sinh tham dự cuộc thi Olympic Tin học quốc tế năm 2014. Do lần đầu ra nước ngoài nên bạn ấy muốn mua các món quà lưu niệm tặng các bạn ở trường. Sau những buổi thi căng thẳng, ban tổ chức dẫn các thí sinh dự thi đi tham quan danh lam thắng cảnh và những cửa hàng lưu niệm của địa phương.
Sau khi đi lòng vòng Tý bước vào một cửa hàng lưu niệm bán những món quà mà bạn ấy yêu thích. Chủ cửa hàng giới thiệu cho Tý () món quà, món quà thứ () có giá (). 
Tý muốn chọn mua () món quà sao cho độ chênh lệch giữa giá món quà rẻ nhất và đắt nhất là tối thiểu. Vì đi chơi nên Tý không mang theo máy tính nên bạn hãy giúp bạn ấy tính xem có thể mua các món quà với độ chênh lệch nhỏ nhất.
 Dữ liệu vào: từ file văn bản BUYGIFTS.INP có cấu trúc như sau:
	- Dòng 1: ghi hai số nguyên dương n và m.
	- Dòng 2: ghi số nguyên lần lượt là .
	- Các số trên cùng một dòng cách nhau một dấu cách.
Kết quả: ghi ra file BUYGIFTS.OUT gồm một số nguyên dương là độ lệch tối thiểu.
Ví dụ:
BUYGIFTS.INP
BUYGIFTS.INP
Giải thích
6 4
10 12 10 5 7 22
5
Tý có thể mua các món quà có giá trị: 
10, 12, 10, 7.
Câu 2. Sơn hàng rào (6 điểm) 
Mr Bean muốn sơn lại hàng rào nhà mình. Hàng rào của anh ấy được ghép bởi n () tấm ván liên tiếp, mỗi tấm rộng 1 cm và có chiều cao khác nhau, tấm ván thứ () chiều cao là (). Mr Bean muốn sơn hàng rào nhà mình sao cho thật đặc biệt. Ban đầu anh ta tiến hành khảo sát hệ thống hàng rào, để tìm ra chiều cao của tấm ghép thấp nhất trong một đoạn liên tiếp các tấm ván từ tấm thứ i đến tấm thứ j (i£j). Có m (m£105) đoạn liên tiếp cần khảo sát lần lượt là: (i1, j1), (i2, j2), (i3, j3),  , (im, jm). 
Thông tin về các đoạn liên tiếp này thỏa mãn 2 điều kiện:
 (i1 £ i2 ££ im-1 £ im ) và (j1£ j2 £  £ jm-1 £ jm)
Dữ liệu vào: từ file văn bản PAINT.INP có cấu trúc như sau:	
	- Dòng 1: ghi hai số nguyên dương n và m.
	- Dòng 2: ghi n số nguyên dương lần lượt là .
	- m dòng tiếp theo, dòng thứ k ghi hai số ik, jk là thông tin về đoạn hàng rào thứ k mà Mr Bean cần khảo sát.
Dữ liệu ra: ghi ra file PAINT.OUT gồm m dòng, dòng thứ i là chiều cao của tấm ghép thấp nhất trong đoạn hàng rào khảo sát thứ i.
Ví dụ:
PAINT.INP
PAINT.OUT
5 5
3 6 8 2 1
1 3
2 3
3 4
3 5
4 5
3
6
2
1
1
Câu 3. CITY (5 điểm)
	Một vương quốc có n thành phố đánh số từ 1 đến n, có m tuyến đường hai chiều, mỗi tuyến đường nối một cặp thành phố và có độ dài xác định. Hai thành phố được nối với nhau bởi không quá một con đường. Công ty X có trụ sở đặt thành phố A và thành phố B. Để giảm chi phí cho việc vận chuyển hàng, Giám đốc công ty muốn xây dựng một trụ sở mới tại một thành phố khác A và B.
Yêu cầu: Hãy tìm danh sách các thành phố để công ty có thể đặt trụ sở tại đó, sao cho tổng khoảng cách từ thành phố này đến hai thành phố A và B là ngắn nhất có thể.
Dữ liệu vào: Ghi trong file văn bản CITY.INP có cấu trúc như sau:
- Dòng đầu tiên ghi 2 số nguyên dương n, m (2 £ n £ 104, 0 £ m £ 105).
- Dòng thứ 2 ghi 2 số A, B.
- m dòng tiếp theo mỗi dòng gồm 3 số u, v, c (1 £ u, v £ n, u khác v, 1 £ c £ 105), là thông tin về tuyến đường hai chiều nối giữa hai thành phố u và v với độ dài là c.
Dữ liệu ra: Ghi vào file văn bản CITY.OUT có cấu trúc như sau:
	- Dòng đầu tiên ghi một số nguyên K là số lượng các thành phố công ty Beta có thể đặt trụ sở tại đó.
	- K dòng tiếp theo ghi ra danh sách các thành phố tìm được. Số hiệu của các thành phố được ghi theo thứ tự tăng dần.
CITY.INP 
CITY.OUT 
5 7
1 5
1 2 2
1 3 1
1 4 2
2 3 1
2 4 3
2 5 3
4 5 4
2
2
3
Câu 4. BUS (3 điểm)
Hãng taxi BUS có n bến đỗ và có m taxi. Có 1 điều đặc biệt là mỗi taxi sẽ chỉ được đi trên 1 con đường hai chiều nối trực tiếp giữa 2 bến taxi, không có 2 taxi nào cùng hoạt động trên một tuyến đường.
Tí và Tèo nhận ra rằng vẫn có một số bến taxi không được “kết nối”, bến taxi A được “kết nối” với bến B nếu tồn tại một đường đi trực tiếp hoặc gián tiếp từ A đến B. Tí và Tèo đề xuất 2 sáng kiến để giải quyết vấn đề này:
- Một số taxi sẽ chuyển làn, chi phí chuyển làn của mỗi taxi là khác nhau.
- Mua thêm một số taxi mới, mỗi taxi mới có giá C, taxi này sẽ chạy trên một làn đường chưa được chọn bởi bất kỳ taxi nào khác.
Sau khi xem xét, Tí và Tèo quyết định tìm số tiền nhỏ nhất phải trả để cho tất cả các bến taxi được “kết nối” với nhau và số taxi mua mới càng ít càng tốt. Nhiệm vụ của bạn là giúp Tí và Tèo tìm số tiền nhỏ nhất phải chi, số lượng taxi mới cần phải mua và số lượng taxi phải chuyển làn.
Dữ liệu vào: Ghi trong file văn bản BUS.INP 
Dòng đầu tiên ghi 3 số n, m, C (2 £ n £ 104, 0 £ m £ 104, 1 £ C £ 105) lần lượt là số bến taxi, số xe taxi và chi phí để mua 1 taxi mới.
m dòng tiếp theo, dòng thứ i gồm 3 số u, v, r (1 £ a, b £ n, a khác b, 1 £ r £ 105) thể hiện xe taxi thứ i chạy trên tuyến đường từ u đến v sẽ cần r đơn vị tiền để chuyển làn.
Dữ liệu ra: Ghi ra file văn bản BUS.OUT có cấu trúc như sau:
Gồm 3 số lần lượt là số lượng taxi mới cần mua, số lượng taxi cũ phải chuyển làn và chi phí nhỏ nhất để thực hiện. (các số trên cùng một dòng cách nhau bởi dấu cách)
BUS.INP
BUS.OUT
Giải thích: 
- Mua thêm một xe mới.
- Xe hoạt động trên tuyến đường 1- 5 cần chuyển làn.
Tổng chi phí 
= 10 + 15 = 25
7 5 15
1 2 15
1 5 10
2 5 20
5 7 10
4 3 10
1 1 25
BUS.INP
BUS.OUT
Giải thích: 
- Mua thêm 2 xe mới.
- Không xe nào chuyển làn
Tổng chi phí 
= 15 x 2 = 30
25
7 5 15
1 2 25
1 5 30
2 5 20
5 7 10
4 3 10
2 0 30
50% số test có n, m <= 100.
------------- HẾT -------------
Chữ ký giám thị 1:	 Chữ ký giám thị 2: 
Họ và tên thí sinh :....................................................... Số báo danh .......................................
SỞ GD&ĐT NINH BÌNH
ĐỀ THI CHỌN HSG VÒNG 2 THAM DỰ KÌ THI
HSG QUỐC GIA LỚP 12 THPT NĂM 2015
MÔN: TIN HỌC
(hướng dẫn chấm gồm......trang)
Câu
Đáp án
Điểm
Câu 1. 
uses math;
const nmax = round(5e3)+3;
 oo = round(1e18);
var a: array[1..1000001] of longint;
 m,n: longint;
procedure openf;
var i,u,v,c:longint;
begin
 assign(input,'BUYGIFTS.INP'); Reset(input);
 assign(output,'BUYGIFTS.OUT'); Rewrite(output);
 read(n,m);
 for i:=1 to n do read(a[i]);
end;
{-------------}
procedure swap(i,j: longint);
var tg:longint;
begin
 tg:= a[i]; a[i]:= a[j]; a[j]:= tg;
end;
{------------}
procedure qs(l,r: longint);
var i,j,k: longint;
begin
 if l>= r then exit;
 i:= l; j:= r;
 k:= a[(l+r) div 2] ;
 repeat
 while a[i]< k do inc(i);
 while a[j]> k do dec(j);
 if i<=j then
 begin
 swap(i,j);
 inc(i);
 dec(j);
 end;
 until i> j;
 qs(l,j); qs(i,r);
end;
{-----------}
procedure xuly;
var i, res:longint;
begin
 qs(1,n);
 res:= MAXLONGINT;
 for i:=1 to n-m+1 do
 begin
 if res> (a[i+m-1]- a[i]) then res:= a[i+m-1]- a[i];
 end;
 write(res);
end;
{-----------}
BEGIN
 OPENF;
 XULY;
 CLOSE(INPUT);
 CLOSE(OUTPUT);
END.
6.0 điểm
Câu 2.
 program PAINT;
 const fi='PAINT.INP';
 fo='PAINT.OUT';
 type point=record
 x,y:longint;
 end;
 var a,q:array[0..100001] of longint;
 f:array[1..100001] of point;
 n,m,first,last:longint;
 //
 procedure nhap;
 var i,j:longint;
 begin
 assign(input,fi);reset(input);
 readln(n,m);
 for i:=1 to n do read(a[i]);
 readln;
 for j:=1 to m do readln(f[j].x,f[j].y);
 close(input);
 end;
 //
 procedure push(x:longint);
 begin
 inc(last);
 q[last]:=x;
 if last=1 then first:=1;
 end;
 //
 procedure xuly;
 var i,d:longint;
 begin
 assign(output,fo);rewrite(output);
 first:=1;
 last:=-1;
 d:=0;
 a[0]:=-1;
 push(0);
 for i := 1 to m do
 begin
 while d<f[i].y do
 begin
 inc(d);
 if a[d]>=a[q[last]] then push(d)
 else
 begin
 while (first<=last) and (a[d]<a[q[last]]) do dec(last);
 push(d);
 end;
 end;
 while q[first]<f[i].x do inc(first);
 writeln(a[q[first]]);
 end;
 close(output);
 end;
 //
 BEGIN
 nhap;
 xuly;
 END.
6.0 điểm
Câu 3.
Program city;
Const
 InputFile = 'CITY.INP';
 OutputFile = 'CITY.OUT';
 maxn=5001;
 maxm=100001;
 vc=maxlongint;
type
 arrN=array[0..maxn] of longint;
var
 n, m: longint;
 a,b: longint;
 cost: array[1..maxn] of longint;
 d, c, r: array[1..maxm] of longint;
 tro: array[1..maxn] of longint;
 ke, ts: array[1..2*maxm] of longint;
 color: arrN;
 qn: longint;
 q, vt: arrN;
 kc1, kc2: arrN;
 ds: longint;
 Kq: array[1..10000] of longint;
 sl: longint;
procedure Up(var kc: arrN; k: longint);
var v: longint;
begin
 v:=q[k];
 while kc[q[k div 2]]>kc[v] do
 begin
 q[k]:=q[k div 2];
 vt[q[k]]:=k;
 k:=k div 2;
 end;
 q[k]:=v;
 vt[v]:=k;
end;
procedure down(var kc: arrN; k: longint);
var v, l: longint;
begin
 v:=q[k];
 while 2*k<=qn do
 begin
 l:=2*k;
 if (l<qn) and (kc[q[l+1]]<kc[q[l]]) then inc(l);
 if kc[q[l]]>=kc[v] then break;
 q[k]:=q[l];
 vt[q[k]]:=k;
 k:=l;
 end;
 q[k]:=v;
 vt[v]:=k;
end;
procedure initq(var kc: arrN);
begin
 qn:=0;
 vt[0]:=0;
 kc[0]:=-1;
end;
procedure put(var kc: arrN; u: longint);
begin
 inc(qn);
 q[qn]:=u;
 vt[u]:=qn;
 Up(kc,qn);
end;
function Get(var kc: arrN): longint;
begin
 Get:=q[1];
 q[1]:=q[qn];
 vt[q[1]]:=1;
 dec(qn);
 down(kc,1);
end;
function qempty: boolean;
begin
 exit(qn=0);
end;
Procedure Dijstra(xp: longint; var kc: arrN);
var u, i, v: longint;
begin
 fillchar(color,sizeof(color),0);
 initq(kc);
 put(kc,xp); color[xp]:=1; kc[xp]:=0;
 repeat
 u:=get(kc); color[u]:=2;
 for i:=tro[u] to tro[u+1]-1 do
 begin
 v:=ke[i];
 case color[v] of
 0: begin
 kc[v]:=kc[u]+Ts[i];
 put(kc,v);
 color[v]:=1;
 end;
 1: if kc[v]>kc[u]+Ts[i] then
 begin
 kc[v]:=kc[u]+Ts[i];
 Up(kc,Vt[v]);
 end;
 end;
 end;
 until qempty;
end;
Procedure Doc;
var k, i, u, L, v: longint;
begin
 read(n,m);
 read(a,b);
 for i:=1 to m do read(d[i],c[i],r[i]);
 // Init Graph
 for i:=1 to m do
 begin
 inc(tro[d[i]]);
 inc(tro[c[i]]);
 end;
 v:=0;
 for i:=1 to n do
 begin
 u:=tro[i];
 tro[i]:=v+1;
 v:=v+u;
 end;
 tro[n+1]:=v+1;
 for i:=1 to m do
 begin
 u:=d[i];
 v:=c[i];
 ke[tro[u]]:=v; Ts[tro[u]]:=r[i];
 ke[tro[v]]:=u; Ts[tro[v]]:=r[i];
 inc(tro[u]);
 inc(tro[v]);
 end;
 for i:=n downto 2 do tro[i]:=tro[i-1];
 tro[1]:=1;
end;
procedure process;
var i: longint; min:longint;
begin
 sl:=0;
 min:=maxlongint;
 for i:=1 to n do
 if (ia)and(ib) then
 begin
 if kc1[i]+ kc2[i] = min then
 begin
 inc(sl); kq[sl]:=i;
 end;
 if kc1[i] + kc2[i] < min then
 begin
 min:= kc1[i]+kc2[i];
 sl:=1;
 kq[sl]:= i;
 end;
 end;
end;
Procedure Main;
var i:longint ;
Begin
 assign(Input,InputFile); reset(Input);
 assign(Output,OutputFile); rewrite(Output);
 Doc;
 Dijstra(a,kc1);
 Dijstra(b,kc2);
 process;
 writeln(sl);
 for i:=1 to sl do
 writeln(kq[i]);
 close(Input); Close(Output);
End;
BEGIN
 Main;
END.
6.0 điểm
Câu 4.
const fi = 'BUS.INP';
 fo = 'BUS.OUT';
type diem= record
 u,v,c: longint;
 end;
var p: array [1..100000] of longint;
 mua,chuyen,kq:longint;
 n,m,cc: longint;
 ds: array [1..100000] of diem;
 sl:longint;dem:longint;
 thua:array[1..100000] of longint;
procedure doc;
var i: longint;
begin
 assign(input,fi); reset(input);
 read(n,m,cc);
 for i:=1 to m do
 read (ds[i].u, ds[i].v,ds[i].c);
 close(input);
end;
{--------------}
procedure swap(var a,b:diem);
var tg:diem;
begin
 tg:=a; a:=b; b:=tg;
end;
{---------------}
procedure qs(l,r:longint);
var i,j,key: longint;
begin
 if l>=r then exit;
 key:= ds[(l+r) div 2].c;
 i:=l; j:=r;
 repeat
 while ds[i].c< key do inc(i);
 while ds[j].c> key do dec(j);
 if i<=j then
 begin
 swap(ds[i],ds[j]);
 inc(i); dec(j);
 end;
 until i>j;
 qs(l,j); qs(i,r);
end;
{--------------------------------}
procedure init;
var i:longint;
begin
 for i:=1 to n do p[i]:= -1;
end;
{------------------------------}
function findset(i:longint):longint;
begin
 if p[i]< 0 then findset:= i
 else
 begin
 p[i]:= findset(p[i]);
 findset:= p[i];
 end;
end;
{------------------------------}
procedure union(i,j:longint);
var u,v:longint;
begin
 u:= findset(i);
 v:= findset(j);
 if u=v then exit;
 if (p[u]<p[v]) then
 begin
 p[u]:= p[u]+p[v];
 p[v]:= u;
 end
 else
 begin
 p[v]:= p[v]+ p[u];
 p[u]:= v;
 end;
end;
{--------------------------------}
procedure xuly;
var i:longint; u,v,c:longint;
begin
 dem:=0; sl:=0;
 for i:= m downto 1 do
 begin
 u:= ds[i].u;
 v:= ds[i].v;
 c:= ds[i].c;
 if findset(u) findset(v) then
 begin
 inc(dem);
 union(u,v);
 end
 else
 begin
 inc(sl);
 thua[sl]:= c;
 end;
 end;
 mua:= 0;
 chuyen:= 0;
 kq:= 0;
 if dem = n-1 then exit;
 for i:= sl downto 1 do
 begin
 if (dem = n-1) or (thua[i]>cC) then break;
 kq:= kq+thua[i];
 inc(chuyen);
 inc(dem);
 end;
 if dem= n-1 then exit;
 mua:= n-1 -dem;
 kq:= kq+ mua*cc;
end;
{-----------------}
procedure inkq;
begin
 assign(output,fo);
 rewrite(output);
 write(mua,' ',chuyen,' ',kq);
 close(output);
end;
{--------------}
begin
 randomize;
 doc;
 init;
 qs(1,m);
 xuly;
 inkq;
end.
6.0 điểm
-----------Hết-----------