Đề thi Tin học 10 – Trại hè Hùng Vương lần thứ XV – THPT CHUYÊN BẮC KẠN – Kèm code mẫu
Đề thi Tin học 10 – Trại hè Hùng Vương lần thứ XV – THPT CHUYÊN BẮC KẠN
TỔNG QUAN ĐỀ THI
| Tên bài | File chương chương trình | File dữ liệu vào | File kết quả | |
| Bài 1 | Đàn cừu | Sheeps.* | Sheeps.inp | Sheeps.out |
| Bài 2 | Số chính phương | Chinhphuong.* | Chinhphuong.inp | Chinhphuong.out |
| Bài 3 | Hàng cây | Hangcay.* | Hangcay.inp | Hangcay.out |
Dấu * được thay thế bởi PAS hoặc CPP của ngôn ngữ lập trình được sử dụng tương ứng là Pascal hoặc C++.
Hãy lập trình giải các bài toán sau:
Bài 1. Đàn cừu (6 điểm)
Thắng vừa chuyển đến làm việc cho một nông trại. Thắng được giao nhiệm vụ quản lý đàn cừu của nông trại. Thắng nghĩ cần phải gán cho mỗi chú cừu một số thứ tự để việc theo dõi và chăm sóc đàn cừu được tốt hơn.
Đàn cừu có n con, mỗi con sẽ được Thắng gán cho một số thứ tự trong đoạn từ 1 đến n, hai chú cừu khác nhau được gán bởi hai số thứ tự khác nhau.
Yêu cầu: Thắng cần biết khi gán số thứ tự cho đàn cừu thì phải viết bao nhiêu chữ số.
Input: SHEEPS.inp
Gồm một dòng ghi số n ( 1£ n£ 109)
Output: SHEEPS.out
Gồm một dòng ghi số chữ số mà Thắng phải viết
Ví dụ:
| SHEEPS.inp | SHEEPS.out |
| 3 | 3 |
| 100 | 192 |
| 1000000 | 5888896 |
Subtask 1 (60% điểm): Giả thiết N≤ 106
Subtask 2 (40% điểm): Giả thiết N≤ 109
Bài 2: Số chính phương (7 điểm)
Bạn An rất thích các số chính phương, muốn tìm hiểu về nó, và biết rằng số chính phương cũng được biểu diễn bằng tích của một tập các số tự nhiên phân biệt. Chẳng hạn: 144 = 2 ´ 3 ´ 4 ´ 6; 324=2 ´ 3 ´ 6 ´ 9. Bạn An hay ngẫm nghĩ về nó mọi lúc khi có thời gian rãnh. Hôm nay, giờ giải lao trên lớp, An quay sang hỏi Hưng, với số tự nhiên N cho trước thì số chính phương lớn nhất được biểu diễn bằng tích của một tập các số tự nhiên phân biệt từ 1 đến N là bao nhiêu? Hưng suy nghĩ mãi mà chưa trả lời được câu đố và thời gian thì ít quá.
Yêu cầu: Cho một số nguyên N, hãy giúp Hưng đưa ra số chính phương lớn nhất là tích của một tập các số tự nhiên phân biệt từ 1 đến N. Số đó có thể rất lớn nên chỉ cần xuất ra phần dư khi chia số đó cho 1000000007.
Dữ liệu: Từ file văn bản CHINHPHUONG.INP có cấu trúc:
Một dòng duy nhất chứa số nguyên dương N. (N ≤ 4.104)
Kết quả: Ghi vào file văn bản CHINHPHUONG.OUT có cấu trúc:
Một dòng duy nhất là kết quả bài toán sau khi đã mod 1000000007
Ví dụ
| CHINHPHUONG.INP | CHINHPHUONG.OUT |
| 7 | 144 |
- Subtask 1 (2 điểm): Giả thiết N≤ 102 .
- Subtask 2 (2 điểm): Giả thiết N≤ 103 .
- Subtask 3 (2 điểm): Giả thiết N≤ 4.104 .
Bài 3. Hàng cây (7 điểm)
Lão phù thủy giam công chúa xứ sở thần tiên trong một lâu đài, biết bao hiệp sĩ đến cứu nàng nhưng đâu có dễ. Chỉ có một con đường duy nhất vào lâu đài, trên con đường ấy có một hàng n cây, cây thứ i có độ cao là ai (1 ≤ ai ≤ 109, 1≤ n≤106, i=1..n).
Lão ta thích thuật toán nên nghĩ ra một số nguyên k và thách thức các hiệp sĩ tìm ra dãy liên tục các cây có độ cao trung bình là k (1 ≤ k ≤ 109) trong khoảng 1 giây. Nếu ai giải được thì người đó có thể cứu công chúa.
Yêu cầu: Cho n, k và ai, i =1..n. Hãy xác định dãy liên tục các cây có độ cao trung bình là k dài nhất, chỉ ra cây đầu tiên và độ dài của dãy tìm được. Nếu tồn tại nhiều dãy cùng độ dài thì chỉ ra dãy cây có vị trí đầu nhỏ nhất. Nếu không tồn tại dãy cây thì đưa ra một số 0.
Dữ liệu: Vào từ file văn bản TREELINE.INP
- Dòng đầu tiên chứa 2 số nguyên n và k.
- Dòng thứ 2 chứa n số nguyên a1, a2, . . ., an.
- Các số trên cùng một dòng được ghi cách nhau ít nhất một dấu cách.
Kết quả: Đưa ra file văn bản TREELINE.OUT trên một dòng 2 số nguyên: độ dài của dãy tìm được và số thứ tự của cây đầu tiên hoặc một số 0 nếu không tồn tại dãy, giữa hai số cách nhau một dấu cách.
Ví dụ:
| TREELINE.INP | TREELINE.OUT |
| 7 6
1 2 4 5 6 7 8 |
5 3 |
Ràng buộc: Có 50% số test ứng với 50% số điểm của bài có n ≤ 103
——————————- Hết ——————————-
Code mẫu (Pascal) Đề thi Tin học 10 – Trại hè Hùng Vương lần thứ XV
Bài 1:
Program Sheeps;
Uses Math;
Const fi='D:\SHEEPS.inp'; fo='D:\SHEEPS.out';
Var f:text;
N,K,i:longint;
S:int64;
S1:string;
A,T:array[0..10]
of int64;
Begin
Assign(f,fi); reset(f);
Readln(f,N);
Close(f);
Str(N,S1);
K:=Length(S1);
A[1] :=1; T[1]
:=9;
For i:=2 to 10 do
Begin
A[i] :=A[i-1]
*10;
T[i] :=T[i-1] +(A[i] *10-A[i]
)*i;
End;
S:=(N-A[k] +1)*K+T[k-1]
;
Assign(f,fo); rewrite(f);
Writeln(f,S);
close(f)
End.
Bài 2:
[rml_read_more]
uses crt;
var i,u,j,z,n,k,m:longword;
a,b: array[0..50000]
of longword;
kq:qword;
procedure vao;
var f: text;
begin
clrscr;
assign(f,'d:\bai1.inp');
reset(f);
read(f,n);
close(f);
end;
function snt(u:longword): boolean;
begin
k:=0;
for i:=1 to u do if u mod i =0 then inc(k);
if k=2 then snt:=true else snt:=false;
end;
procedure demsnt;
begin
for i:=1 to n do
if snt(i)=true then
begin
inc(z);
a[z]
:=i;
end;
end;
procedure phantich;
begin
for i:=1 to z do
for j:=1 to n do
if j mod a[i]
= 0 then
begin
m:=j;
k:=0;
repeat
m:=m div a[i]
;
inc(k);
until m mod a[i]
<>0;
b[i] :=b[i]
+k;
end;
end;
procedure xuli;
begin
for i:=1 to z do
if b[i] mod 2 = 1 then b[i] :=b[i]
-1;
end;
procedure ghi;
var f1:text;
begin
assign(f1,'D:\ketqua.out');
rewrite(f1);
kq:=1;
for i:=1 to z do
for j:=1 to b[i] do kq:=kq*a[i]
mod 1000000007;
write(f1,kq);
close(f1);
end;
begin
vao;
demsnt;
phantich;
xuli;
ghi;
end.
Bài 3
const
fi='d:\cay1.inp';
fo='d:\cay1.out';
var
f:text;
k,sum,p:extended;
d,max,n,i,j,vt: longword;
a: array[1..1000000]
of extended;
procedure readfile;
begin
assign(f,fi);
reset(f);
read(f,n);
readln(f,k);
for i:=1 to n do read(f,a[i]
);
close(f);
end;
procedure solve;
begin
for i:=1 to n do
begin
j:=i;
sum:=0;
d:=0;
p:=0;
repeat
sum:=sum+a[j]
;
inc(j);
inc(d);
p:=sum / d;
until (p=k)or (j>n);
if (d>max)and(p=k)then
begin
max:=d;
vt:=i;
end;
end;
end;
procedure outfile;
begin
assign(f,fo);
rewrite(f);
if (max=0) and (vt=0) then write(f,0)
else write(f,max,' ',vt);
close(f);
end;
begin
readfile;
solve;
outfile;
end.
