Menu

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

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 4
    [/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: 11/04/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]reverse.pas
    [/TD]
    [TD]reverse.in
    [/TD]
    [TD]reverse.out
    [/TD]
    [TD]1 giây / 1 test
    [/TD]
    [TD]6
    [/TD]
    [/TR]
    [TR]
    [TD]Bài 2
    [/TD]
    [TD]choco.pas
    [/TD]
    [TD]choco.in
    [/TD]
    [TD]choco.out
    [/TD]
    [TD]1 giây / 1 test
    [/TD]
    [TD]7
    [/TD]
    [/TR]
    [TR]
    [TD]Bài 3
    [/TD]
    [TD]atm.pas
    [/TD]
    [TD]atm.in
    [/TD]
    [TD]atm.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. Lật màu
    Xét trò chơi một người như sau: cho băng giấy n ô (1 ≤ n ≤ 1.000), mỗi ô có một màu đen hoặc trắng. Mỗi lần người chơi có thể chọn dãy ô liên tục độ dài tùy ý, đổi ngược màu các ô được chọn, tức là trắng thành đen, đen thành trắng. Nhiệm vụ của người chơi là đưa tất cả các ô của băng về cùng một màu.



    Cho n và màu của các ô dưới dạng dãy n số 0 và 1, 0 tương ứng với ô màu đen, 1 tương ứng với ô màu trắng. Hãy xác định số lần ít nhất biến đổi để đưa các ô về cùng một màu.

    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 n số nguyên 0 và 1 xác định màu các ô, giữa hai số ngăn cách nhau một dấu cách.

    Kết quả: Đưa ra file ra một số nguyên là số lần biến đổi ít nhất.

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


    Bài 2. Sô cô la
    Một loại sô cô la mới được bày bán ở cửa hàng địa phương. Sô cô la được sản xuất dưới dạng tấm, loại 1 ô, 2 ô, 4 ô, 8 ô, ... tức là số ô có dạng 2[SUP]m[/SUP]. Với m chẵn tấm sô cô la có hình vuông, với m lẻ tấm sô cô la có hình chữ nhật, một cạnh dài gấp đôi cạnh kia.

    Mirko rất thích loại sô cô la mới này và nghĩ rằng mình phải ăn đủ k ô mới cảm nhận được hết vị ngon của nó. Mirko bẻ tấm sô cô la để lấy đúng k ô. Phần còn thừa (nếu có) sẽ chia cho người bạn thân của mình. Để tránh nhầm lẫn Mirko luôn bẻ đôi tấm sô cô la hoặc phần xuất hiện sau mỗi lần bẻ.

    Ví dụ với k = 5, Mirko sẽ mua tấm sô cô la có 8 ô và sau 3 lần bẻ Mirko lấy 1 miếng 4 ô và 1 miếng 1 ô thì sẽ lấy được cho mình đúng 5 ô.

    Cho số nguyên k (1 ≤ k ≤ 10[SUP]6[/SUP]). Hãy xác định tấm sô cô la nhỏ nhất cần mua và số lần bẻ.

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

    Kết quả: Đưa ra file ra 2 số nguyên ngăn cách nhau một dấu cách tương ứng là số ô của tấm sô cô la nhỏ nhất cần mua và số lần bẻ.

    Ví dụ:
    [TABLE="align: center"]
    [TR]
    [TD]choco.in
    [/TD]
    [TD]choco.out
    [/TD]
    [/TR]
    [TR]
    [TD]5
    [/TD]
    [TD]8 3
    [/TD]
    [/TR]
    [TR]
    [TD]6
    [/TD]
    [TD]8 2
    [/TD]
    [/TR]
    [TR]
    [TD]7
    [/TD]
    [TD]8 3
    [/TD]
    [/TR]
    [/TABLE]


    Bài 3. ATM
    Một cây rút tiền tự động ATM có n loại tiền mệnh giá a[SUB]1[/SUB], a[SUB]2[/SUB], ..., a[SUB]n[/SUB] với số lượng tiền mỗi loại không hạn chế. Bạn viết một chương trình cho cây rút tiền tự động ATM: Khi mỗi khách hàng đến rút m đồng thì cần bao nhiêu tiền mỗi loại để chi trả, sao cho số lượng tờ tiền sử dụng là ít nhất.

    Dữ liệu: File vào gồm 2 dòng: dòng thứ nhất ghi 2 số nguyên nm (1 £ n £ 30, 1 £ m £ 1.000.000); dòng thứ hai ghi n số nguyên a[SUB]1[/SUB], a[SUB]2[/SUB], ..., a[SUB]n[/SUB] ngăn cách nhau bởi một dấu cách (1 £ a[SUB]i[/SUB] £ 500.000 với i = 1, 2, ..., n).

    Kết quả: Nếu bài toán vô nghiệm thì ghi ra một dòng chữ ‘No solution’. Ngược lại ghi ra file ra gồm 2 dòng: dòng đầu tiên ghi số lượng tờ phải trả; dòng thứ hai ghi n số nguyên không âm, số thứ i ứng với số tờ cần trả cho loại tiền mệnh giá thứ i, các số ghi trên cùng một dòng cách nhau một dấu cách. Nếu có nhiều cách trả có cùng số lượng tờ ít nhất thì đưa ra một cách bất kỳ trong chúng.

    Ví dụ:
    [TABLE="align: center"]
    [TR]
    [TD]atm.in
    [/TD]
    [TD]atm.out
    [/TD]
    [/TR]
    [TR]
    [TD]5 97
    1 5 10 50 100
    [/TD]
    [TD]8
    2 1 4 1 0
    [/TD]
    [/TR]
    [TR]
    [TD]2 1234
    1000 2000
    [/TD]
    [TD]No solution
    [/TD]
    [/TR]
    [/TABLE]

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