Đề khảo sát đội tuyển HSG Tin 11 – Nam Đàn – Nghệ An 1819
Đề khảo sát đội tuyển HSG Tin 11 – Nam Đàn – Nghệ An 1819
Môn thi: TIN HỌC – THPT BẢNG A
Thời gian: 150 phút (không kể thời gian giao đề)
| Bài | Tên file nguồn | File Input | File Outout | Thời gian chạy | Điểm |
| Bài 1 | BANGNHAC.PAS | BANGNHAC.INP | BANGNHAC.OUT | 1 giây | 6 |
| Bài 2 | DIV.PAS | DIV.INP | DIV.OUT | 1 giây | 6 |
| Bài 3 | SEQ.PAS | SEQ.INP | SEQ.OUT | 1 giây | 4 |
| Baì 4 | GN.PAS | GN.INP | GN.OUT | 1 giây | 4 |
Bài 1( 6 điểm) BĂNG NHẠC
Một máy phát nhạc tự động có một băng nhạc đủ lớn để ghi n bài hát ,thời gian phát mỗi bài hát tính theo phút và được biết trước .Biết rằng , để phát bài hát thứ i thì máy phải trở về vị trí đầu băng và phải quay để bỏ i-1 bài trước đó .Máy có thể trở về vị trí đầu băng với thời gian không đáng kể và thời gian quay băng để bỏ qua mỗi bài và thời gian phát bài đó là bằng nhau.
Hãy tìm cách ghi các bài hát đó trên băng nhạc sao cho tổng số thời gian quay băng trong ngày là nhỏ nhất .Biết rằng mỗi bài hát được phát một lần .
Chẳng hạn :Băng nhạc có 3 bài hát có thứ tự là 1, 2, 3 với thời gian phát mỗi bài lần lượt là 3,2 và 6 phút . Nếu ta ghi băng nhạc theo thứ tự khác nhau thì tổng thời gian phát cả băng nhạc là khác nhau , cụ thể là :
| Thứ tự bài hát | Thời gian phát mỗi bài | Tổng thời gian phát |
| 1 2 3
2 3 1 |
3 2 6
2 6 3 |
3+(3+2)+(3+2+6)=19
2+(2+6)+(2+6+3)=21 |
Dữ liệu vào :
Đọc từ tệp văn bản BANGNHAC.INP có cấu trúc như sau:
-Dòng thứ nhất chứa số n (n≤ 100)
– Các dòng tiếp theo chứa các số nguyên t1,t2,…,tn lần lượt là thời gian phát các bài hát 1,2,…,n . các số cách nhau ít nhất một dấu cách .
Dữ liệu ra :
Ghi vào tệp BANGNHAC.OUT có cấu trúc như sau:
-Dòng thứ nhất ghi số Tmin là tổng thời gian tìm và phát cả băng nhạc
– Các dòng tiếp theo chứa n số là thứ tự các bài hát ghi trên băng nhạc ,các số cách nhau ít nhất một dấu cách.
Ví dụ BANGNHAC.INP BANGNHAC.OUT
3 18
3 2 6 2 1 3
Bài 2. Trò chơi với băng số (6 điểm) File bài làm DIV.PAS
Cho một băng số gồm n số nguyên dương, mỗi số được viết trên một ô. Hãy cắt băng số này thành nhiều đoạn nhất sao cho tổng các phần tử trong các đoạn là bằng nhau.
Dữ liệu vào: DIV.INP + Dòng đầu ghi n (n ≤ 1000)
+ Dòng tiếp theo ghi n số nguyên dương a1, a2, …, an
(các số nằm trên một dòng cách nhau bởi một dấu cách ai ≤ 1000)
Dữ liệu ra: DIV.OUT Ghi K là số đoạn cần chia.
Ví dụ:
| DIV.INP | DIV.OUT | Giải thích |
| 8
10 2 6 2 5 2 1 2 |
3
|
Đoạn 1: 10
Đoạn 2: 2 + 6 + 2 =10 Đoạn 3: 5 + 2 + 1 + 2 = 10 |
Bài 3 (4.0 điểm): SEQ
Cho dãy số gồm n số nguyên a1, a2, …, an và 2 số nguyên không âm L, R (L ≤ R).
Yêu cầu: Đếm số cặp (i, j) thỏa mãn điều kiện: i ≤ j và L ≤ |ai+…+aj| ≤ R .
Dữ liệu vào: Từ file văn bản SEQ.INP gồm:
– Dòng đầu tiên chứa 3 số nguyên n, L, R (n ≤ 105 ; 0 ≤ L ≤ R ≤ 109)
– Dòng thứ hai chứa n số nguyên dương a1, a2,…, an (ai ≤ 109)
Kết quả: Ghi ra file văn bản SEQ.OUT gồm một số nguyên duy nhất là số lượng cặp (i, j) đếm được.
Ví dụ:
| SEQ.INP | SEQ.OUT |
| 3 0 1
1 -1 2 |
4 |
Hạn chế: – Có 50% số test ứng với 0 < n ≤ 103
– Có 50% số test ứng với 103 < n ≤ 105
Bài 4 (4.0 điểm): GN
Người ta đo độ giống nhau của hai xâu X, Y có độ dài bằng nhau là số vị trí mà hai kí tự tương ứng trên hai xâu giống nhau, tức là số chỉ số i thỏa mãn X[i] = Y[i] .
Ví dụ: X = ‘avbc’; Y = ‘avvv’ có độ giống nhau bằng 2.
Cho một xâu S có độ dài n và một xâu T có độ dài m (m n), độ giống nhau giữa xâu S và xâu T là tổng số độ giống nhau giữa xâu T và mọi xâu con gồm các kí tự liên tiếp của S có độ dài m.
Yêu cầu: Cho hai xâu S và T. Tính độ giống nhau giữa xâu S và xâu T.
Dữ liệu vào: Từ file văn bản GN.INP như sau:
– Dòng đầu ghi xâu T.
– Dòng thứ 2 ghi xâu S.
Các kí tự trong hai xâu thuộc ‘a’ .. ‘z’ và có độ dài không quá 2.106 kí tự.
Kết quả: Ghi ra file văn bản GN.OUT gồm một số nguyên duy nhất là độ giống nhau giữa xâu S và xâu T.
Ví dụ:
| GN.INP | GN.OUT |
| abaab
aababacab |
12 |
Hạn chế: – Có 25% số test ứng với 0 < n ≤ 102
– Có 25% số test ứng với 102 < n ≤ 104
– Có 50% số test ứng với 104 < n ≤ 2.106
Code tham khảo Đề khảo sát đội tuyển HSG Tin 11 – Nam Đàn – Nghệ An 1819
Bài 1
Const inp='bangnhac.inp';
Out='bangnhac.out';
Var t:array[1..100]
of integer;
B :array[1..100]
of integer;
Fi,fo:text;
N,Tmin: integer;
Procedure Openfile;
Begin
Assign(fi,inp); reset(fi);
Assign(fo,out);rewite(fo);
End;
Procedure Readfile;
Var i,j: integer;
Begin
Readln(fi,n);
For i:=1 to n do read(fi,t[i]
);
For i:=1 to n do b[i]
:=i;
End;
Procedure process;
Var i,j,tg: integer;
Begin
For i:=1 to n-1 do
For j:=i+1 to n do
If t[i] >t[j]
then
Begin
Tg:=t[i] ; t[i] :=t[j] ; t[j]
:=tg;
Tg:=b[i] ; b[i] :=b[j] ; b[j]
:=tg;
End;
End;
Procedure Writefile;
Var
I, j:integer;
Begin
Tmin:=0;
J:=1;
Repeat
For i:=1 to j do Tmin :=Tmin+t[i]
;
J:=j+1;
Until j>n
Writeln (fo,Tmin);
For i:=1 to n do write (fo,b[i]
,' ');
End;
Procedure Closefile;
Begin
Close(fi);
Close(fo);
End;
BEGIN
Openfile;
Readfile;
Process;
Writefile;
Closefile;
END.
Bài 2:
const
tfi='DIV.INP';
tfo='DIV.OUT';
var n: longint;
a, s: array[0..1001]
of longint;
res: longint;
function ok(t: longint): boolean;
var i,u,tong: longint;
begin
tong:=0;
for i:=1 to n do if a[i]
<>0 then
begin
tong:=tong+a[i]
;
if tong=t then tong:=0;
end;
exit(tong=0);
end;
procedure main;
var j,u,i,k,t: longint;
begin
assign(input,tfi); reset(input);
assign(output,tfo); rewrite(output);
read(n);
for i:=1 to n do read(a[i]
);
s[0]
:=0;
for i:=1 to n do s[i] :=s[i-1] +a[i]
;
for k:=n downto 1 do if s[n]
mod k=0 then
begin
t:=s[n]
div k;
if ok(t) then
begin
res:=k;
break;
end;
end;
writeln(res);
close(input); close(output);
end;
BEGIN
main;
END.
Bài 3:
const finp='GN.INP';
fout='GN.OUT';
maxn=2*trunc(1e6)+14;
var fi,fo:text;
n,m:longint;
kq:int64;
s,t:ansistring;
pos:array[0..maxn,'a'..'z']
of int64;
procedure mo;
begin
assign(fi,finp);
reset(fi);
assign(fo,fout);
rewrite(fo);
end;
procedure dong;
begin
close(fi);
close(fo);
end;
procedure doc;
begin
readln(fi,s);
read(fi,t);
n:=length(s);m:=length(t);
end;
procedure init;
var i:Longint;
j:char;
begin
for i:=1 to m do
begin
for j:='a' to 'z' do pos[i,j] :=pos[i-1,j]
;
pos[i,t[i] ]:=pos[i-1,t[i]
]+1;
end;
end;
procedure solve;
var i,dau,cuoi:longint;
begin
cuoi:=m-n+1;dau:=0;
for i:=1 to n do
begin
kq:=kq+pos[cuoi,s[i] ]-pos[dau,s[i]
];
inc(cuoi);inc(dau);
end;
writeln(fo,kq);
end;
begin
mo;
doc;
init;
solve;
dong;
end.
Bài 4
uses math;
const fi='seq.inp';
fo='seq.out';
MAXN=100007;
var n,d,c:longint;
l,r:int64;
a:array[0..MAXN]
of int64;
res:int64;
procedure mf;
begin
assign(input,fi);reset(input);
assign(output,fo);rewrite(output);
end;
procedure df;
begin
close(input);
close(output);
end;
procedure nhap;
var i:longint;
begin
readln(n,l,r);
for i:=1 to n do
begin
read(a[i]
);
a[i] :=a[i] +a[i-1]
;
end;
end;
procedure swap(var a,b:int64);
var tg:int64;
begin
tg:=a;a:=b;b:=tg;
end;
procedure sort(l,r:longint);
var i,j:longint;
x:int64;
begin
i:=l;j:=r;x:=a[l+random(r-l+1)]
;
repeat
while a[i]
<x do inc(i);
while a[j]
>x do dec(j);
if i<=j then
begin
swap(a[i] ,a[j]
);
inc(i);dec(j);
end;
until i>j;
if i<r then sort(i,r);
if l<j then sort(l,j);
end;
procedure xl;
var i:longint;
begin
sort(0,n);
for i:=0 to n-1 do
begin
d:=max(d,i+1);
c:=max(d,c);
while (d<n) and (a[d] -a[i]
<l) do inc(d);
while (c<n) and (a[c+1] -a[i]
<=r) do inc(c);
if d<=c then res:=res+c-d+1;
end;
writeln(res);
end;
begin
mf;
nhap;
xl;
df;
end.
