Bài tập bồi dưỡng học sinh giỏi tin 9
const fi='tronmang.inp';fo='tronmang.out'; var
n, m, i, j, a, b,d: longint; ma,mb,mc:array[1..500000] of longint; begin assign(input,fi);reset(input); assign(output,fo);rewrite(output); readln(n,m); for i:=1 to n do readln(ma[i]); for i:=1 to m do readln(mb[i]); i:=1;a:=ma[1]; j:=1;b:=mb[1];d:=0; while (i<=n)> if (a<=b)> begin inc(d);mc[d]:=a; inc(i); if (i<=n)> else a:=maxlongint; end
else begin
inc(d);mc[d]:=b; inc(j);
if (j<=m)>else b:=maxlongint; end; end;
for i:=1 to d do writeln(mc[i]); end.
Em được cho trước số nguyên dương n, hai số nguyên dương a, m. Hãy xác định dãy w1, w2, …, wn theo công thức: wi = ai mod m + 1 Tính tổng của dãy số này. Input: 3 số n, a, m Output: tổng dãy số Giải thích: dãy số tạo được là: 5, 8, 2, 5, 8. const fin = 'taomang.inp'; fon = ' taomang.out'; var
n, t, a, m,ai,s,max:int64; i,j:longint; k,im,jm,km:int64; w:array[1..1000000] of longint; fi,fo:text;
begin
ai:=a; for i:=1 to n do begin w[i]:=ai mod m +1; ai:=(ai mod m)*(a mod m); end;
begin assign(fi,fin);reset(fi); assign(fo,fon);rewrite(fo); read(fi,n, a, m); taomang; for i:=1 to n do s:=s+w[i]; writeln(fo,s); close(fi);close(fo); end. Yêu cầu: Tính số lớn nhất các hình vuông đồng nhất bậc 2 chứa cùng một số. Dữ liệu:
Kết quả: số lượng hình vuông tìm được. Ví dụ: 0 1 1 0 2 2 0 5 5 0 0 1 1 0 2 2 0 5 5 0 0 0 0 1 1 0 0 0 0 0 0 8 0 1 1 1 1 0 9 0 0 0 0 0 0 1 1 0 0 0 3 Chương trìnhconst fin='countsq.inp'; fon = 'countsq.out'; maxmn=1000; var
m,n:longint; a:array[1..maxmn,1..maxmn] of longint; dem:array[0..255] of longint;
var i,j:longint; begin readln(m, n); for i:=1 to m do for j:=1 to n do read(a[i,j]); end;
var i,j,imax:longint; begin for i:=1 to m-1 do for j:=1 to n-1 do if (a[i,j]=a[i,j+1]) and (a[i,j]=a[i+1,j]) and (a[i,j]=a[i+1,j+1]) then inc(dem[a[i,j]]); Imax:=0;
for i:=0 to 255 do if dem[i]>dem[imax] then imax:=i; //writeln(imax,' ',dem[imax]); writeln(dem[imax]); end;
assign(input,fin);reset(input); assign(output,fon);rewrite(output); enter;
solve; close(input);close(output); end.
(())
()() (((())
))(( (()))(()
YES YES
NO NO NO Xét xâu S chỉ bao gồm các kí tự ngoặc mở ‘(‘ và ngoặc đóng ‘)’. Xâu S xác định một cách đặt ngoặc đúng, nếu thỏa mãn các điều kiện:
Yêu cầu: cho biết một xâu s có là một cách đặt ngoặc đúng không? Input
Output: t dòng, mỗi dòng là kết quả 1 test tương ứng, xuất “YES” nếu cách đặt ngoặc đúng, ngược lại xuất “NO” Const fi='ngoac.inp';Fo='ngoac.out'; var n,i:longint; s:string;
var dong,mo,i:longint; begin dong:=0;mo:=0; for i:=1 to length(s) do begin
if s[i]=')' then inc(dong) else inc(mo); if dong>mo then exit(false); end;
if dong=mo then exit(true) else exit(false); end; BEGIN
assign(input,fi);reset(input); Assign(output,fo);rewrite(output); Readln(n); for i:=1 to n do begin readln(s); if solve(s) then writeln('YES') else writeln('NO'); end;
END.
Bài 20.Giải nén xâu GNENĐề thi tin học trẻ bảng C tỉnh Quảng Bình năm 2009 Trong máy tính, để tiết kiệm bộ nhớ, người ta thường tìm cách nén dữ liệu. Trong việc nén văn bản, ta sử dụng một phương pháp đơn giản được mô tả thông qua ví dụ sau: Ví dụ:
Cho một xâu ký tự St1 gồm các ký tự thuộc tập 'a'..'z'. Gọi St là xâu nén của xâu St1 theo phương phápđược mô tả như trên. Xâu St gồm N (1 N 255) ký tự thuộc tập các ký tự: 'a'..'z', '0'..'9' Yêu cầu: Hãy giải nén xâu St để được xâu gốc St1. Dữ liệu vào: xâu ký tự St. Dữ liệu ra: Ghi xâu St1 là xâu sau khi đã được giải nén. Ví dụ:
const fi='gnenxau.in1'; fo='gnenxau.ou1; var st,xso:string; f,g:text; i,j,k,n,code:integer; begin assign(f,fi); assign(g,fo); reset(f); rewrite(g); readln(f,st); j:=1; while j<=length(st)> if st[j] in ['0'..'9'] then begin
i:=j; xso:='';
while st[i] in ['0'..'9'] do begin xso:=xso+st[i]; i:=i+1; end; val(xso,n,code); for k:=1 to n do write(g,st[i]); j:=i+1
end else begin write(g,st[j]); j:=j+1; end; close(f); close(g); end.
Khi làm việc với các số tự nhiên, Tom và Jerry thích sắp xếp chúng theo thứ tự từ điển giống như so sánh xâu kí tự, chẳng hạn dãy số (1, 8, 9, 10, 11, 100) sẽ được sắp xếp thành (1, 10, 100, 11, 8, 9). Bài toán Tom đặt ra cho Jerry là: cho ba số A, B, K thì số trong đoạn [A; B] chia hết cho K có thứ tự từ điển nhỏ nhất là số nào? Hãy giúp Jerry giải bài toán trên. Dữ liệu vào:Một dòng duy nhất ghi ba số nguyên A, B, K (1 ≤ A ≤ B ≤ 109, 1 ≤ K ≤ 109). Dữ liệu vào đảm bảo luôn có nghiệm. Dữ liệu ra: Một dòng duy nhất ghi một số nguyên tìm được. Ví dụ:
const fin='test.inp'; fon='test.out'; var a,b,k:longint;procedure nhap; var i,j:longint; begin read(a, b, k); end;procedure xuli; var
i:longint; si,min:string; begin min:='a'; for i:=a to b do if i mod k = 0 then begin str(i,si); if si end;
write(min); end;
assign(input,fin);reset(input); assign(output,fon);rewrite(output); nhap; xuli;
close(input);close(output); end.
Input
Output: t dòng, mỗi dòng là kết quả 1 test tương ứng. Ví dụ
Const Finame='test.inp'; Foname='test.out'; var s:string; function dem(s:string):longint; var
co:array['A'..'Z'] of boolean; i,d:longint; c:char; begin
for c:='A' to 'Z' do co[c]:=false; for i:=1 to length(s) do co[s[i]]:=true; d:=0; for c:='A' to 'Z' do if co[c] then inc(d); exit(d);
procedure xuli; var i,n:longint; dx:boolean; begin
readln(n); for i:=1 to n do begin readln(s); writeln(dem(s)); end;
BEGIN assign(input,finame);reset(input); Assign(output,foname);rewrite(output); nhap;xuli; Close(input);close(output); END.
Bài 23.COUNTCBG COUNT N
Input: Gồm nhiều dòng, mỗi dòng chứa một số nguyên N. (Giới hạn : số dòng <=> Output Mỗi dòng ghi một số nguyên là số cách phân tích số N đọc được ở dòng tương ứng trong input. const fin=''; fon=''; var n,d:longint; procedure count; var i,j:longint; begin d:=0; for i:=2 to trunc(sqrt(2*n)) do begin if 2*n mod i<>0 then continue; j:=2*n div i; if (n/i-(i-1)/2)=int(n/i-(j-1)/2) then inc(d); if j<>i then if (n/j-(j-1)/2)=int(n/j-(j-1)/2) then inc(d); end; end; procedure xuli; begin assign(input,fin); reset(input); assign(output,fon); rewrite(output); while not(eof(input)) do begin readln(n); count; writeln(d); end; end; BEGIN
assign(input,fin); reset(input); assign(output,fon); rewrite(output); xuli; close(input); close(output); END.
Bài 24.MULONE Nhân 1Cho số S = 111...11 (n chữ số 1, hệ thập phân), tính S2. Input
Output: Với mỗi test ghi kết quả trên 1 dòng. } var i,j,k,n,t:longint; begin readln(t); for j:=1 to t do begin readln(n); for i:=1 to (n-1) div 9 do write('123456790'); k:=(n-1) mod 9; for i:=1 to k do write(chr(48+i)); for i:=k+1 downto 2 do write(chr(48+i)); for i:=1 to (n-1) div 9 do write('098765432'); writeln(1); end; Bài 25.Vị trí POSBạn Nam rất thông minh và chăm học. Trong học kỳ vừa rồi, bạn ấy đã đạt danh hiệu học sinh giỏi. Phần thưởng cho thành tích này của cậu là được anh dắt đi xem phim. Đứng trong dòng người xếp hàng mua vé, vì là học sinh tò mò, Nam thắc mắc không hiểu là mình đứng ở vị trí thứ mấy trong hàng người đó. Cậu bèn hỏi anh, muốn thử trí thông minh của cậu em tò mò, anh bé Nam đưa ra câu đố:”Trong hàng bây giờ có n người, có không ít hơn a người đứng trước em, và không nhiều hơn b người đứng sau em, em thử đếm xem có bao nhiêu vị trí mà em có thể đứng trong hàng?”
Input: Gồm 3 số nguyên dương n, a, b (n, a, b ≤ 100) Output: Gồm 1 dòng duy nhất là kết quả của bài toán Const fin = 'POS.INP'; fon = 'POS.OUT'; maxn=10000000+1; Var
procedure solve; begin
readln(n,a,b); if a+1>n-b then max:=a+1 else max:=n-b; if n+1 else write(n-max+1); end; Begin
assign(input,fin);reset(input); assign(output,fon);rewrite(output); solve; close(input);close(output); End. Có một tin nhắn được mã hóa và giấu trong một xâu văn bản trước khi gửi đi. Quy tắc mã hóa tin nhắn là thay mỗi chữ cái trong tin nhắn thành một chữ cái đứng cách nó k vị trí trong bảng chữ cái tiếng Anh theo quy tắc xoay vòng, các ký tự không phải chữ cái thì không thay đổi. Trong xâu có thể có nhiều tin nhắn, giữa các tin nhắn được ngăn cách nhau bởi dấu #. Biết rằng tin nhắn có độ dài lớn nhất là tin nhắn cần tìm. Nếu có nhiều tin nhắn có cùng chiều dài thì tin nhắn đầu tiên tìm thấy là tin nhắn cần giải mã.Yêu cầu: Cho trước một xâu S dài không quá 255 ký tự và một số nguyên dương k. Hãy tìm và giải mã tin nhắn được giấu trong xâu S. Input: Cho trong tệp văn bản có tên TINNHAN.INP gồm hai dòng: − Dòng đầu: xâu S; − Dòng thứ hai: số nguyên dương k. Ouput: Xuất ra tệp văn bản có tên TINNHAN.OUT gồm hai dòng: − Dòng đầu: số lượng tin nhắn tìm được; − Dòng thứ hai: nội dung tin nhắn cần tìm đã được giải mã. Ví dụ
1
2 PASCAL
Chương trìnhConst fi='TINNHAN.INP'; fo='TINNHAN.OUT'; var k:longint; procedure giaima(s:string); var i:longint; begin for i:=1 to length(s) do begin if ('A'<=s[i])> begin k:=k mod 26; if ord(s[i])-64 - k > 0 then write(chr(ord(s[i])-k)) else write(chr(ord(s[i])-k+26)); end
else write(s[i]); end;
end; procedure solve; var i,d,dem,lmax:longint; a:array[1..200] of string; x,s,s1:string; begin readln(s); readln(k); s:=s+'#';d:=0;x:=''; for i:=1 to length(s) do if s[i]<>'#' then x:=x+s[i] else begin
inc(d); a[d]:=x;
x:=''; end;
//for i:=1 to d do writeln(a[i]); lmax:=0;
for i:=1 to d do if length(a[i])>lmax then begin lmax:=length(a[i]); s1:=a[i]; end;
dem:=0; for i:=1 to d do if length(a[i])=lmax then inc(dem); writeln(dem); //writeln(s1); giaima(s1); end;
Assign(input,fi); Reset(input); Assign(output,fo); Rewrite(output); solve;
Close (output);Close(input); End.
Một con robot di chuyển theo một chương trình định sẵn trên mặt phẳng toạ độ. Chương trình này được thể hiện dưới dạng một dãy N lệnh (1N3000). Các lệnh thuộc một trong các dạng sau:
Yêu cầu: Cho một chương trình điều khiển robot, hãy xác định chiều dài T đoạn đường mà con robot đã đi được, biết mỗi bước của nó dài d(cm). Ban đầu con robot đứng tại vị trí (0,0) và hướng theo chiều dương của trục hoành. Dữ liệu: Vào từ file văn bản PATH.INP:
Kết quả: Ghi ra file PATH.OUT chứa chiều dài T tìm được. Ví dụ: PATH.INP PATH.OUT 4 1 F 5
R 7 F 2
Chương trìnhconst finp='path.inp'; fout='path.out'; var i, n, d, x, s: longint; c: char;
begin assign(input,finp); reset(input); assign(output,fout); rewrite(output); readln(n,d); for i:=1 to n do begin readln(c,c,x); s:=s+x; end;
writeln(S); close(input); close(output); end.
Input: Dòng đầu chứa T – số lượng testcase. T nhóm dòng, mỗi nhóm miêu tả 1 testcase.
Output: Gồm T dòng, dòng thứ i ghi một số nguyên là diện tích hình chữ nhất lớn nhất tìm được tương ứng với testcase thứ i. Example
Giới hạn: 30% số điểm có m, n ≤ 10, 30% số test có 10 < max(m,n) ≤ 40 const fin='MESSAGE.INP';fon='MESSAGE.OUT'; maxn=10; maxm=10; var f:array[0..maxN,0..maxn] of longint; a,b:array[1..maxM,1..maxN] of char; m,n:longint; procedure enter; var i,j:longint; begin
readln(m,n); for i:=1 to m do begin for j:=1 to n do read(a[i,j]); readln; end;
for i:=1 to m do begin
for j:=1 to n do read(b[i,j]); readln;
end; end;
var r,s:longint; begin
for r:=0 to u-1 do for s:=0 to v-1 do if a[i+r,j+s] <>b[p+r,q+s] then exit(0); exit(u*v); end;
var u,v,p,q,i,j,kmax,imax,max,dt:longint; begin max:=0;
for u:=1 to m do for v:=1 to n do begin //xet cac hinh kich thuoc (u,v) bang a for i:=1 to m-u do for j:=1 to n-v do //voi moi hinh bang a, xet tat ca //cac hinh bang b for p:=1 to m-u do for q:=1 to n-v do begin //so sanh hinh dt:=ss(i,j,p,q,u,v); if max end; end;
BEGIN assign(input,fin);reset(input); assign(output,fon);rewrite(output); enter;
solve; close(input);close(output); END.
Bài 29.Từ dài nhất WORDHương có một xâu chứa các kí tự alphabe ‘a’…’z’ và các kí tự trống, cô ấy muốn tìm trong xâu các từ dài nhất có kí tự bắt đầu trùng với một kí tự bất kỳ nào đó trong xâu. Một từ theo Hương là một xâu chứa các kí tự liên tiếp không có kí tự trống là xâu con của xâu đã cho. Ví dụ, Hương có xâu ‘ toi lo lang cho viêc hoc tap qua’. Kí tự bắt đầu mà Hương muốn tìm là ‘t’, như vậy từ phải tìm là ‘toi’ , ‘tap’Yêu cầu: Tìm các từ dài nhất theo yêu cầu của Hương Dữ liệu vào: có cấu trúc như sau:
Dữ liệu ra: Mỗi dòng ghi một tìm được Ví dụ:
const fin='word.inp'; fon='word.out';
var
i,d,n,max:longint; w:array[1..1000] of string; s:string; c:char;
n:=0; s:='';
while not eoln do begin
read(c); if c<>' ' then s:=s+c else begin
if s<>'' then begin
inc(n); w[n]:=s;
s:=''; end;
end; end;
inc(n); w[n]:=s;
readln; read(c);
//for i:=1 to n do writeln(w[i]); //writeln(c); max:=0; for i:=1 to n do if (w[i][1]=c) and (length(w[i])>max) then max:=length(w[i]); for i:=1 to n do if (w[i][1]=c) and (length(w[i])=max) then writeln(w[i]); end;
begin assign(input,fin); reset(input); assign(output,fon); rewrite(output); xuli;
close(input); close(output); end.
Ví dụ: chuỗi ‘123/456’ biểu diễn cho phân số chuỗi ‘1/12’ biểu diễn cho phân số Yêu cầu: cho chuỗi có dạng phân số. Sau đó xuất ra dạng tối giản của phân số đó. Input: Xâu s biểu diễn phân số Ouput: tối giản của phân số đó. Ví dụ: Chương trìnhProgram Toigian; Var
i,j,p:longint; t,m,s:string; kq1,kq2:extended; t1,m1,uc,r:longint; Begin Write('Nhap phan so: '); Readln(s); t:='';
m:=''; For i:=1 to length(S) do IF s[i]='/' then p:=i;
For i:=1 to p-1 do t:=t+s[i]; For j:=p+1 to length(s) do m:=m+s[j]; val(t,t1,r); val(m,m1,r); For i:=1 to t1 do If (t1 mod i =0) and (m1 mod i=0) then uc:=i; kq1:=t1/uc; kq2:=m1/uc; Write('Toi gian phan so la: ',kq1:0:0,'/',kq2:0:0); Readln; End.
Chia sẻ với bạn bè của bạn:
|