De thi HSGQG 2014-2015

SỞ GIÁO DỤC VÀ ĐÀO TẠO KỲ THI CHỌN ĐỘI TUYỂN HỌC SINH GIỎI QUỐC GIA CẤP THPT
VĨNH LONG NĂM HỌC 2012 - 2013

ĐỀ THI CHÍNH THỨC Môn thi: TIN HỌC
Thời gian làm bài: 180 phút (không kể thời gian giao đề) Ngày thi: 8/12/2012
(Đề thi có 03 trang, gồm 05 bài)

TỔNG QUAN BÀI THI


Tên bài
File chương trình
File dữ liệu vào
File kết quả

Bài 1
Tổng số ong tổ tiên
ONGTONG.PAS
ONGTONG.INP
ONGTONG.OUT

Bài 2
Tickets
TICKETS.PAS
TICKETS.INP
TICKETS.OUT

Bài 3
Trò chơi
GAME.PAS
GAME.INP
GAME.OUT

Bài 4
Cái ba lô
BALO.PAS
BALO.INP
BALO.OUT

Bài 5
Mạng máy tính
NET.PAS
NET.INP
NET.OUT


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

Bài 1. (6 điểm) Tổng số ong tổ tiên
Ong là loài có thể thụ tinh đơn tính hoặc lưỡng tính. Nếu một trứng ong thụ tinh bởi chính con ong cái nó nở thành một con ong đực. Tuy nhiên, nếu một trứng thụ tinh bởi một ong đực nó nở thành một con ong cái. Như vậy một con ong đực sẽ luôn có một mẹ, và một con ong cái sẽ có cả bố và mẹ.
Ta bắt đầu tính số con ong tổ tiên của một con ong đực. Xét 1 con ong đực ở thế hệ thứ n. Theo quy luật trên, ta thấy:
- Trước một đời, thế hệ n-1: Con ong đực chỉ có một mẹ (1 ong cái).
- Trước hai đời, thế hệ n-2: Con ong cái đời n-1 có 2 bố mẹ, một ong bố (đực) và một ong mẹ (cái) (2 con ong: 1 đực+ 1 cái)).
- Trước ba đời, thế hệ n-3: Con ong cái thế hệ n-2 lại có hai bố mẹ, một ong bố (đực) và một mẹ (cái), và con đực thế hệ n-2 có một mẹ (3 con ong: 1 ong đực + 2 ong cái).
- Trước bốn đời, thế hệ n-4: Hai con cái, mỗi con có 2 cha, mẹ và mỗi con đực có một mẹ (5 con ong: 2 ong đực 3 ong cái).
Vĩnh và Long là đôi bạn cùng lớp. Sau khi tính được số con ong tổ tiên của 1 con ong đực ở 1 thế hệ N bất kỳ (với N<=25000), Vĩnh nghĩ ra 1 trò chơi như sau:
Vĩnh sẽ nói ngẫu nhiên một con số N cho biết con ong đực đang ở thế hệ thứ mấy, còn Long trong vòng 2 giây phải tính ra tổng số con ong ở các thế hệ tổ tiên của con ong đó từ thế hệ N-1 đến thế hệ đầu tiên.
Với N nhỏ (N=6 chẳng hạn), Vĩnh có thể dễ dàng kiểm tra kết quả là đúng hay sai, nhưng khi N lớn (với N=49, Long cho ra con số 20365011072) thì Vĩnh bắt đầu nghi ngờ kết quả này, N càng lớn thì sự nghi ngờ chắc chắn sẽ càng cao! Bạn hãy giúp Vĩnh giải tỏa mối nghi ngờ này nhé!
Yêu cầu: cho biết con ong đang ở thế hệ N, hãy tính ra tổng số con ong ở các thế hệ tổ tiên của con ong đó từ thế N-1 đến thế hệ thứ nhất.
Dữ liệu: vào từ file văn bản ONGTONG.INP chỉ có 1 dòng chứa số nguyên dương N cho biết con ong đực đang ở thế hệ thứ mấy (2<=N<=25000).
Kết quả: ghi ra file văn bản ONGTONG.OUT một số nguyên duy nhất là tổng số con ong ở các thế hệ tổ tiên của con ong đực ở thế hệ N.
Ví dụ:
ONGTONG.INP
ONGTONG.OUT

6
19

49
20365011072


Ràng buộc: 50% số test ứng với 50% số điểm của bài có N <= 5000.


Bài 2. (6 điểm) Tickets
Có N người xếp hàng mua vé. Được đánh số từ 1 đến N theo thứ tự đứng trong hàng (từ đầu hàng đến cuối hàng). Mỗi người cần mua một vé nhưng được quyền mua tối đa 3 vé cho mình và những người đứng ngay sau mình. Dĩ nhiên, không ai được mua thừa vé . Mỗi người có một tốc độ xử lý tình huống khác nhau, do đó thời gian phục vụ mỗi người cũng khác nhau. Với người thứ i thời gian để mua một vé là ai, 2 vé là bi và 3 và là ci.
Yêu cầu: Cho biết n – số người trong