Bài tập về mảng 1 chiều tin 11 pascal năm 2024

Bài tập về mảng 1 chiều trong Pascal.

Cho 1 dãy số gồm n phần tử n<=15. Giá trị từng phần tử là số thực. Thực hiện các chương trình

sau:

1. Nhập từ bàn phím số phần tử và giá trị từng phần tử

2. Tính tổng các phần tử âm của dãy

3. Tính tổng và trung bình cộng của các phần tử chẵn của dãy

4. Tìm phần tử có giá trị lớn nhất của dãy

5. Tìm phần tử có giá trị nhỏ nhất

6. Sắp xếp dãy theo chiều giảm dần về giá trị của từng phần tử

7. In các kết quả trên ra màn hình

program vd1;

var i,n :Byte;

ta, tb, b, c, d :real;

a: array[1..15] of real ;

begin

write(' nhập số lượng phần tử n ='); readln(n);

Writeln('Nhap mang a: ');

for i:=1 to n do

begin

write('a[',i,']= ');

readln(a[i])

end;

ta:=0;

for i:=1 to n do if a[i] <0 then ta= ta + a[i] ; { tính tổng âm}

tc:= 0; t:=1;

for i:=1 to n do if i mod 2 =0 then begin

t= t+1 ;

tc= tc + a[i] ; {tính tổng phần tư chẵn}

end;

ttc = tc/t ; { trung bình phần tử chẵn}

max:= a[1];

for i=2 to n do if max < a[i] then max =a[i] ; { tìm phần tử lớn nhất}

min:= a[1];

for i=2 to n do if min > a[i] then min =a[i] ; { tìm phần tử nhỏ nhất}

for i=2 to n do

for j=n down to i do

if (a[j]> a[j-1])

then begin

b:= a[j-1] ;

a[j-1]:=a[j];

a[j]:=b;

end; {sắp xếp các phần tử giảm dần về giá trị}

for i=1 to n then begin

write( a[i]);

writeln;

end; {in ra theo chiều dọc mảng}

end. hết

nếu muốn in theo chiều ngang

for i=1 to n then begin

write( a[i]);

write(' '); { dấu cách giữa 2 giấu ' }

end;

• 1. 2018 GV: PHẠM THỊ BÍCH TƯỜNG EMAIL:[email protected] KIỂU DỮ LIỆU CÓ CẤU TRÚC TRONG PASCAL BÀI TẬP MẢNG CƠ BẢN & NÂNG CAO
• 2. CƠ BẢN................................................................................................................. 3 Bài tập 1: Viết chương trình tìm giá trị lớn nhất của một mảng chứa các số nguyên gồm N phần tử. ................................................................................................................................. 3 Bài tập 2: Viết chương trình tính tổng bình phương của các số âm trong một mảng gồm N phần tử. ................................................................................................................................. 3 Bài tập 3: Viết chương trình nhập vào một mảng gồm N số nguyên. Sắp xếp lại mảng theo thứ tự tăng dần và in kết quả ra màn hình............................................................................. 4 Bài tập 4: Viết chương trình nhập vào một mảng A gồm N số nguyên và nhập thêm vào một số nguyên X. Hãy kiểm tra xem phần tử X có trong mảng A hay không?..................... 4 Bài 5: Nhập vào mảng A có N phần tử. Tìm phần tử xuất hiện nhiều nhất trong mảng.... 5 Bài 6: Viết chương trình nhập vào một mảng số nguyên có N phần tử theo thứ tự giảm dần và số M. Chèn số M vào mảng sao cho mảng vẫn có thứ tự giảm dần. In mảng sau khi chèn..................................................................................................................................... 7 Bài7: Nhập vào mảng 1 chiều gồm 1 dãy số nguyên N phần tử. Hãy xóa các phần tử trùng nhau trong mảng và in kết quả ra màn hình.......................................................................... 7 Bài 8: Viết chương trình Kiểm tra số chính phương trong mảng một chiều........................ 9 Bài 10: Viết chương trình nhập vào số nguyên dương N và dãy A gồm N số nguyên A1, A2,... AN. Hãy sắp xếp dãy số trên sao cho các số chẵn chia hết cho 3 lên đầu.................11 dãy, các số lẻ chia hết cho 3 xuống cuối dãy, các số còn lại ở giữa dãy vẫn giữ được ......11 thứ tự trước khi nhập vào. In ra màn hình dãy trước và sau khi sắp xếp mỗi phần tử.....11 cách nhau một khoảng trắng.................................................................................................11 BÀI 11: Nhập vào một số n (5<=n<=10) và n phần tử của dãy a, 1
• 3. dãy theo chiều giảm dần về giá trị của từng phần tử......................................16 g) In các kết quả trên ra màn hình .....................................................................................16 Bài 14: Viết chương trình mảng một chiều gồm n phần tử n<=100 kiểu nguyên..............23 Bài 15: Nhập họ tên và năm sinh của người và cho biết người này thuộc lứa tuổi nào: sơ sinh, nhi đồng, thiếu niên, thanh niên, trung niên, người lớn tuổi. Biết rằng:..................29 BÀI TẬP NÂNG CAO.........................................................................................................30 Bài tập 1: DHLOCO spoj ......................................................................................................30 Bài tập 2: Cho trước một dãy số dương có N phần tử. Bạn biết trước tổng của bất kì 2 phần tử nào trong dãy số, hãy tìm dãy số ban đầu. ..............................................................33 Bài tập 3: Một đoạn số có tổng bằng nhau trong một dãy số là một nhóm các số theo đúng thứ tự ban đầu trong dãy mà nếu nhóm với nhau thì sẽ cho ra cùng một giá trị tổng. .....35 Bài tập 4: BONUS Spoj..........................................................................................................38
• 4. BẢN Bài tập 1: Viết chương trình tìm giá trị lớn nhất của một mảng chứa các số nguyên gồm N phần tử. Uses Crt; Type Mang = ARRAY[1..50] Of Integer; Var A:Mang; N,i,Max:Integer; Begin {Nhập mảng} Write(‘Nhap N=’); Readln(N); For i:=1 To N Do Begin Write(‘A[‘,i,’]=’); Readln(A[i]); End; {Tìm phần tử lớn nhất} Max:=A[1]; For i:=2 To N Do If Max
• 5. To N Do If A[i]<0 Then S:=S+A[i]*A[i]; {In kết quả ra màn hình} Writeln(‘S= ’, S); Readln; End. Bài tập 3: Viết chương trình nhập vào một mảng gồm N số nguyên. Sắp xếp lại mảng theo thứ tự tăng dần và in kết quả ra màn hình. Uses Crt; Type Mang = ARRAY[1..50] Of Integer; Var A:Mang; N,i,j,Tam:Integer; Begin Write(‘Nhap N=’); Readln(N); For i:=1 To N Do Begin Write(‘A[‘,i,’]=’); Readln(A[i]); End; For i:=1 To N-1 Do For j:=i+1 To N Do If A[i]>A[j] Then Begin Tam:=A[i]; A[i]:=A[j]; A[j]:=Tam; End; Writeln(‘Ket qua sau khi sap xep:’); For i:=1 To N Do Write(A[i]:5); Readln; End. Bài tập 4: Viết chương trình nhập vào một mảng A gồm N số nguyên và nhập thêm vào một số nguyên X. Hãy kiểm tra xem phần tử X có trong mảng A hay không?
• 6. = ARRAY[1..50] Of Integer; Var A:Mang; N,i,x:Integer; Begin I:=1; While (I <= N) and (X<>A[I]) do I:=I+1; If I <= N Then Timkiem:=I Else Timkiem:=0; End; Begin Write(‘Nhap N=’); Readln(N); For i:=1 To N Do Begin Write(‘A[‘,i,’]=’); Readln(A[i]); End; Write(‘Nhap X=’); Readln(x); If TimKiem(X,N,A)<>0 Then Writeln(‘Vi tri cua X trong mang la:’, TimKiem(X,N,A)) Else Writeln(‘X khong co trong mang.’); Readln; End. Bài 5: Nhập vào mảng A có N phần tử. Tìm phần tử xuất hiện nhiều nhất trong mảng. Uses crt; var a,b:array[1..100] of integer; n,i,j,d,max,k:integer; begin write('N=');readln(n); for i:=1 to n do
• 7. n do begin d:=0; for j:=i to n do if a[i]=a[j] then inc(d); if d>max then begin max:=d; b[1]:=a[i]; k:=1; end else if d=max then begin inc(k); b[k]:=a[i]; end; end; for i:=1 to k do write(b[i],' '); readln; end.
• 8. chương trình nhập vào một mảng số nguyên có N phần tử theo thứ tự giảm dần và số M. Chèn số M vào mảng sao cho mảng vẫn có thứ tự giảm dần. In mảng sau khi chèn. var a:array[1..100] of integer; n,m,i,j:integer; begin write('N=');readln(n); for i:=1 to n do begin write('a[',i,']=');readln(a[i]); end; write('M=');readln(m); write('Mang sau khi chen: '); for i:=1 to n do begin if (m>=a[i]) and (j=0) then begin write(m,' '); j:=1; end; write(a[i],' '); end; if j=0 then write(m); readln; end. Bài7: Nhập vào mảng 1 chiều gồm 1 dãy số nguyên N phần tử. Hãy xóa các phần tử trùng nhau trong mảng và in kết quả ra màn hình.
• 9. Integer; i,j,k,n:Integer; Begin Writeln('XOA BO CAC SO TRUNG NHAU'); Readln(n); For i:=1 To N Do Begin Write('-Phan tu A[',i,']= '); Readln(a[i]); End; i:=2; While i <= N Do Begin j:=1; While a[j] <> a[i] Do j:=j+1; If j < i Then Begin For k:=i to n-1 Do
• 10. to n Do Write(a[i]:8); Writeln(' Bam phim de ket thuc '); Readln End. Bài 8: Viết chương trình Kiểm tra số chính phương trong mảng một chiều. uses crt; type ArrInt = array[1..250] of integer; Var n,i,x : integer; a: ArrInt; BEGIN clrscr; write('Nhap so phan tu: '); readln(n); for i:=1 to n do begin write('Phan tu thu ',i,'= '); readln(a[i]); end; writeln('Cac so chinh phuong co trong mang:'); for i:=1 to n do begin x:=trunc(sqrt(a[i])); if sqr(x)=a[i] then write(a[i]:4); end; readln; END.
• 11. chương trình nhập số nguyên N (0 < N ≤ 10 000) và mảng a gồm N số nguyên. Tính và in ra trung bình cộng của các số âm, số dương trong a. Không tính số 0. Ví dụ : a[] = {1, -6, 0, 3, -1}. Trung bình cộng là -0.75 PROGRAM tbc_am_duong_mang; USES crt; VAR a:ARRAY[1..100] OF REAL; i,n,x,y:INTEGER; tongam,tongduong,tba,tbd:REAL; BEGIN clrscr; write('So phan tu cua day n= ');readln(n); FOR i:=1 TO n DO BEGIN write('Nhap phan tu a[',i,']: '); readln(a[i]); END; tongam:=0; x:=0; FOR i:=1 TO n DO IF a[i]<0 THEN BEGIN tongam:=tongam+a[i]; x:=x+1; END; tba:=tongam/x; write('TB cong cac so am la: ',tba:5:1); writeln; tongduong:=0; y:=0; FOR i:=1 TO n DO IF a[i]>0 THEN BEGIN tongduong:=tongduong+a[i]; y:=y+1; END; tbd:=tongduong/y; write('TB cong cac so duong la: ',tbd:5:1); readln; END.
• 12. chương trình nhập vào số nguyên dương N và dãy A gồm N số nguyên A1, A2,... AN. Hãy sắp xếp dãy số trên sao cho các số chẵn chia hết cho 3 lên đầu dãy, các số lẻ chia hết cho 3 xuống cuối dãy, các số còn lại ở giữa dãy vẫn giữ được thứ tự trước khi nhập vào. In ra màn hình dãy trước và sau khi sắp xếp mỗi phần tử cách nhau một khoảng trắng Output: Dãy trước khi sắp xếp: 1 6 5 9 12 3 4 15 7 Dãy sau khi sắp xếp: 6 12 1 5 4 7 9 3 15 Program bai1; Uses crt; Var A: array[1..250] of integer; i, N: integer; Begin Clrscr; Write(‘nhap so luong phan tu N= ‘); readln(N); For i:= 1 to N do Begin Write(‘A[‘,I,‘] = ‘);readln(A[i]); End; Writeln(‘Day truoc khi sap xep‘); For i:= 1 to N do write(A[i], ‘ ‘); Writeln; Writeln(‘Day sao khi sap xep‘); For i:=1 to N do If (A[i] mod 2=0) and (A[i] mod 3=0) write(A[i], ‘ ‘); For i:=1 to N do If ((A[i] mod 2=0) and (A[i] mod 3<>0)) or ((A[i] mod 2<>0) and (A[i] mod 3<>0)) write(A[i], ‘ ‘); For i:=1 to N do If (A[i] mod 2<>0) and (A[i] mod 3=0) write(A[i], ‘ ‘);
• 13. vào một số n (5<=n<=10) và n phần tử của dãy a, 1
• 14. 1 to n do begin write('a',i,'='); repeat readln(a[i]); if (1
• 15. writeln(a[i]); {nếu ai là nguyên tố thì in ra} end; function UCLN(a,b: integer): integer; var r : integer; begin while b<>0 do begin r := a mod b; a := b; b := r; end; UCLN := a; end; Thủ tục tính UCLN của các phần tử của một mảng procedure TinhUC; var i,u : integer; begin u := a[1]; {u là UCLN của các phần tử từ 1 đến i} for i := 2 to n do u := UCLN(u,a[i]); {là UCLN của các phần tử từ 1 đến i-1 và ai} writeln('UCLN cua ca day la:',u); end; function hammu(a : real; n : integer): real; {hàm mũ tính an} var s : real; i : integer; begin
• 16. i := 1 to n do s := s * a; hammu := s; end; Thủ tục tính tổng các phần tử có lấy mũ: procedure tong; var s : real; i : integer; {s phải khai báo là số thực để tránh tràn số} begin s := 0; for i := 1 to n do s := s + hammu(a[i],i); {s := s + (ai)i} writeln('Tong can tinh:',s:10:0); end; Thủ tục sắp xếp tăng dần các phần tử của một mảng: procedure sxep; var i,j,tg : integer; begin for i := 1 to n-1 do for j := i + 1 to n do if a[i] > a[j] then begin tg := a[i]; a[i] := a[j]; a[j] := tg; end; writeln('DAY SAU KHI SAP XEP TANG DAN:'); for i := 1 to n do writeln(a[i]); end;
• 17. lần lượt gọi từng thủ tục BEGIN nhap; inngto; tinhuc; tong; sxep; END. BÀI 12: Cho 1 dãy số gồm n phần tử n<=15. Giá trị từng phần tử là số thực. Thực hiện các chương trình sau: a) Nhập từ bàn phím số phần tử và giá trị từng phần tử b) Tính tổng các phần tử âm của dãy c) Tính tổng và trung bình cộng của các phần tử chẵn của dãy d) Tìm phần tử có giá trị lớn nhất của dãy e) Tìm phần tử có giá trị nhỏ nhất f) Sắp xếp dãy theo chiều giảm dần về giá trị của từng phần tử g) In các kết quả trên ra màn hình program vd1; var i,n :Byte; ta, tb, b, c, d :real; a: array[1..15] of real ; begin write(' nhập số lượng phần tử n ='); readln(n); Writeln('Nhap mang a: '); for i:=1 to n do begin write('a[',i,']= '); readln(a[i]) end; ta:=0;
• 18. n do if a[i] <0 then ta= ta + a[i] ; { tính tổng âm} tc:= 0; t:=1; for i:=1 to n do if i mod 2 =0 then begin t= t+1 ; tc= tc + a[i] ; {tính tổng phần tư chẵn} end; ttc = tc/t ; { trung bình phần tử chẵn} max:= a[1]; for i=2 to n do if max < a[i] then max =a[i] ; { tìm phần tử lớn nhất} min:= a[1]; for i=2 to n do if min > a[i] then min =a[i] ; { tìm phần tử nhỏ nhất} for i=2 to n do for j=n down to i do if (a[j]> a[j-1]) then begin b:= a[j-1] ; a[j-1]:=a[j]; a[j]:=b; end; {sắp xếp các phần tử giảm dần về giá trị} for i=1 to n then begin write( a[i]); writeln; end; {in ra theo chiều dọc mảng} end. hết nếu muốn in theo chiều ngang for i=1 to n then begin write( a[i]); write(' '); { dấu cách giữa 2 giấu ' } end; có gì sai sót thì bạn sửa nhe như khai báo các biến ấy có thể thiếu. cái này học hồi 11 nên không nhớ rõ lắm - Yêu cầu: Chạy lại chương trình với dãy A như sau: 12 4 6 9 Nhập số cần tìm là: 7  Xem kết quả e. Tính tích các số chắn trong dãy vd: Dãy A gồm 7 phần tử: 5 13 4 7 2 10  Tich cac so chan la: 80 BÀI GIẢI: USES CRT; VAR A: ARRAY[1..100] OF INTEGER; I,N: INTEGER;
• 19. PHAN TU: '); READLN(N); FOR I:=1 TO N DO BEGIN WRITELN('NHAP SO THU: ',I,' '); READLN(A[I]); END; TICH:=1; FOR I:=1 TO N DO IF A[I] MOD 2 =0 THEN TICH:=TICH*A[I]; WRITELN('TICH CAC SO CHAN LA: ',TICH); READLN END. Tính Trung Bình Cộng Uses CRT; Var i,n : Integer; s : Real; a : Array[1.. 100] of Real; Begin ClrScr; Write( ‘ Ban muon nhap bao nhieu PT cho mang : ‘ ); Readln(n); For i := 1 to n do Begin Write( ‘ PT A[ ‘ , i , ‘ ]= ’ ); Readln(a[i]); End; s := 0; For i := 1 to n do s := s + a[i]; Write( ‘ Trung binh cong cua day so = ‘ , s / n : 0 : 4 ); Readln; End. Nếu cần tìm phần tử lớn nhất / nhỏ nhất hoặc sắp xếp 1 dòng (1 cột) của mảng 2 chiều thì ta cũng coi dòng (cột) đó như 1 mảng 1 chiều. Chẳng hạn tất cả các phần tử trên dòng k đều có dạng chỉ số là a[k,i] với i chạy từ 1 đến n (n là số cột). Ví dụ 2. Tìm phần tử lớn nhất của dòng k và đổi chỗ nó về phần tử đầu dòng. procedure timmax(k : integer); var i, vt, tg : integer; begin
• 20. {vt là vị trí của phần tử min dòng k} for i := 1 to n do if a[k,i] > a[k,vt] then vt := i; {các phần tử dòng k có dạng a[k,i]} tg := a[k,1]; a[k,1] := a[k,vt]; a[k,vt] := tg; end; Ví dụ 3. Sắp xếp giảm dần cột thứ k. procedure sapxep(k: integer); var i,j,tg : integer; begin for i := 1 to m-1 do {mỗi cột có m phần tử, vì bảng có m dòng} for j := i+1 to m do if a[i,k] > a[j,k] then begin {các phần tử cột k có dạng a[i,k]} tg := a[i,k]; a[i,k] := a[j,k]; a[j,k] := tg; end; end; Đưa ra các số âm 1. Nhập vào 1 dãy số nguyên gồm N phần tử (N <= 100) a. Đưa ra các số âm có trong dãy và vị trí của chúng Dãy A gồm 5 phần tử: 2 15 -7 4 -20  Cac so am la: -7 vi tri la: 3 -20 vi tri la: 5
• 21. A: ARRAY[1..100] OF INTEGER; I,N: INTEGER; BEGIN WRITELN('NHAP SL PHAN TU: '); READLN(N); FOR I:=1 TO N DO BEGIN WRITELN('NHAP SO THU: ',I,' '); READLN(A[I]); END; WRITELN('CAC SO AM LA: '); FOR I:=1 TO N DO IF A[I] < 0 THEN BEGIN WRITE(A[I]:4); WRITELN(' VI TRI LA: ',I); END; READLN END. Đếm và tính tổng các số lẻ có trong dãy Dãy A gồm 6 phần tử: 2 5 8 7 12 3  Co 3 so le Tong la: 15 BÀI GIẢI: USES CRT; VAR A: ARRAY[1..100] OF INTEGER; I,N,DEM,S: INTEGER; BEGIN WRITELN('NHAP SL PHAN TU: '); READLN(N); FOR I:=1 TO N DO BEGIN WRITELN('NHAP SO THU: ',I,' '); READLN(A[I]); END; FOR I:=1 TO N DO IF A[I] MOD 2 <> 0 THEN
• 22. LE'); WRITELN('TONG LA: ',S); READLN END. Tính TB cộng các bội số của 3 và đưa ra các bội số đó c. Tính TB cộng các bội số của 3 và đưa ra các bội số đó vd: Dãy gồm 5 phần tử: 10 6 4 3 13  Cac boi so cua 3 la: 6 3 TB Cong la: 4.5 BÀI GIẢI: USES CRT; VAR A: ARRAY[1..100] OF INTEGER; I,N,DEM,S: INTEGER; TBC: REAL; BEGIN WRITELN('NHAP SL PHAN TU: '); READLN(N); FOR I:=1 TO N DO BEGIN WRITELN('NHAP SO THU: ',I,' '); READLN(A[I]); END; WRITELN('CAC BOI SO CUA 3 LA: '); FOR I:=1 TO N DO IF A[I] MOD 3 = 0 THEN BEGIN WRITE(A[I]:4); DEM:=DEM+1; S:=S+A[I]; END; WRITELN; {XUONG DONG} TBC:= S/DEM; WRITELN('TB CONG LA: ',TBC:6:1); READLN END. d) Nhập vào số nguyên K, tìm xem K có trong dãy không?
• 23. nguyên K, tìm xem K có trong dãy không? Nếu có thì đưa ra các vị trí của nó trong dãy. Nếu không thì thông báo “Không tìm thấy”. Vd: Dãy A gồm 5 phần tử: 1 5 6 12 5 Nhap so can tim: 5  Cac vi tri cua 5 la: 2 5 BÀI GIẢI: USES CRT; VAR A: ARRAY[1..100] OF INTEGER; I,N,DEM,K: INTEGER; BEGIN WRITELN('NHAP SL PHAN TU: '); READLN(N); FOR I:=1 TO N DO BEGIN WRITELN('NHAP SO THU: ',I,' '); READLN(A[I]); END; WRITE('NHAP SO CAN TIM: '); READLN(K); WRITELN('CAC VI TRI CUA ',K,' LA: '); FOR I:=1 TO N DO IF A[I] = K THEN BEGIN WRITE(I:4); DEM:=DEM+1; END; WRITELN; {XUONG DONG} IF DEM = 0 THEN WRITELN('KHONG TIM THAY VI TRI NAO'); READLN END.
• 24. chương trình mảng một chiều gồm n phần tử n<=100 kiểu nguyên
• 25.
• 26.
• 27.
• 28.
• 29.
• 30. họ tên và năm sinh của người và cho biết người này thuộc lứa tuổi nào: sơ sinh, nhi đồng, thiếu niên, thanh niên, trung niên, người lớn tuổi. Biết rằng: + Sơ sinh tuổi từ 0->0 + Nhi đồng tuổi từ 2->9 + Thiếu niên tuổi từ 10->15 + Thanh niên tuổi 16->32 + Trung niên tuổi từ 33 -> 50 + Người già tuổi từ 50 trở lên
• 31. longint; i,n:longint; begin clrscr; write('nhap so nguoi:'); readln(n); for i:=1 to n do begin write('nhap tuoi cua nguoi thu ',i,':'); readln(a[i]); end; for i:=1 to n do begin write('nguoi thu',i,':'); case a[i] of 0:writeln('tre so sinh'); 2..9:writeln('nhi dong'); 10..5:writeln('thieu nien'); 16..32:writeln('thanh nien'); 33..50:writeln('trung nien'); Else writeln('nguoi gia'); end; end; readln; end. BÀI TẬP NÂNG CAO Bài tập 1: DHLOCO spoj Carnaval Hạ Long 2015 với chủ đề “Hội tụ tinh hoa – Lan tỏa nụ cười”, điểm mới của lễ hội là sự song hành giữa biểu diễn nghệ thuật “Nơi tinh hoa hội tụ” và diễu hành đường phố “Nụ cười Hạ Long” với sự góp mặt của hơn 2000 diễn viên quần chúng. Có rất nhiều chương trình vui chơi được tổ chức, một trong những trò chơi thu hút được nhiều du khách tham gia đó là trò chơi nhảy lò cò, cụ thể:
• 32. vượt qua một đoạn đường dài n mét, mỗi bước, người chơi có ba cách nhảy với độ dài bước nhảy tương ứng là 1 mét, 2 mét, 3 mét. Một cách đi chuyển đúng là dãy các bước nhảy có tổng đúng bằng n. Yêu cầu: Cho n và M, gọi K là số cách đi chuyển đúng khác nhau để đi hết đoạn đường n mét, hãy tính phần dư của K chia M. Input gồm một dòng chứa hai số nguyên dương n, M (M ≤ 2015); Output một số nguyên là phần dư của K chia M. Example Input: 5 100 Output 13 Ghi chú: Có 20% số test ứng với 20% số điểm có n ≤ 20; Có 40% số test ứng với 40% số điểm có n ≤ 106; Có 40% số test còn lại ứng với 40% số điểm có n ≤ 1015.: 2. Gợi ý DHLOCO spoj Trò chơi lò cò -Các bạn sử dụng thuật toán nhân ma trận là dễ nhất ype matrix=array[1..3,1..3] of int64; const fi=''; fo=''; var f:text; a,b:matrix; n:int64; m:int64; procedure input; begin
• 33. u:=1 to 3 do for v:=1 to 3 do begin c[u,v]:=0; for k:=1 to 3 do c[u,v]:=(c[u,v]+a[u,k]*b[k,v])mod m; end; exit(c); end; function luythua(a:matrix;k:int64):matrix; var b:matrix; begin if k=1 then exit(a) else begin b:=luythua(a,k div 2); b:=nhan(b,b); if k mod 2 =1 then b:=nhan(b,a); end; exit(b); end; procedure solve; begin a[1,1]:=0; a[1,2]:=1; a[1,3]:=0; a[2,1]:=0; a[2,2]:=0; a[2,3]:=1; a[3,1]:=1; a[3,2]:=1; a[3,3]:=1; b:=luythua(a,n-1); end;
• 34. of 1: writeln(f,1); 2: writeln(f,2 mod m); 3: writeln(f,4 mod m); else begin solve; writeln(f,(b[1,1]+b[1,2]*2+b[1,3]*4)mod m); end; end; close(f); end; BEGIN input; output; END. Bài tập 2: Cho trước một dãy số dương có N phần tử. Bạn biết trước tổng của bất kì 2 phần tử nào trong dãy số, hãy tìm dãy số ban đầu. Input Dòng đầu tiên là N, số phần tử của dãy số. (2 <= N <= 1000) N dòng sau, mỗi dòng gồm N số (mỗi số <= 100 000) mô tả ma trận biểu diễn tổng của 2 phần tử trong dãy. * S(i,j) = 0 nếu i = j. * S(i,j) = A[i] + A[j] với i ≠ j, là tổng của phần tử thứ i và thứ j trong dãy số. Output In ra trên 1 dòng dãy số cần tìm. Input luôn đảm bảo có 1 đáp số duy nhất.
• 35. 1 Input2: 4 0 3 6 7 3 0 5 6 6 5 0 9 7 6 9 0 Ouput2: 2 1 4 5 const fi=''; nmax=1000; type data=longint; var f:text; A:array[1..nmax,1..nmax] of data; B:array[1..nmax] of data; N:data; procedure docfile; var i,j:data; begin assign(f,fi); reset(f); readln(f,n); for i:=1 to n do for j:=1 to n do
• 36. div 2; B[2]:=(a[1,2]-a[1,3]+a[2,3]) div 2; write(b[1],' ',b[2],' '); for i:=3 to n do write((A[1,2]-A[1,i]-a[2,i]) div (-2),' '); end; begin docfile; xuli; end. Bài tập 3: Một đoạn số có tổng bằng nhau trong một dãy số là một nhóm các số theo đúng thứ tự ban đầu trong dãy mà nếu nhóm với nhau thì sẽ cho ra cùng một giá trị tổng. Ví dụ với dãy: 2 5 1 3 3 7 thì ta có thể nhóm thành: (2 5) (1 3 3) (7) cùng cho giá trị tổng là 7. Chú ý: đoạn đặc biệt chứa tất cả các phần tử của dãy cũng được coi là một đoạn có tổng bằng nhau với chính giá trị tổng các số của dãy đó. Yêu cầu: viết chương trình nhận vào các dãy số nguyên dương và trả về giá trị tổng nhỏ nhất có thể của một đoạn tổng bằng nhau trong dãy. Dữ liệu vào Dòng đầu tiên chứa một số nguyên 1 ≤ t ≤ 1000 là số lượng bộ test. Mỗi bộ test bao gồm:  Dòng đầu tiên chứa thứ tự bộ test và số M (1≤ M ≤ 10000) là số phần tử của dãy.  Các dòng tiếp theo mỗi dòng ghi 10 số của dãy phân cách bởi 1 dấu cách. Dòng cuối cùng có thể có ít hơn 10 số. (Các số trong dãy đều nhỏ hơn 20000).
• 37. mỗi bộ test, in ra trên một dòng gồm số thứ tự bộ test và tổng nhỏ nhất có thể đạt được của các đoạn số có tổng bằng nhau. Example INPUT OUTPUT 31 6 2 5 1 3 3 7 2 6 1 2 3 4 5 6 3 20 1 1 2 1 1 2 1 1 2 1 1 2 1 1 2 1 1 2 1 1 1 72 21 3 2 onst fi=''; nmax=10000; type data=longint; var f:text; A:array[0..nmax+1] of data; n,test:data; function tknp(dau,cuoi,x:data):data; var giua:data; begin while dau<=cuoi do begin giua:=(dau+cuoi) div 2; if a[giua]=x then exit(giua) else if a[giua]>x then cuoi:=giua-1 else dau:=giua+1; end; exit(0);
• 38. i:=1 to sl do begin vt:=tknp(id,n,a[id]+x); if vt=0 then exit(false); id:=vt; end; exit(true); end; procedure xuli; var i,j:data; begin i:=a[n]; if a[n] mod i = 0 then if check(a[n] div i, i) then begin writeln(test,' ',a[n] div i); exit; end; i:=a[n] div 2; if a[n] mod i = 0 then if check(a[n] div i, i) then begin writeln(test,' ',a[n] div i); exit; end; for i:=trunc(sqrt(a[n])) downto 2 do if a[n] mod i = 0 then if check(a[n] div i, i) then begin writeln(test,' ',a[n] div i);
• 39. i,j,sl:data; begin assign(f,fi); reset(f); read(f,sl); a[0]:=0; for i:=1 to sl do begin read(f,test,n); for j:=1 to n do begin read(f,a[j]); a[j]:=a[j-1]+a[j]; end; xuli; end; close(f); end; begin docfile; end. Bài tập 4: BONUS Spoj Tuấn là người chiến thắng trong một cuộc thi “tìm hiểu kiến thức vũ trụ” và được nhận các phần thưởng do công ty XYZ tài trợ. Các phần thưởng được bố trí trên một bảng hình vuông nxn có dạng một lưới ô vuông kích thước đơn vị. Các dòng của bảng được đánh số từ 1 đến n, từ trên xuống dưới và các cột của bảng được đánh số từ 1 đến n, từ trái qua phải. Ô nằm trên giao của dòng i và cột j được gọi là ô (i,j) và trên ô đó chứa một món quà có giá trị là a[i,j] (1 <= i, j <= n)
• 40. thưởng, Tuấn được phép chọn một hình vuông kích thước k x k chiếm trọn trong một số ô của bảng và nhận tất cả các phần quà có trong các ô nằm trong hình vuông đó. Yêu cầu: Hãy xác định tổng giá trị lớn nhất của món quà mà Tuấn có thể nhận được. Dữ liệu:  Dòng thứ nhất chứa hai sô nguyên dương n, k (n <= 1000, n/3 <= k <= n).  Dòng thứ i trong số n dòng tiếp theo chứa n số nguyên dương, số thứ j là a[i,j] (a[i,j] <= 1000) Kết quả:  Ghi ra một số nguyên duy nhất là tổng giá trị lớn nhất của các món quà mà Tuấn có thể nhận được. Ví dụ: INPUT OUTPUT Code tham khảo const fi=''; nmax=1000; type data=longint; var f:text; A:array[0..nmax+1,0..nmax+1] of longint; n,k:data; procedure xuli; var i,j:data; 4 3 1 9 1 1 9 9 9 9 1 9 9 9 1 9 9 14 86
• 41. to n do begin a[i,0]:=0; a[0,i]:=0; end; res:=low(data); for i:=1 to n do for j:=1 to n do begin read(f,a[i,j]); A[i,j]:=a[i,j]+a[i-1,j]+a[i,j-1]-a[i-1,j-1]; end; for i:=k to n do for j:=k to n do if res