Đề thi HSG Tin 11 Tỉnh Thanh Hóa – Năm học 2017 – 2018 – Có Code tham khảo

Đề thi HSG Tin 11 Tỉnh Thanh Hóa – Năm học 2017 – 2018 – Có Code tham khảo

Tổng quan bài thi:


Dữ liệu vào là đúng đắn, không cần phải kiểm tra. Trong các file dữ liệu vào, nếu dữ liệu trên cùng một dòng thì được cách nhau bởi ít nhất 1 dấu cách. Dấu (*) trong tên file chương trình biểu thị đuôi file tùy thuộc vào NNLT sử dụng (‘pas’ đối với NNLT PASCAL, ‘c’ đối với NNLT C,…).

Bài 1(5 điểm):Hệ đếm

Lần đầu tiên tiếp xúc với các vấn đề cơ sở Tin học, Mạnh ngỡ ngàng và thú vị khi được làm quen với hệ đếm cơ số 2 (Hệ đếm nhị phân). Mạnh nghĩ ra một xâu kí tự chỉ bao gồm các kí tự ‘0’ và ‘1’ biểu diễn một số tự nhiên N trong hệ đếm cơ số 2 và đố Hải tìm biểu diễn của N trong hệ đếm cơ số 10 (Hệ đếm thập phân).

Ví dụ: Mạnh nghĩ ra xâu ‘00010101’ là biểu diễn của số tự nhiên 15 trong hệ đếm cơ số 2.

Yêu cầu: Hãy giúp Hải chuyển xâu kí tự biểu diễn số tự nhiên N trong hệ đếm cơ số 2 thành xâu biểu diễn N trong hệ đếm cơ số 10.

Dữ liệu vào: Từ tệp văn bản BAI1.INP gồm một dòng duy nhất chứa xâu S có độ dài không quá 32 ký tự.

Dữ liệu ra: Ghi ra tệp văn bản BAI1.OUT xâu biểu diễn của N trong hệ đếm cơ số 10.

Ví dụ:

BAI1.INP BAI1.OUT
10101110 174
Read:   Lập trình Scratch đếm các số tự nhiên thỏa mãn điều kiện

Bài 2 (5 điểm):Tìm số nguyên tố

– Tìm tất cả các số P lớn hơn M và nhỏ hơn N thỏa mãn các điều kiện sau:

+ Là số nguyên tố.

+ Tổng các chữ số của P phải chia hết cho k.

Dữ liệu vào: Từ tệp văn bản BAI2.INP: Gồm 3 số M, N, k (1 ≤ M,N,k ≤ 106) (các số cách nhau ít nhất một dấu cách).

Dữ liệu ra: Ghi ra tệp văn bản BAI2.OUT gồm duy nhất 1 số là số lượng các số thỏa mãn yêu cầu đầu bài.

Ví dụ:

BAI2.INP BAI2.OUT BAI2.INP BAI2.OUT
2 35 2 6 1 10 11 0

Bài 3(4 Điểm): Taxi

Trong dịp nghỉ hè các bạn học sinh lớp 12 dự định tổ chức dã ngoại đến biển Sầm Sơn và sẽ đi bằng taxi. Các bạn được chia thành n nhóm, nhóm thứ i gồm Si bạn (1 ≤ Si ≤ 4) và mỗi chiếc taxi chở tối đa 4 hành khách. Vậy lớp 12 cần thuê ít nhất bao nhiêu chiếc taxi để chở các nhóm đi, với điều kiện là các bạn trong nhóm phải ngồi chung taxi (một taxi có thể chở một nhóm trở lên).

Dữ liệu vào: Từ tệp văn bản BAI3.INP gồm:

– Dòng đầu chứa số nguyên n (1 ≤ n ≤ 105(số lượng các nhóm học sinh)

– Dòng số 2 chứa dãy số nguyên S1, S2, …, Sn (1 ≤ Si ≤ 4). Các số nguyên cách nhau bởi dấu cách với Si là số học sinh trong nhóm thứ i.

Dữ liệu ra: Ghi ra tệp văn bản BAI3.OUT là 1 số nguyên duy nhất là số lượng tối thiểu xe taxi cần thiết để chở tất cả học sinh đến nơi.

Ví dụ:

BAI3.INP BAI3.OUT
5

1 2 4 3 3

4

Bài 4 (3 điểm):Hamming

Dãy số nguyên dương tăng dần, trong đó ước nguyên tố của mỗi số không quá 5 được gọi là dãy Hamming.

Như vậy, 10 = 2×5 sẽ là một số trong dãy Hamming, còn 26 = 2×13  không thuộc dãy Hamming.

Phần đầu của dãy Hamming là 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, . . .

Yêu cầu: Cho số nguyên x (1 ≤ x ≤ 109). Hãy xác định số thứ tự của x trong dãy Hamming.

Dữ liệu vào: Từ tệp văn bản BAI4.INP:

– Dòng đầu tiên chứa số nguyên t – số lượng tests (1 ≤ t ≤ 105),

– Các dòng tiếp theo mỗi dòng chứa một số nguyên x.

Dữ liệu ra: Ghi ra tệp văn bản BAI4.OUT: kết quả mỗi test đưa ra trên một dòng dưới dạng số nguyên hoặc thông báo (-1) nếu không tồn tại số đó trong dãy Hamming.

Ví dụ:

Bài 5 (3 điểm): Số lớn nhất

Cho 2 số nguyên dương X=X1X2…Xn và Y= Y1Y2…Ym (M,N≤200). Hãy tìm số Z=Z1Z2…Zk lớn nhất (Z nhận được từ X và Y bằng cách xoá đi một số chữ số).

Ví dụ: X= 12345     Y= 435012

Thì Z=45 (nhận được từ X bằng cách xoá đi X1,X2,X3; nhận được từ Y bằng cách xoá đi Y2 ­, Y4 , Y5 , Y6)

Dữ liệu vào: Từ tệp văn bản BAI5.INP gồm:

– Dòng thứ nhất là X.

– Dòng thứ hai là Y.

Dữ liệu ra: Ghi ra tệp văn bản BAI5.OUT 1 số Z là kết quả của bài toán.

Ví dụ:

BAI5.INP BAI5.OUT BAI5.INP BAI5.OUT
42572

39258

25 12345

4351023

123

Trong đó: có 1/6 số test chỉ tồn tại số Z mà các chữ số của nó trong X và Y là liên tiếp nhau.

—————————– Hết —————————–

Code tham khảo Đề thi HSG Tin 11 Tỉnh Thanh Hóa – Năm học 2017 – 2018

Bài 1 (pascal)

[rml_read_more]



































Program Bai1;
Var f1,f2:Text;
    he10,n:int64;
    i,j:Longint;
    M:Array[1..200000000] 














 of Longint;
    S:Ansistring;
Function luythua(m,x:Longint):int64;
Var k:int64; i:longint;
begin
k:=1;
for i:=1 to m do k:=k*x;
luythua:=k;
end;
BEGIN
   Assign(f1,'BAI1.INP'); Reset(f1);
   Assign(f2,'BAI1.OUT'); Rewrite(f2);
   Read(f1,S);
   n:=length(S);
   For i:=1 to Length(S) do
       if (S[i] ='1') or (S[i] ='0') then  Val(S[i] ,m[i] 



);
   He10:=0;
   for i:=1 to n do
   begin
      he10:=he10+Luythua(n-1,2)*m[i] 





;
      dec(n);
   end;
   writeln(f2,He10);
Close(f1);
Close(f2);
END.

Bài 2















































const fi='Bai2.inp';
      fo='bai2.out';
var n,m,k:longint;
procedure readfile;
var f:text;
begin
      assign(f,fi);
      reset(f);
      read(f,m,n,k);
      close(f);
end;
function nt(a:longint):boolean;
var i:longint;
begin
    if a=1 then exit(false);
    if a<4 then exit(true)
    else
     for i:=2 to trunc(sqrt(a)) do
      if a mod i = 0 then exit(false);
    exit(true);
end;
function chia(a:longint):boolean;
var sum:longint;
begin
    sum:=0;
    while a<>0 do
     begin
      sum:=sum+a mod 10;
      a:=a div 10;
     end;
    if sum mod k = 0 then exit(true)
    else exit(false);
end;
procedure process;
var p,i:longint; f:text;
begin
   p:=0;
   for i:=m to n do
    if chia(i) and nt(i) then inc(p);
   assign(f,fo);
   rewrite(f);
   write(f,p);
   close(f);
end;
BEGIN
     readfile;
     process;
END.

Bài 3






















var fi,fo: text;
    n,i,d:longint;
    a:array[0..5] 







 of longint;
begin
        assign(fi,'bai3.inp'); reset(fi);
        assign(fo,'bai3.out'); rewrite(fo);
        readln(fi,n);
        for i:=1 to n do
        begin
                read(fi,d);
                inc(a[d] 

);
        end;
        if a[3] <a[1] 
 then
           dec(a[1] ,a[3] 

)
        else
           a[1] 
:=0;
        inc(a[1] ,a[2] 
*2);
        Write(fo,a[4] +a[3] +((a[1] 

+3) div 4));
        close(fi); close(fo);
end.

Bài 4
































































































Program Bai4;
Const fi='Bai4.inp';
      fo='Bai4.out';
      max=1000000000;
Var A:Array[1..100000] 

 of Longint;
    n,k:Longint;
    dem:Array[1..1530] 
 of Longint;
    B:Array[1..max] 







 of Boolean;
Procedure readfile;
Var f:text;
    i:longint;
Begin
     Assign(f,fi);
     Reset(f);
     Readln(f,n);
     for i:=1 to n do readln(f,A[i] 







);
     close(f);
end;
Procedure Quicksort(l,r:Longint);
Var i,j,k,tg:Longint;
Begin
   i:=l;
   j:=r;
   k:=dem[(l+r) div 2] 

;
   Repeat
      while dem[i] 
<k do inc(i);
      while k<dem[j] 


 do dec(j);
         if i<=j then
            begin
               tg:=dem[i] 
;
               dem[i] :=dem[j] 
;
               dem[j] 



















:=tg;
               inc(i);
               dec(j);
            end;
   Until i>j;
   if l<j then Quicksort(l,j);
   if i<r then Quicksort(i,r);
end;
Procedure hammingtest;
Var i,j,z:Longint;
    hm: real;
Begin
   k:=1;
   for i:=0 to 30 do
       for j:=0 to 18 do
           for z:=0 to 13 do
              begin
                 hm:=exp(i*ln(2))*exp(j*ln(3))*exp(z*ln(5));
                 if (hm<=exp(9*ln(10))) then
                    begin
                       dem[k] 













:=trunc(hm);
                       inc(k);
                    end
                       else break;
              end;
end;
Function tknp(z:Longint):integer;
Var l,r,mid:integer;
Begin
    l:=1;
    r:=k;
    while l<=r do
      begin
         mid:=(l+r) div 2;
         if dem[mid] 

=z then exit(mid)
            else
                if dem[mid] 













<z then l:=mid+1
                  else r:=mid-1;
      end;
    exit(0);
end;
Procedure process;
Var  f:text; i,j:longint;x:integer;
Begin
    hammingtest;
    Quicksort(1,k-1);
    Assign(f,fo);
    Rewrite(f);
    for i:=1 to n do
        begin
           x:=tknp(A[i] 









);
           if x<>0 then writeln(f,x)
             else writeln(f,-1);
        end;
    close(f);
end;

BEGIN
    readfile;
    process;
END.

Bài 5






































































const       max        =250;
            fi         ='bai5.inp';
            fo         ='bai5.out';

var         l          :array[1..max+1,1..max+1] 
























of byte;
            a,b,c      :string;

procedure docf;
var  f    :text;
 begin
    assign(f,fi);
    reset(f);
    readln(f,a);readln(f,b);
    close(f);
 end;

function maxso(x,y,z:byte):byte;
 begin
   if x<y then x:=y;
   if x<z then maxso:=z else maxso:=x;
 end;

procedure lam;
var i,j,k,x,y,m :integer;
    ch          :char;
 begin
   fillchar(l,sizeof(l),0);
   for i:=length(a) downto 1 do
    for j:=length(b) downto 1 do
     l[i,j] :=maxso(l[i+1,j] ,l[i,j+1] ,l[i+1,j+1] +ord(a[i] =b[j] 





));

   m:=0;c:='0';
   for ch:='9'downto '1' do
     begin
       i:=pos(ch,a);j:=pos(ch,b);
       if (i>0)and(j>0)and(l[i,j] >m) then begin c:=ch;m:=l[i,j] 






;end;
     end;
   i:=pos(c,a)+1;j:=pos(c,b)+1;
   for k:=m-1 downto 1 do
     for ch:='9'downto '0' do
       begin
          x:=i;y:=j;
          while (x<=length(a))and(a[x] 
<>ch) do inc(x);
          while (y<=length(b))and(b[y] 
<>ch) do inc(y);
          if l[x,y] 




















=k then
            begin
               c:=c+ch;i:=x+1;j:=y+1;
               break;
            end;
       end;
 end;

procedure ghif;
var f     :text;
 begin
    assign(f,fo);
    rewrite(f);
    write(f,c);
    close(f);
 end;

BEGIN
   docf;
   lam;
   ghif;
END.

 

Read:   Ngắm vẻ đẹp tuyệt vời của đề thi HSG Toán soạn bằng Latex
Hình đại diện của người dùng

admin

Trả lời

Email của bạn sẽ không được hiển thị công khai. Các trường bắt buộc được đánh dấu *