SỞ GD&ĐT NINH BÌNH

ĐỀ CHÍNH THỨC


ĐỀ THI CHỌN ĐỘI TUYỂN CHÍNH THỨC DỰ THI HỌC SINH GIỎI QUỐC GIA
Năm học: 2011 - 2012
Môn: Tin học
Thời gian làm bài: 180 phút.
(Đề thi gồm 03 bài trong 02 trang)


Tổng quan đề thi:
Bài
Chương trình
Input
Output
Thời gian

Lát viền
BRICK.PAS
BRICK.INP
BRICK.OUT
01 giây/test

Trái phiếu
OBL.PAS
OBL.INP
OBL.OUT
 01 giây/test

Tăng lương
SALARY.PAS
SALARY.INP
SALARY.OUT
04 giây/test


Bài 1: Lát viền (7 điểm).
Người ta cần lát kín đường viền trang trí trong công viên có kích thước 2 x n bằng n viên gạch kích thước 2 x 1 (trong hình dưới là các cách lát cho trường hợp n = 3).




















Yêu cầu: Cho biết n, hãy xác định số cách lát khác nhau.
Dữ liệu vào: Cho trong file BRICK.INP gồm một số nguyên dương n (n < 10000).
Dữ liệu ra: Ghi ra file BRICK.OUT một số nguyên duy nhất là đáp án của bài toán.
Ví dụ:
BRICK.INP
BRICK.OUT

3
3


Bài 2: Trái phiếu (7 điểm).
Rôn tốt nghiệp khoa kinh tế với bằng xuất sắc và quyết định khởi nghiệp bằng việc tham gia thị trường mua bán trái phiếu ngắn hạn của chính phủ. Nguyên tắc của thị trường trái phiếu chính phủ là nếu ngày nào bạn đăng ký tham gia thì phải mua hoặc bán đúng một trái phiếu. Trong một ngày giá bán hay mua là giống nhau. Qua nghiên cứu tìm hiểu, Rôn thấy rằng trái phiếu lên giá hàng ngày. Hiện nay mỗi trái phiếu có giá là 1, ngày mai giá mỗi trái phiếu sẽ là 2, đến ngày thứ m giá sẽ là m.
Trong tay Rôn hiện đang có số tiền mặt là n và một số lượng trái phiếu lớn hơn k. Rôn quyết định đăng ký tham gia thị trường Trái phiếu trong k ngày liên tiếp kể từ hôm nay với quy tắc hành động hết sức đơn giản: mỗi ngày nếu còn đủ tiền mặt để mua thì sẽ mua, trong trường hợp ngược lại sẽ bán. Ví dụ, với n = 7 và k = 4, hôm nay Rôn sẽ mua và số tiền còn lại trong túi là 6, hai ngày nữa Rôn cũng sẽ mua với chi phí là 2 và 3, tiền mặt còn lại là 1. Ở ngày thứ tư Rôn bán trái phiếu và có số tiền mặt là 5.
Yêu cầu: Cho n, k (1 ≤ n, k ≤ 1015). Hãy xác định số tiền mặt Rôn có ở cuối ngày thứ k.
Dữ liệu: Vào từ file văn bản OBL.INP gồm một dòng chứa 2 số nguyên n và k.
Kết quả: Đưa ra file văn bản OBL.OUT một số nguyên là số tiền mặt Rôn có ở cuối ngày thứ k.
Ví dụ:
OBL.INP

OBL.OUT

7 4

5

Bài 3: Tăng lương (6 điểm).
Steve là ông chủ kiêu hãnh của một công ty phần mềm lớn. Ban đầu công ty chỉ có một mình Steve. Công việc làm ăn phát đạt và công ty thuê n công nhân, lần lượt từng người, từng người một. Steve được đánh số là 0. Các công nhân khác – đánh số từ 1 đến n theo trình tự thuê. Mỗi người mới vào có một mức lương khởi điểm và chịu sự chỉ đạo của một ai đó trong công ty. Nếu lương công nhân cao hơn lương thủ trưởng trực tiếp của mình thì lương của người thủ trưởng đó được nâng lên bằng lương người dưới quyền mình. Quá trình điều chỉnh này được tiếp diễn cho đến khi đảm bảo được trong toàn công ty lương thủ trưởng không thấp hơn lương công nhân dưới quyền.
Yêu cầu: Với mỗi công nhân được tuyển chọn vào công ty hãy xác định số người phải điều chỉnh lương cho phù hợp với người mới được tuyển chọn.
Dữ liệu: Vào từ file văn bản SALARY.INP:
Dòng đầu tiên chứa số nguyên n (1 ≤ n ≤ 300 000),
Dòng thứ 2 chứa một số nguyên – lương khởi điểm của Steve,
Dòng thứ i trong n dòng sau chứa 2 số nguyên S và B – lương khởi điểm và thủ trưởng của người công nhân thứ i.
Lương khởi điểm nằm trong phạm vi từ 1 đến 109.
Kết quả: Đưa ra file văn bản SALARY.OUT n số số nguyên, mỗi số trên một dòng, là kết quả tính được đối với mỗi người.
Ví dụ: