Menu

Tin học Đề kiểm tra đội tuyển tin 10 lần 2

Discussion in 'Đề thi HSG' started by ♥ Ngơ ♥, Feb 18, 2012.

Share This Page

  1. ♥ Ngơ ♥

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

    • Messages: 430
    • Likes Received: 0
    [TABLE="width: 659, align: center"]
    [TR]
    [TD]TRƯỜNG THPT CHUYÊN HẠ LONG[/TD]
    [TD]KIỂM TRA ĐỘI TUYỂN LẦN II[/TD]
    [TD][/TD]
    [/TR]
    [TR]
    [TD][/TD]
    [TD]NĂM HỌC 2011-2012[/TD]
    [TD][/TD]
    [/TR]
    [TR]
    [TD="colspan: 3"]Môn: Tin Học
    Thời gian: 150 phút (không kể thời gian giao đề)[/TD]
    [/TR]
    [TR]
    [TD="colspan: 3"]Ngày thi: 06/02/2012[/TD]
    [/TR]
    [TR]
    [TD="colspan: 3"][/TD]
    [/TR]
    [/TABLE]
    TỔNG QUAN VỀ BÀI THI
    [TABLE="width: 713, 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]
    [TD]Điểm[/TD]
    [/TR]
    [TR]
    [TD]Bài 1[/TD]
    [TD]parking.pas[/TD]
    [TD]parking.in[/TD]
    [TD]parking.out[/TD]
    [TD]1 giây / 1 test[/TD]
    [TD]6,0[/TD]
    [/TR]
    [TR]
    [TD]Bài 2[/TD]
    [TD]stamps.pas[/TD]
    [TD]stamps.in[/TD]
    [TD]stamps.out[/TD]
    [TD]1 giây / 1 test[/TD]
    [TD]7,0[/TD]
    [/TR]
    [TR]
    [TD]Bài 3[/TD]
    [TD]sumx.pas[/TD]
    [TD]sumx.in[/TD]
    [TD]sumx.out[/TD]
    [TD]1 giây / 1 test[/TD]
    [TD]7,0[/TD]
    [/TR]
    [/TABLE]

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

    Bài 1. Đỗ xe
    Ở thời đại khi ô tô bay phát triển, nạn kẹt xe giảm hẳn, nhưng lại xuất hiện những vấn đề mới. Bất chấp những quy định nghiêm ngặt nhất, nhiều người vẫn đỗ xe lung tung khắp nơi, kể cả trên thảm cỏ xanh được chăm sóc hết sức cẩn thận ở quảng trường trung tâm thành phố. Người ta phải dựng các chốt chống đỗ xe.
    Thảm cỏ có dạng hình chữ nhật kích thước m×n ô. Mỗi xe khi đỗ cần đúng một ô trống không có vật cản (kể cả ở trên biên). Việc xây dựng các chốt chống đỗ xe cũng khá tốn kém và nếu dựng quá nhiều cũng sẽ mất mỹ quan. Vì vậy người ta cố gắng dựng càng ít càng tốt. Ví dụ, với n = m = 2 thì chỉ cần dựng một chốt ở tâm là đủ.

    Cho m, n (1 ≤ m, n ≤ 1000). Hãy xác định số chốt ít nhất cần dựng.

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

    Kết quả: Đưa ra file ra số lượng chốt ít nhất cần dựng.

    Ví dụ:
    [TABLE="align: center"]
    [TR]
    [TD]parking.in[/TD]
    [TD]parking.out[/TD]
    [/TR]
    [TR]
    [TD]1 1[/TD]
    [TD]1[/TD]
    [/TR]
    [TR]
    [TD]2 2[/TD]
    [TD]1[/TD]
    [/TR]
    [/TABLE]


    Bài 2. Stamps
    Mọi người đều ghét Raymond. Anh ta là nhà sưu tầm tem lớn nhất trên thế giới và vì lẽ đó anh ta thường chế diễu tất cả các nhà sưu tầm tem khác. May thay, mọi người đều yêu Lucy và cô ta có một kế hoạch. Cô ấy bí mật hỏi bạn bè cho cô ấy mượn tem, để cô ấy có thể làm cho Raymond xấu hổ bằng cách chứng tỏ bộ sưu tầm tem của mình còn lớn hơn bộ sưu tầm tem của anh ta.

    Raymond rất tin tưởng vào sự tốt nhất của bộ tem của mình, cho nên anh ta luôn nói cho mọi người biết anh ta sẽ trưng bày bao nhiêu con tem. Lucy biết mình có bao nhiêu con tem và cô ta biết rằng mình cần bao nhiêu con tem nữa. Cô ấy cũng biết có bao nhiêu người bạn sẽ cho cô mượn tem và mỗi người sẽ cho mượn bao nhiêu. Nhưng cô ấy muốn mượn từ một số người bạn ít nhất có thể. Bạn hãy viết chương trình, tính giúp cô ấy cần mượn tem từ ít nhất bao nhiêu người bạn.

    Dữ liệu: Dòng đầu tiên của file vào chứa hai số nguyên sn ngăn cách nhau bởi một dấu cách, ở đó s là số con tem tối thiểu mà Lucy cần mượn ([​IMG]) và n là số người bạn sẽ cho Lucy mượn tem ([​IMG]). Dòng thứ hai chứa n số nguyên là số tem mà mỗi người bạn sẽ cho Lucy mượn (các số nằm trong phạm vi từ 1 đến 10.000).

    Kết quả: Ghi ra file ra một số duy nhất là số người bạn ít nhất mà Lucy cần mượn tem. Trong trường hợp Lucy không mượn được số tem tối thiểu mình cần thì ghi ra file ra dòng thông báo “impossible”.

    Ví dụ:
    [TABLE="align: center"]
    [TR]
    [TD]stamps.in[/TD]
    [TD]stamps.out[/TD]
    [/TR]
    [TR]
    [TD]100 6
    13 17 42 9 23 57[/TD]
    [TD]3[/TD]
    [/TR]
    [TR]
    [TD]99 6
    13 17 42 9 23 57[/TD]
    [TD]2[/TD]
    [/TR]
    [TR]
    [TD]1000 3
    314 159 265[/TD]
    [TD]impossible[/TD]
    [/TR]
    [/TABLE]


    Bài 3. Tổng cặp số
    Xét dãy gồm n số nguyên dương đôi một khác nhau a[SUB]1[/SUB], a[SUB]2[/SUB], …, a[SUB]n[/SUB]. Với số nguyên dương x cho trước, hãy xác định số cặp (a[SUB]i[/SUB], a[SUB]j[/SUB]) thỏa mãn các điều kiện:

    • a[SUB]i[/SUB] + a[SUB]j[/SUB] = x,
    • 1 ≤ i < jn.

    Dữ liệu: Dòng đầu tiên của file vào chứa 2 số nguyên n, x (2 ≤ n ≤ 10[SUP]5[/SUP], 1 ≤ x ≤ 2×10[SUP]5[/SUP]). Dòng thứ i trong số n dòng tiếp theo ghi một số nguyên dương a[SUB]i[/SUB] (a[SUB]i[/SUB] ≤ 10[SUP]6[/SUP]).

    Kết quả: Đưa ra file ra một số nguyên là số cặp tìm được.

    Ví dụ:
    [TABLE="align: center"]
    [TR]
    [TD]sumx.in[/TD]
    [TD]sumx.out[/TD]
    [/TR]
    [TR]
    [TD]9 13
    5
    12
    7
    10
    9
    1
    2
    3
    11[/TD]
    [TD]3[/TD]
    [/TR]
    [/TABLE]


    ----------------------------- Hết -----------------------------
     
    Last edited: Feb 18, 2012
  2. Nắng

    Nắng Moderator

    • Messages: 108
    • Likes Received: 0
    cái gì thế nhỉ