Đề thi chọn học sinh giỏi quốc gia lớp 12 THPT môn Tin học - Năm học 2007-2008 (Có đáp án)

Bé GI¸O DôC Vµ §µO T¹O	K× THI CHäN HäC SINH GiáI QuèC GIA
	LíP 12 THPT N¡M 2008
 §Ò THI CHÝNH THøC
	M«n: TIN Häc
	Thêi gian: 180 phót (kh«ng kÓ thêi gian giao ®Ò)
	Ngµy thi: 29/01/2008
 (Đề thi gồm 3 trang)
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
Trò chơi với dãy số
SEQGAME.*
SEQGAME.INP
SEQGAME.OUT
Bài 2
Lò cò 
JUMP.*
JUMP.INP
JUMP.OUT
Bài 3
Quà Tết
GIFTS.*
GIFTS.INP
GIFTS.OUT
Dấu * được thay thế bởi PAS hoặc CPP của ngôn ngữ lập trình được sử dụng tương ứng là Pascal hoặc C++. 
Hãy lập trình giải các bài toán sau:
Bài 1 (6 điểm). Trò chơi với dãy số
Hai bạn học sinh trong lúc nhàn rỗi nghĩ ra trò chơi sau đây. Mỗi bạn chọn trước một dãy số gồm n số nguyên. Giả sử dãy số mà bạn thứ nhất chọn là
 b1, b2, ..., bn
còn dãy số mà bạn thứ hai chọn là
 c1, c2, ..., cn.
Mỗi lượt chơi mỗi bạn đưa ra một số hạng trong dãy số của mình. Nếu bạn thứ nhất đưa ra số hạng bi (1 ≤ i ≤ n), còn bạn thứ hai đưa ra số hạng cj (1 ≤ j ≤ n) thì giá của lượt chơi đó sẽ là |bi + cj|.
Ví dụ: Giả sử dãy số bạn thứ nhất chọn là 1, - 2; còn dãy số mà bạn thứ hai chọn là 2, 3. Khi đó các khả năng có thể của một lượt chơi là (1, 2), (1, 3), (-2, 2), (-2, 3). Như vậy, giá nhỏ nhất của một lượt chơi trong số các lượt chơi có thể là 0 tương ứng với giá của lượt chơi (-2, 2).
Yêu cầu: Hãy xác định giá nhỏ nhất của một lượt chơi trong số các lượt chơi có thể.
Dữ liệu: Vào từ file văn bản SEQGAME.INP:
Dòng đầu tiên chứa số nguyên dương n (n ≤ 105);
Dòng thứ hai chứa dãy số nguyên b1, b2, ..., bn (|bi| ≤ 109, i = 1, 2, ..., n);
Dòng thứ ba chứa dãy số nguyên c1, c2, ..., cn (|cj| ≤ 109, j = 1, 2, ..., n).
Hai số liên tiếp trên một dòng được ghi cách nhau bởi dấu cách.
Kết quả: Ghi ra file văn bản SEQGAME.OUT giá nhỏ nhất tìm được.
Ví dụ:
SEQGAME.INP
SEQGAME.OUT
2
1 -2 
2 3 
0
Ràng buộc: 60% số tests ứng với 60% số điểm của bài có 1 ≤ n ≤ 1000.
Bài 2 (7 điểm). Lò cò
Nhảy lò cò là trò chơi dân gian của Việt Nam. Người trên hành tinh X cũng rất thích trò chơi này và họ đã cải biên trò chơi này như sau: Trên mặt phẳng vẽ n vòng tròn được đánh số từ 1 đến n. Tại vòng tròn i người ta điền số nguyên dương ai. Hai số trên hai vòng tròn tuỳ ý không nhất thiết phải khác nhau. Tiếp đến người ta vẽ các mũi tên, mỗi mũi tên hướng từ một vòng tròn đến một vòng tròn khác. Quy tắc vẽ mũi tên là: Nếu có ba số ai, aj, ak thoả mãn: ak=ai+aj thì vẽ mũi tên hướng từ vòng tròn i đến vòng tròn k và mũi tên hướng từ vòng tròn j đến vòng tròn k. Người chơi chỉ được di chuyển từ một vòng tròn đến vòng tròn khác nếu có mũi tên từ vòng tròn xuất phát hướng đến vòng tròn đích. Người chơi có thể xuất phát từ một trong số các vòng tròn, di chuyển theo các mũi tên đã vẽ để đến các vòng tròn khác. Người thắng cuộc sẽ là người tìm được cách di chuyển qua nhiều vòng tròn nhất.
Ví dụ: Với 5 vòng tròn và các số trong vòng tròn là 1, 2, 8, 3, 5, trò chơi được trình bày trong hình dưới đây: 
1
2
3
5
8
Khi đó có thể di chuyển được nhiều nhất qua 4 vòng tròn (tương ứng với đường di chuyển được tô đậm trên hình vẽ).
Yêu cầu: Hãy xác định xem trong trò chơi mô tả ở trên, nhiều nhất có thể di chuyển được qua bao nhiêu vòng tròn.
Dữ liệu: Vào từ file văn bản JUMP.INP:
Dòng đầu tiên chứa số nguyên n (3 ≤ n ≤ 1000);
Dòng thứ hai chứa dãy số nguyên dương a1, a2, ..., an (ai ≤ 109, i = 1, 2, ..., n).
Hai số liên tiếp trên một dòng được ghi cách nhau bởi dấu cách.
Kết quả: Ghi ra file văn bản JUMP.OUT số lượng vòng tròn trên đường di chuyển tìm được.
Ví dụ:
JUMP.INP
JUMP.OUT
5
1 2 8 3 5 
4
Ràng buộc: 60% số tests ứng với 60% số điểm của bài có 3 ≤ n ≤ 100.
Bài 3 (7 điểm). Quà Tết
Chuẩn bị đón năm mới, Công ty bánh kẹo Hương Dứa đã làm một tấm sôcôla cực lớn với mục đích ghi tên mình vào sách kỷ lục Ghi nét đồng thời quảng bá thương hiệu trước công chúng. Tấm sôcôla có hình vuông kích thước 2k×2k ô, tạo thành lưới ô vuông 2k hàng và 2k cột. Các hàng được đánh số từ 0 đến 2k-1 từ trên xuống dưới, các cột được đánh số từ 0 đến 2k-1 từ trái sang phải. Ô nằm trên hàng i và cột j được gọi là ô (i, j). Sau buổi trưng bày giới thiệu sản phẩm, tấm sôcôla được cắt nhỏ, chia cho mọi người, mỗi người được một ô của chiếc bánh kỷ lục. Bộ phận tiếp thị đã ấn vào hai ô khác nhau (p, q) và (u, v) mỗi ô một đồng xu. Vị khách nào may mắn nhận được ô sôcôla có đồng xu sẽ được tặng rất nhiều sản phẩm độc đáo của Công ty. 
Vì chiếc bánh rất lớn nên Công ty đã thiết kế một máy cắt bánh. Máy thực hiện dãy các thao tác cắt, bắt đầu từ chồng bánh chỉ gồm 1 tấm sôcôla ban đầu, mỗi thao tác gồm hai bước sau: 
Bước 1: Cắt ngang song song với cạnh chồng bánh chia chồng sôcôla thành hai phần bằng nhau, úp chồng bánh bên dưới lên chồng bánh bên trên sao cho mép dưới đè lên mép trên.
Bước 2: Cắt dọc song song với cạnh chồng bánh chia chồng sôcôla thành hai phần bằng nhau, úp chồng bánh bên trái lên trên chồng bánh bên phải sao cho mép trái đè lên mép phải.
Như vậy sau mỗi lần thực hiện thao tác cắt, chiều dài và chiều rộng của các tấm sôcôla giảm đi một nửa. Sau k lần thực hiện thao tác cắt, các ô của tấm sôcôla sẽ được xếp thành một cột. Khách nhận bánh xếp hàng một và được đánh số từ 1 trở đi, người thứ m sẽ nhận được ô sôcôla thứ m từ trên xuống dưới (1 ≤ m ≤ 2k×2k). 
Ví dụ, với k = 1 và đồng xu được ấn vào các ô (0, 0), (1, 1), việc thực hiện các thao tác cắt được trình bày trên hình vẽ minh hoạ ở trên. Trong ví dụ này, vị khách thứ nhất và thứ ba sẽ là những người nhận được tặng phẩm của Công ty.
Yêu cầu: Cho biết các số nguyên k, p, q, u, v. Hãy xác định số thứ tự của hai vị khách may mắn được nhận quà.
Dữ liệu: Vào từ file văn bản GIFTS.INP gồm một dòng chứa 5 số nguyên k, p, q, u, v, các số cách nhau bởi dấu cách.
Kết quả: Đưa ra file văn bản GIFTS.OUT một dòng chứa hai số nguyên là số thứ tự của các vị khách may mắn. Hai số phải cách nhau đúng một dấu cách.
Ví dụ:
GIFTS.INP
GIFTS.OUT
1 0 0 1 1
1 3
Ràng buộc:
1 ≤ k ≤ 40, 0 ≤ p, q, u, v ≤ 2k -1;
60% số tests ứng với 60% số điểm của bài có 1 ≤ k ≤ 5.
--------------------------- Hết ---------------------------
Ghi chú: 
Thí sinh không được sử dụng tài liệu.
Cán bộ coi thi không giải thích gì thêm.