Tin lớp 9

Thứ bảy - 24/04/2021 03:13

KÌ THI CHỌN HỌC SINH GIỎI HUYỆN LỚP 9
NĂM HỌC 2020 - 2021
Môn thi: TIN HỌC
Thời gian: 150 phút (không kể thời gian giao đề)

Tổng quan bài thi

Tên bài	File nguồn	File Input	File Output	Thời gian
GIAI THỪA	GIAITHUA.*	GIAITHUA.Inp	GIAITHUA.Out	1 giây
FIBONACI	FIBO.*	FIBO.Inp	FIBO.Out	1 giây
XẾP TÁO	XEPTAO.*	XEPTAO.Inp	XEPTAO.Out	1 giây
ĐỔI CHỖ CHỮ SỐ	CHUSO.*	CHUSO T.Inp	CHUSO.Out	1 giây

Phần mở rộng .* được thay thế bằng Pas, Cpp, Py ứng với các ngôn ngữ lập trình Pascal, C++, Python.

Hãy lập trình giải các bài toán sau:

CÂU 1 (5 điểm): GIAI THỪA
Cho trước số nguyên dương n (n<10⁹). Hãy cho biết trong kết quả n! (n giai thừa) có bao nhiêu chữ số 0 tận cùng?

Dữ liệu vào: File văn bản giaithua.inp chỉ bao gồm một số nguyên dương n
Dữ liệu ra: Được ghi ra file văn bản giaithua.out chỉ bao gồm một số là kết quả tìm được

Ví dụ:

Giaithua.inp		Giaithua.out
16780		4193

CÂU 2 (5 điểm): FIBONACI
Dãy Fibonacci là dãy số thỏa mãn: F[1] = 1; F[2] = 1; F[i] = F[i-1]+F[i-2] với mọi số tự nhiên i > 2.
Cho trước số nguyên dương n (n<10⁹). Hãy phân tích n thành tổng ít nhất các số fibonacci không trùng nhau?

Dữ liệu vào: File văn bản fibo.inp chỉ bao gồm một số nguyên dương n
Dữ liệu ra: Được ghi ra file văn bản fibo.out là dãy fibonacci được sắp theo thứ tự giảm thoả mãn yêu cầu đề bài

Ví dụ:

Fibo.inp		Fibo.out
1750		1597 144 8 1

CÂU 3 (6 điểm): XẾP TÁO
Siêu thị Mường Thanh Diễn Châu đang bày bán rất nhiều loại hoa quả, trong đó có n quả cam và n quả táo được xếp thành một dãy rất dài. Trong quá trình xếp, các nhân viên đã vô ý xếp những quả cam và những quả táo không theo một thứ tự nhất định. Quản lý siêu thị yêu cầu các nhân viên phải xếp lại sao cho chúng được xếp xen kẽ nhau, cứ một quả cam rồi lại đến một quả táo và ngược lại.
Các hành động lấy một quả cam hoặc quả táo ra khỏi dãy, dồn những quả bên trái hoặc bên phải về chỗ trống vừa lấy và chèn quả vừa lấy vào vị trí thích hợp được xem là một thao tác.
Yêu cầu: Bạn hãy giúp người quản lý siêu thị tính xem cần ít nhất bao nhiêu thao tác để xếp lại dãy quả cam và quả táo.
Dữ liệu vào: Từ tệp văn bản XEPTAO.INP gồm:

Dòng đầu ghi số nguyên dương n (n ≤ 10⁶).
Dòng thứ hai ghi 2.nsố 0 và 1, trong đó những số 0 biểu thị cho vị trí các quả cam còn những số 1 biểu thị cho vị trí các quả táo.

Kết quả: Ghi ra tệp văn bản XEPTAO.OUT một số nguyên duy nhất là số thao tác ít nhất cần thực hiện để xếp lại dãy quả cam và quả táo theo đúng yêu cầu bài toán.
Ví dụ:

XEPTAO.INP	XEPTAO.OUT
3 100011	2

CÂU 4 (4 điểm): ĐỔI CHỖ CHỮ SỐ
Cho hai số nguyên dương K và S. Nhiệm vụ của các em đưa ra số lớn nhất bằng cách thực hiện nhiều nhất K lần đổi chỗ chữ số của số S.
Ví dụ k=3 và s=1234567 ta đươc 7654321
Dữ liệu vào: Từ tệp văn bản CHUSO.INP gồm:

Dòng đầu ghi số nguyên dương K (0<k<=10).

- Dòng thứ 2 ghi số dương S
Kết quả: Ghi ra tệp văn bản CHUSO.OUT một số nguyên duy nhất là ra số lớn nhất bằng cách thực hiện nhiều nhất K lần đổi chỗ chữ số của số S.

---------------------------HẾT---------------------------
(Lưu ý: đề thi có 2 trang)
CODE
CÂU 1
program giaithua;
var n,tong:longint;
begin
    assign(input,'Giaithua.inp'); reset(input);
    assign(output,'Giaithua.out'); rewrite(output);
    read(n);
    tong:=0;
    while n>0 do
    begin
         tong:= tong + (n div 5);
         n:= n div 5;
    end;
    write(tong);
    close(input);
    close(output);
end.

CÂU 2
rogram fibo1;
var n,i:longint;
function timfibo(n:longint):longint;
var i,j,t:longint;
begin
  if n< 4 then exit(n);
i:=1; j:=2;
while i+j<n do
begin
    t:= j;
    j:= i+j;
    i:= t;
end;
exit(j);
end;
begin
assign(input,'Fibo.inp'); reset(input);
assign(output,'Fibo.out'); rewrite(output);
read(n);
while n>0 do
begin
    i:=timfibo(n);
    write(i,' ');
    n:=n-i;
end;
close(input);
close(output);
end.

CÂU 3
var f1,f2:text;
    a:array[1..2000001] of char;
    n,i,d0,d1:longint;
begin
assign(f1,'xeptao.inp');
reset(f1);
readln(f1,n);
n:=n*2;
for i:=1 to n do read(f1,a[i]);
close(f1);
d1:=0;
d0:=0;
for i:=1 to n-1 do
   if (a[i]='0')and(a[i+1]='0') then d0:=d0+1
    else if (a[i]='1')and(a[i+1]='1') then d1:=d1+1;
assign(f2,'xeptao.out');
rewrite(f2);
if d1>d0 then writeln(f2,d1) else writeln(f2,d0);
close(f2);
end.

CÂU 4
#include<bits/stdc++.h>
using namespace std;
int k,i,j;
string s;
int main()
{
    freopen("doichuso.inp","r",stdin);
    freopen("doichuso.out","w",stdout);
    cin>>k>>s;
    for(i=0;i<s.size(); i++)
    {
        char Max=s[s.size()-1];
        int vt=s.size()-1;
        for(j=s.size()-1;j>i&&k>0;j--)
        {
            if(Max<s[j])
            {
                Max=s[j];
                vt=j;
            }
            if(Max>s[i])
            {
                swap(s[i],s[vt]);
                k++;
            }
        }
    }
    cout<<s;

}