Menu

Tin học Đề Khảo sát môn chuyên 2011-2012

Discussion in 'Đề thi HSG' started by ♥ Ngơ ♥, Mar 12, 2012.

Share This Page

  1. ♥ Ngơ ♥

    ♥ Ngơ ♥ Cùi bắp nhất forun

    • Messages: 430
    • Likes Received: 0
    [TABLE]
    [TR]
    [TD]TRƯỜNG THPT CHUYÊN HẠ LONG
    [/TD]
    [TD]ĐỀ KIỂM TRA CHẤT LƯỢNG MÔN CHUYÊN
    [/TD]
    [/TR]
    [TR]
    [TD]
    [/TD]
    [TD]LỚP 10 THPT NĂM HỌC 2011-2012
    [/TD]
    [/TR]
    [/TABLE]

    [TABLE="width: 649, align: center"]
    [TR]
    [TD]
    [/TD]
    [TD]Môn: Tin Học
    Thời gian: 180 phút (không kể thời gian giao đề)
    [/TD]
    [TD]Họ tên, chữ ký
    của giám thị số 1:
    [/TD]
    [/TR]
    [TR]
    [TD]
    [/TD]
    [TD]Ngày thi: 10/03/2012
    [/TD]
    [TD].........................................
    .........................................
    [/TD]
    [/TR]
    [TR]
    [TD]
    [/TD]
    [TD][/TD]
    [/TR]
    [TR]
    [TD]
    [/TD]
    [TD]
    [/TD]
    [/TR]
    [/TABLE]

    TỔNG QUAN VỀ BÀI THI
    [TABLE="align: center"]
    [TR]
    [TD]Tên bài
    [/TD]
    [TD]File chương trình
    [/TD]
    [TD]File vào
    [/TD]
    [TD]File ra
    [/TD]
    [TD]Giới hạn thời gian
    [/TD]
    [/TR]
    [TR]
    [TD]Bài 1
    [/TD]
    [TD]pave.pas
    [/TD]
    [TD]pave.in
    [/TD]
    [TD]pave.out
    [/TD]
    [TD]1 giây / 1 test
    [/TD]
    [/TR]
    [TR]
    [TD]Bài 2
    [/TD]
    [TD]weiter.pas
    [/TD]
    [TD]weiter.in
    [/TD]
    [TD]weiter.out
    [/TD]
    [TD]1 giây / 1 test
    [/TD]
    [/TR]
    [TR]
    [TD]Bài 3
    [/TD]
    [TD]standing.pas
    [/TD]
    [TD]standing.in
    [/TD]
    [TD]standing.out
    [/TD]
    [TD]1 giây / 1 test
    [/TD]
    [/TR]
    [TR]
    [TD]Bài 4
    [/TD]
    [TD]gps.pas
    [/TD]
    [TD]gps.in
    [/TD]
    [TD]gps.out
    [/TD]
    [TD]1 giây / 1 test
    [/TD]
    [/TR]
    [/TABLE]


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

    Bài 1. Lát sàn
    [​IMG]Ivica định lát phòng ngủ hình chữ nhật của mình bằng gạch men màu nâu, nhưng hàng gạch chạy sát chân tường là màu đỏ. Các chiều dài và rộng của phòng có kích thước nguyên. Gạch men có hình vuông kích thước 1×1. Sau khi đo đạc, tính toán Ivica mua về a viên màu đỏ và b viên màu nâu. Khi làm hợp đồng lát nền, cần phải điền vào mục kích thước phòng, Ivica phát hiện ra mình đã để quên bản ghi kích thước ở nơi mua gạch, trong túi chỉ còn hóa đơn cho biết các số ab. Không muốn quay lại tìm bản vẽ, Ivica ngồi tính lại kích thước phòng.

    Cho ab (8 ≤ a ≤ 4×10[SUP]9[/SUP], 1 ≤ b ≤ 10[SUP]18[/SUP]). Hãy tính chiều dài d và chiều rộng w của phòng (dw). Dữ liệu vào đảm bảo có lời giải.

    Dữ liệu: File vào gồm một dòng chứa 2 số nguyên ab.

    Kết quả: Đưa ra file ra trên một dòng 2 số nguyên dw .

    Ví dụ:
    [TABLE="align: center"]
    [TR]
    [TD]pave.in
    [/TD]
    [TD]pave.out
    [/TD]
    [/TR]
    [TR]
    [TD]8 1
    [/TD]
    [TD]3 3
    [/TD]
    [/TR]
    [TR]
    [TD]10 2
    [/TD]
    [TD]4 3
    [/TD]
    [/TR]
    [TR]
    [TD]24 24
    [/TD]
    [TD]8 6
    [/TD]
    [/TR]
    [/TABLE]



    Bài 2. Cân và chữ cái
    Jimmy có một bộ các chiếc cân đặc biệt: Nếu đặt 1 khối lập phương lên đĩa, sẽ có chữ ‘a’ hiện lên mặt cân, nếu đặt 2 khối – hiện lên chữ ‘b’, ..., đặt 26 khối – hiện lên chữ ‘z’. Đặt quá 26 khối cân sẽ bị gãy.

    Chơi một thời gian Jimmy làm gãy mấy cái cân, các khối lập phương cũng bị thất lạc một số. Bây giờ Jimmy chỉ còn n chiếc cân. Jimmy muốn đặt chúng thành một dãy và cho hiện từ s nhưng băn khoăn, không biết bây giờ còn làm được không.

    Cho n (1 ≤ n ≤ 100) và từ s chỉ bao gồm các chữ cái la tinh thường, độ dài không quá 100. Hãy xác định xem có thể hiển thị từ s được hay không. Nếu được, hãy tính số khối lập phương cần thiết, nếu không được – đưa ra thông báo “Impossible”.

    Dữ liệu: Dòng đầu tiên của file vào chứa số nguyên n. Dòng thứ hai chứa từ s.

    Kết quả: Đưa ra file ra số khối lập phương cần thiết hoặc thông báo “Impossible”.

    Ví dụ:
    [TABLE="align: center"]
    [TR]
    [TD]weiter.in
    [/TD]
    [TD]weiter.out
    [/TD]
    [/TR]
    [TR]
    [TD]20
    impossible
    [/TD]
    [TD]119
    [/TD]
    [/TR]
    [TR]
    [TD]5
    impossible
    [/TD]
    [TD]Impossible
    [/TD]
    [/TR]
    [/TABLE]



    Bài 3. Kết quả đẹp
    Steve hào hứng theo dõi kết quả tất cả các kỳ thi lập trình. Với Steve, bảng công bố kết quả online cũng hấp dẫn không kém nội dung các bài thi.

    Steve coi một bảng kết quả là đẹp nếu số bài giải được của mỗi đội được sắp xếp theo thứ tự giảm dần và số bài giải được của mỗi đội hoặc bằng 0 hoặc là ước của tổng số bài trong kỳ thi. Khi một đội giải được thêm một bài nào đó thì số lượng tương ứng trên bảng sẽ tăng thêm một. Không có đội nào tại một thời điểm đồng thời giải xong quá một bài, hệ thống cũng không ghi nhận đồng thời kết quả của hai hay nhiều đội.

    Hiện thời bảng đang có trạng thái đẹp. Ví dụ, với số đội tham gia là 7, có 12 bài trong kỳ thi và kết quả hiện tại là (12, 6, 4, 3, 3, 1, 0). Nếu đội ở vị trí thứ 4 giải thêm một bài thì bảng kết quả sẽ là (12, 6, 4, 4, 3, 1, 0) vẫn là bảng đẹp. Tiếp theo đội thứ 5 giải thêm một bài bảng vẫn đẹp: (12, 6, 4, 4, 4, 1, 0). Tương tự như vậy, đội thứ 6 có thể giải thêm 1, 2 hoặc 3 bài, còn đội đang đứng cuối có thể giải thêm được 1, 2, 3, 4 bài - bảng vẫn đẹp. Tóm lại có 9 trường hợp có bài được giải thêm mà bảng vẫn ở trạng thái đẹp.

    Cho n, m là số đội tham gia và số bài phải giải (1 ≤ n ≤ 100, 1 ≤ m ≤ 10[SUP]9[/SUP]) và cho kết quả số bài giải được của mỗi đội theo thứ tự giảm dần tạo thành một bảng đẹp. Hãy xác định số lần thay đổi trạng thái liên tiếp tối đa mà bảng kết quả vẫn đẹp.

    Dữ liệu: Dòng đầu tiên chứa 2 số nguyên nm. Dòng thứ hai chứa n số nguyên là số bài giải được của mỗi đội.

    Kết quả: Đưa ra file ra một số nguyên là số bảng đẹp liên tiếp có thể xuất hiện.

    Ví dụ:
    [TABLE="align: center"]
    [TR]
    [TD]standing.in
    [/TD]
    [TD]standing.out
    [/TD]
    [/TR]
    [TR]
    [TD]7 12
    12 6 4 3 3 1 0
    [/TD]
    [TD]9
    [/TD]
    [/TR]
    [/TABLE]



    Bài 4. GPS Text Entry
    Vào ngày sinh nhật, Sandy nhận được món quà là một thiết bị hệ thống định vị toàn cầu (GPS). Đó là một thiết bị điện tử mà cô ta có thể sử dụng để đánh dấu đường đi của mình. Dọc theo đường đi, Sandy có thể đánh dấu các vị trí mà chúng có thể tạo ra một bản đồ khi cô đi về nhà. Mỗi mô tả của một vị trí có thể được đưa vào thiết bị GPS, tuy nhiên thiết bị này không có bàn phím nhưng nó có 4 nút điều khiển con trỏ: lên trên, xuống dưới, sang trái, sang phải và nút “accept” chấp nhận chữ cái như hình sau:

    [TABLE="align: center"]
    [TR]
    [TD]
    [/TD]
    [TD]_
    [/TD]
    [TD]
    [/TD]
    [/TR]
    [TR]
    [TD]¬
    [/TD]
    [TD]accept
    [/TD]
    [TD]®
    [/TD]
    [/TR]
    [TR]
    [TD]
    [/TD]
    [TD]¯
    [/TD]
    [TD]
    [/TD]
    [/TR]
    [/TABLE]


    Màn hình thiết bị hiển thị lưới các ký tự và ký hiệu mà có thể dùng để “gõ ra” nó. Sơ đồ của lưới như sau:

    [TABLE="align: center"]
    [TR]
    [TD]A
    [/TD]
    [TD]B
    [/TD]
    [TD]C
    [/TD]
    [TD]D
    [/TD]
    [TD]E
    [/TD]
    [TD]F
    [/TD]
    [/TR]
    [TR]
    [TD]G
    [/TD]
    [TD]H
    [/TD]
    [TD]I
    [/TD]
    [TD]J
    [/TD]
    [TD]K
    [/TD]
    [TD]L
    [/TD]
    [/TR]
    [TR]
    [TD]M
    [/TD]
    [TD]N
    [/TD]
    [TD]O
    [/TD]
    [TD]P
    [/TD]
    [TD]Q
    [/TD]
    [TD]R
    [/TD]
    [/TR]
    [TR]
    [TD]S
    [/TD]
    [TD]T
    [/TD]
    [TD]U
    [/TD]
    [TD]V
    [/TD]
    [TD]W
    [/TD]
    [TD]X
    [/TD]
    [/TR]
    [TR]
    [TD]Y
    [/TD]
    [TD]Z
    [/TD]
    [TD]space
    [/TD]
    [TD]-
    [/TD]
    [TD].
    [/TD]
    [TD]enter
    [/TD]
    [/TR]
    [/TABLE]


    Khi bắt đầu vào tên của các vị trí, con trỏ ở tại A. Bạn phải di chuyển con trỏ sang vị trí của chữ cái hoặc ký hiệu tiếp theo và sau đó chấp nhận ký tự này. Con trỏ chỉ có thể di chuyển tới các ô vuông láng giềng theo chiều ngang hoặc chiều đứng (không theo đường chéo). Một khi bạn đã vào tất cả các ký tự của bản mô tả, bạn cần di chuyển con trỏ tới “enter” để kết thúc việc vào bản mô tả đó.

    Bạn hãy viết một chương trình tính số bước di chuyển con trỏ ít nhất để “gõ vào” bản mô tả. Ví dụ, để vào từ GPS, bắt đầu từ vị trí “A”, bạn di chuyển xuống dưới 1 và chọn “G”, tiếp theo di chuyển sang phải 3 và xuống dưới 1 để chọn “P”, sau đó di chuyển xuống dưới 1 và sang trái 3 để chọn “S” và cuối cùng xuống dưới 1 và sang phải 5 để chọn “enter”. Tổng cộng là 15 bước di chuyển con trỏ, và là cách có số bước di chuyển con trỏ ít nhất. Chú ý rằng bạn không được di chuyển ra ngoài lưới.

    Dữ liệu: File vào gồm một dòng chứa một xâu không quá 40 ký tự. Các ký tự trong xâu là xuất hiện trong lưới.

    Kết quả: Ghi ra file ra tổng số các bước di chuyển con trỏ ít nhất để nhập xâu trong file vào, vào thiết bị GPS, sử dụng lưới các ký tự này.

    Ví dụ:
    [TABLE="align: center"]
    [TR]
    [TD]gps.in
    [/TD]
    [TD]gps.out
    [/TD]
    [/TR]
    [TR]
    [TD]GPS
    [/TD]
    [TD]15
    [/TD]
    [/TR]
    [TR]
    [TD]A BB-C.
    [/TD]
    [TD]29
    [/TD]
    [/TR]
    [/TABLE]


    ----------------------------- Hết -----------------------------
     
  2. ♥ Ngơ ♥

    ♥ Ngơ ♥ Cùi bắp nhất forun

    • Messages: 430
    • Likes Received: 0
    Có 5 bạn đạt điểm 20 : Lê Anh Đức, Lê Trần Bảo Cương, Đào Duy Thắng, Lê Trung Kiên, Nguyễn Hoàng Kỳ. Thầy Thái sẽ xem chương trình và chọn ra 1 nhất 2 nhì 2 ba :) Mình xịt là cái chắc =.=" k biết có vụ xếp giải này nên trong bài làm có mấy cái lung tung quên k xóa đi híc
     
  3. Ông Già

    Ông Già Administrator

    • Messages: 1,057
    • Likes Received: 0
  4. ♥ Ngơ ♥

    ♥ Ngơ ♥ Cùi bắp nhất forun

    • Messages: 430
    • Likes Received: 0
    Mình xin post lời giải của các bài tập trên, đây là code của mình nên có thể có sai sót:

    Bài 1:

    Code:
    Program pave;
    Const
      fi= 'pave.in';
      fo= 'pave.out';
    Var
      a, b: int64;
      d, w: extended;
     
    PROCEDURE init;
    Var
      f: text;
    Begin
      assign(f,fi); reset(f);
      read(f,a,b);
      close(f);
    End;
     
    PROCEDURE process;
    Var
      s: extended;
      p: int64;
    Begin
      s:= (a+4)/2;
      p:= a+b;
      d:= (s+ sqrt(sqr(s)-4*p))/2;
      w:= (s- sqrt(sqr(s)-4*p))/2;
    End;
     
    PROCEDURE result;
    Var
      f: text;
    Begin
      assign(f,fo); rewrite(f);
      writeln(f,d:0:0,' ',w:0:0);
      close(f);
    End;
     
    BEGIN
      init;
      process;
      result;
    END.
    
    Bài 2:
    Code:
    Program weiter;
    Const
      fi= 'weiter.in';
      fo= 'weiter.out';
    Var
      n, sl: int64;
      s: string;
      ok: boolean;
     
    PROCEDURE init;
    Var
      f: text;
    Begin
      assign(f,fi); reset(f);
      readln(f,n);
      readln(f,s);
      close(f);
    End;
     
    PROCEDURE process;
    Var
      i, l: integer;
    Begin
      ok:= true;
      sl:= 0;
      l:= length(s);
      if l>n then
        begin
          ok:= false;
          exit;
        end;
      for i:= 1 to l do
        sl:= sl+ ord(s[i])- 96;
    End;
     
    PROCEDURE result;
    Var
      f: text;
    Begin
      assign(f,fo); rewrite(f);
      if ok= false then
        begin
          writeln(f,'Impossible');
          close(f);
          exit;
        end
      else writeln(f,sl);
      close(f);
    End;
     
    BEGIN
      init;
      process;
      result;
    END.
    
    Bài 3:

    Code:
    Program standing;
    Const
      fi= 'standing.in';
      fo= 'standing.out';
    Type
      arr= array[1..100] of longint;
    Var
      n, m, t: longint;
      a: arr;
     
    PROCEDURE init;
    Var
      f: text;
      i: integer;
    Begin
      assign(f,fi); reset(f);
      read(f,n,m);
      for i:= 1 to n do read(f,a[i]);
      close(f);
    End;
     
    FUNCTION ktra(b: arr): boolean;
    Var
      i: integer;
    Begin
      for i:= 1 to n do
        if (b[i]<>0) and (m mod b[i] <>0) then exit(false);
      exit(true);
    End;
     
    PROCEDURE process;
    Var
      b: arr;
      i: longint;
      ok: boolean;
    Begin
      t:= 0;
      for i:= 1 to n do
        begin
          b:= a;
          ok:= true;
          while (ok) and (b[i]<m) do
            begin
             inc(b[i]);
             if ktra(b) then inc(t)
               else ok:= false;
            end;
        end;
    End;
     
    PROCEDURE result;
    Var
      f: text;
    Begin
      assign(f,fo); rewrite(f);
      writeln(f,t);
      close(f);
    End;
     
    BEGIN
      init;
      process;
      result;
    END.
    
    Bài 4:

    Code:
    Program gps;
    Const
      fi= 'gps.in';
      fo= 'gps.out';
      hang: array['A'..'^'] of integer= (1,1,1,1,1,1,2,2,2,2,2,2,3,3,3,3,3,3,4,4,4,4,4,4,5,5,5,5,5,5);
      cot: array['A'..'^'] of integer=  (1,2,3,4,5,6,1,2,3,4,5,6,1,2,3,4,5,6,1,2,3,4,5,6,1,2,3,4,5,6);
    Var
      s: string;
      kq: longint;
     
    PROCEDURE init;
    Var
      f: text;
      i: integer;
    Begin
      assign(f,fi); reset(f);
      readln(f,s);
      for i:= 1 to length(s) do
        if s[i]= ' ' then s[i]:= '['
        else if s[i]= '-' then s[i]:= '\'
             else if s[i]= '.' then s[i]:= ']';
      s:= 'A'+ s;
      close(f);
    End;
     
    PROCEDURE process;
    Var
      i, l: integer;
    Begin
      l:= length(s);
      kq:= 0;
      for i:= 2 to l do
        kq:= kq+ abs(hang[s[i]]- hang[s[i-1]])+ abs(cot[s[i]]- cot[s[i-1]]);
      kq:= kq+ abs(hang['^']- hang[s[l]])+ abs(cot['^']- cot[s[l]]);
    End;
     
    PROCEDURE result;
    Var
      f: text;
    Begin
      assign(f,fo); rewrite(f);
      writeln(f,kq);
      close(f);
    End;
     
    BEGIN
      init;
      process;
      result;
    END.