Menu

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

Discussion in 'Đề thi HSG' started by ♥ Ngơ ♥, Apr 11, 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 ĐỘI TUYỂN LẦN 3
    [/TD]
    [/TR]
    [TR]
    [TD]

    [/TD]
    [TD]LỚP 10 THPT NĂM HỌC 2011-2012
    [/TD]
    [/TR]
    [/TABLE]

    [TABLE="width: 650, 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]

    [/TD]
    [/TR]
    [TR]
    [TD]

    [/TD]
    [TD]Ngày thi: 23/03/2012
    [/TD]
    [TD]

    [/TD]
    [/TR]
    [TR]
    [TD]

    [/TD]
    [TD]

    [/TD]
    [/TR]
    [/TABLE]
    TỔNG QUAN VỀ BÀI THI
    [TABLE="width: 672, 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]Thời gian
    [/TD]
    [TD]Điểm
    [/TD]
    [/TR]
    [TR]
    [TD]Bài 1
    [/TD]
    [TD]petrol.pas
    [/TD]
    [TD]petrol.in
    [/TD]
    [TD]petrol.out
    [/TD]
    [TD]1 giây / 1 test
    [/TD]
    [TD]6
    [/TD]
    [/TR]
    [TR]
    [TD]Bài 2
    [/TD]
    [TD]subsets.pas
    [/TD]
    [TD]subsets.in
    [/TD]
    [TD]subsets.out
    [/TD]
    [TD]1 giây / 1 test
    [/TD]
    [TD]7
    [/TD]
    [/TR]
    [TR]
    [TD]Bài 3
    [/TD]
    [TD]money.pas
    [/TD]
    [TD]money.in
    [/TD]
    [TD]money.out
    [/TD]
    [TD]1 giây / 1 test
    [/TD]
    [TD]7
    [/TD]
    [/TR]
    [/TABLE]

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

    Bài 1. Xăng sinh học
    Hãng Nanopetro tổ chức đấu thầu xây dựng dây chuyền xăng sinh học. Có n đơn vị nộp đơn xin đấu thầu. Các thông số chủ yếu của gói thầu thứ i là:

    • A[SUB]i[/SUB] – chi phí lắp đặt dây chuyền sản xuất;
    • B[SUB]i[/SUB] – chí phí một tấn xăng do dây chuyền sản xuất;
    • C[SUB]i[/SUB] – giá thị trường chấp nhận cho một tấn xăng do dây chuyền sản xuất.

    Điểm khấu hao là số xăng phải sản xuất để tổng giá bán bằng chi phí lắp đặt cộng với tổng chi phí sản xuất. Ban Giám đốc Nanopetro muốn có dây chuyền sản xuất với điểm khấu hao thấp nhất.

    Cho n và các thông số A[SUB]i[/SUB], B[SUB]i[/SUB], C[SUB]i[/SUB] (1 ≤ A[SUB]i[/SUB], B[SUB]i[/SUB], C[SUB]i[/SUB] ≤ 10[SUP]9[/SUP], B[SUB]i[/SUB] < C[SUB]i[/SUB], i = 1, 2, …, n, 1 ≤ n ≤ 10[SUP]5[/SUP]). Tất cả các giá trị đều nguyên. Hãy xác định đơn vị trúng thầu. Nều tồn tại nhiều đơn vị cùng trúng thầu thì đưa ra đơn vị có thứ tự nhỏ nhất.

    D liu: Dòng đầu tiên của file vào chứa số nguyên n. Dòng thứ i trong n dòng sau chứa 3 số nguyên A[SUB]i[/SUB], B[SUB]i[/SUB]C[SUB]i[/SUB].

    Kết qu: Đưa ra file ra một số nguyên là đơn vị trúng thầu.

    Ví d:
    [TABLE="align: center"]
    [TR]
    [TD]petrol.in
    [/TD]
    [TD]petrol.out
    [/TD]
    [/TR]
    [TR]
    [TD]2
    1 2 3
    2 1 3
    [/TD]
    [TD]1
    [/TD]
    [/TR]
    [TR]
    [TD]3
    1 2 4
    3 1 4
    2 2 4
    [/TD]
    [TD]1
    [/TD]
    [/TR]
    [/TABLE]


    Bài 2. Tập con
    Cho 2 tập số nguyên X = {x[SUB]1[/SUB], x[SUB]2[/SUB], ..., x[SUB]m[/SUB]} và Y = {y[SUB]1[/SUB], y[SUB]2[/SUB], ..., y[SUB]n[/SUB]}, trong đó: x[SUB]1[/SUB] < x[SUB]2[/SUB] < ... < x[SUB]m[/SUB]y[SUB]1[/SUB] < y[SUB]2[/SUB] < ... < y[SUB]n[/SUB].

    Ta nói rằng X có thứ tự từ điển nhỏ hơn Y nếu thỏa mãn 1 trong 2 điều kiện sau:

    1. i sao cho x[SUB]1[/SUB] = y[SUB]1[/SUB], x[SUB]2[/SUB] = y[SUB]2[/SUB], ..., x[SUB]i[/SUB][SUB]-1[/SUB] = y[SUB]i[/SUB][SUB]-1[/SUB], x[SUB]i[/SUB] < y[SUB]i[/SUB],
    2. m < nx[SUB]1[/SUB] = y[SUB]1[/SUB], x[SUB]2[/SUB] = y[SUB]2[/SUB] , ..., x[SUB]m[/SUB] = y[SUB]m[/SUB].

    Cho trước số nguyên dương n, hãy liệt kê tất cả các tập con khác rỗng của tập {1, 2, ..., n} theo thứ tự từ điển (các phần tử trong tập con được liệt kê theo thứ tự tăng dần của giá trị).

    Dữ liệu: File vào gồm một dòng chứa số nguyên dương n (1 ≤ n ≤ 16).

    Kết quả: Ghi ra file ra các tập con khác rỗng theo thứ tự từ điển, mỗi tập con ghi trên một dòng theo định dạng như trong ví dụ dưới đây.

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


    Bài 3. Money Systems
    Các con bò không chỉ tạo ra một chính phủ cho mình, mà còn tạo ra một hệ thống tiền tệ cho mình. Chúng đang tìm hiểu về giá trị của các đồng tiền. Theo truyền thống, các đồng tiền có giá trị 1, 5, 10, 20 hoặc 25, 50 và 100 đơn vị tiền tệ, đôi khi đồng tiền với giá trị 2 đơn vị cũng được sử dụng để việc trao đổi thuận tiện.

    Các con bò muốn biết có bao nhiêu cách khác nhau để phân phối một lượng tiền nào đó bằng cách sử dụng hệ thống tiền tệ cho trước. Ví dụ, nếu sử dụng hệ thống tiền {1, 2, 5, 10, ...} thì có thể tạo ra 18 đơn vị tiền tệ bằng nhiều cách khác nhau, chẳng hạn 18×1, 9×2, 8×2+2×1, 3×5+2+1, và nhiều cách khác nữa.

    Hãy viết một chương trình tính xem có bao nhiêu cách xây dựng một lượng tiền cho trước bằng cách sử dụng một số loại đồng tiền cho trước. Các bộ dữ liệu vào luôn đảm bảo số cách nằm trong kiểu số nguyên Int64 (Free Pascal).

    Dữ liệu: Dòng đầu tiên của file vào chứa hai số nguyên VN (1 ≤ V ≤ 25, 1 ≤ N ≤ 10.000), tương ứng là số loại đồng tiền trong hệ thống tiền tệ và lượng tiền cần xây dựng. Dòng thứ hai chứa V số nguyên là giá trị của mỗi loại đồng tiền.

    Kết quả: File ra gồm một dòng chứa tổng số cách xây dựng N đơn vị tiền tệ với việc sử dụng V loại đồng tiền trên.

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

    ----------------------------- Hết -----------------------------