Đề thi học sinh giỏi cấp trường môn Tin học Lớp 12- Năm học 2020-2021 - Trường THPT Liễn Sơn

TRƯỜNG THPT LIỄN SƠN
(Đề thi có 2 trang)
KÌ THI HSG 12 CÂPS TRƯỜNG
MÔN: TIN HỌC - NĂM HỌC 2020-2021
(Thời gian làm bài: 180 phút)
Bài 1: 
Anh Bo có một số tiền là n đồng. Anh định đem n đồng này gửi ngân hàng với lãi suất 10% một năm. Cứ sau mỗi năm anh sẽ ra ngân hàng rút tiền lãi rồi nhập chung với tiền gốc để gửi lại cho năm sau (nếu tiền lãi là số thập phân lẻ thì sẽ được làm tròn đến hàng đơn vị, nghĩa là từ 0.5 trở lên thì làm tròn lên 1; dưới 0.5 thì làm tròn về 0). Anh dự định khi nào đủ số tiền m đồng thì sẽ rút toàn bộ để đi mua bò. Hỏi sau mấy năm thì anh Bo sẽ có đủ tiền mua bò?
Dữ liệu nhập:
- Là hai số nguyên n và m (10 ≤ n < m ≤ 109)
Dữ liệu xuất:
- Là số năm cần gửi ngân hàng.
Ví dụ
input
Output
100 120
2
100 160
5
Trong test 2:
Sau năm 1: 110 đồng
Sau năm 2: 121 đồng
Sau năm 3: 133 đồng
Sau năm 4: 146 đồng
Sau năm 5: 161 đồng
Bài 2: 
Cho hai số nguyên x và n, hãy tính lũy thừa xn.
Dữ liệu nhập:
- Là hai số nguyên x và n cách nhau một khoảng trắng (1 ≤ x ≤ 1000, 1 ≤ n ≤ 1012)
Dữ liệu xuất:
- Là 4 số cuối của lũy thừa xn (xn mod 104)
Ví dụ
input
Output
2 3
8
3 2
9
Bài 3:
Cho dãy số gồm n số nguyên a1, a2, , an. Một đoạn con của dãy được định nghĩa là dãy ai, ai+1, , aj với 1 ≤ i ≤ j ≤ n, đoạn con này có chiều dài là (j - i + 1). Bây giờ ta chọn hai đoạn con X và Y không có phần tử chung và có cùng chiều dài là k (k >0). Ký hiệu hai đoạn đó là x1, x2, ..., xk và y1, y2, ..., yk. Sau đó tính tổng:
S = x1*yk + x2*yk-1 + ... + xk-1*y2 + xk*y1
Yêu cầu: Với các đoạn con X, Y có thể có trong dãy n số trên, hãy tìm giá trị lớn nhất của S.
Dữ liệu nhập:
- Dòng thứ nhất là số nguyên n (2 ≤ n ≤ 3000).
- Dòng thứ hai là n số nguyên a1, a2, , an (|ai| ≤ 106), mỗi số cách nhau một khoảng trắng.
Dữ liệu xuất:
- Là giá trị lớn nhất của S.
Ví dụ
input
Output
2 38
2 3 0 3 0 3 2 1
13
5
3 2 -9 1 -8
72
Test 1: X = { 2, 3 }, Y = { 3, 2 }
Test 2: X = { -8 }, Y = { -9 }
 -----------------------Hết-----------------
ĐÁP ÁN Tin
Bài 1: (4 điểm)
Code pascal
var n,m,d:longint;
 s:real;
begin
 readln(n,m);
 s:=n;
 d:=0;
 while s<m do
 begin
 s:=s+round(s*10/100);
 d:=d+1;
 end;
 write(d);
 readln;
end.
Code C++
#include 
using namespace std;
int main ()
{
 long long n,m,dem=0;
 cin>>n>>m;
 float s=n;
 while (s<m)
 {
 s+=round(s*10/100);
 dem++;
 }
 cout<<dem;
 return 0;
}
 Bài 2: (4 điểm)
Code pascal
var x,y:int64;
function mu(a,b:int64):int64;
var k,h:int64;
begin
if b = 1 then exit(a mod 10000);
k:=b div 2;
h:=a*a mod 10000;
if b mod 2 = 0 then exit(mu(h,k) mod 10000)
else exit((mu(h,k) mod 10000) * a mod 10000);
end;
begin
read(x,y);
write(mu(x,y));
end.
Code C++
 #include 
using namespace std;
int main()
{
long long a,b;
cin>>a>>b;
if(b>10000)b=b%10000;
int c=1;
while(b!=0)
{
 c=c*a%10000;b--; 
}
cout<<c;
}
Bài 3: (2 điểm)
Code pascal
var n:longint;
 a:array[0..5000] of int64;
 f:array[0..5000,0..5000] of int64;
function max(a,c:int64):int64;
begin
 if a< c then exit(c) else exit(a);
end;
procedure qhd;
var i,j,t:longint;
 max1:int64;
begin
 max1:=low(int64);
 for i:=1 to n-1 do
 for j:=i+1 to n do
 begin
 f[i,j]:=max(a[i]*a[j],f[i-1,j+1]+a[i]*a[j]);
 max1:=max(max1,f[i,j]);
 end;
 write(max1);
end;
var i:longint;
begin
 readln(n);
 for i:=1 to n do
 read(a[i]);
 readln;
 qhd;
 readln;
end.
Code C++
 #include 
#include 
#include 
#include 
#include 
#include 
#define max(a,b) (a>b?a:b)
using namespace std;
using ll = long long;
using pi = pair ;
ll a[3001], b[3001];
ll dp[3001][3001];
int main() {
	int n;
	cin >> n;
	for (int i = 1; i <= n; ++i) {
	cin >> a[i];
	}
	for (int i = 1; i <= n; ++i) {
	b[i] = a[n - i + 1];
	}
	ll res = LLONG_MIN;
	for (int i = 1; i <= n; ++i) {
	for (int j = 1; j <= n - i; ++j) {
	dp[i][j] = max(dp[i - 1][j - 1] + a[i] * b[j], a[i] * b[j]);
	res = max(res, dp[i][j]);
	}
	}
	cout << res;
	return 0;
}