Kỳ thi chọn học sinh giỏi văn hóa lớp 12 THPT môn thi: Tin Học

UBND TỈNH QUẢNG TRỊ
SỞ GIÁO DỤC VÀ ĐÀO TẠO
ĐỀ CHÍNH THỨC
KỲ THI CHỌN HỌC SINH GIỎI VĂN HÓA LỚP 12 THPT
Khóa thi ngày: 05/03/2014
Môn thi: TIN HỌC 
Thời gian làm bài: 180 phút (không kể thời gian giao đề)
Em hãy dùng ngôn ngữ lập trình Pascal hoặc FreePascal để lập trình giải các bài toán sau:
Bài 1. (4điểm) Giải mã văn bản 	 Tên chương trình:GIAIMA.PAS 
Để đảm bảo tính bảo mật trong công tác truyền tin, Cục thông tin quốc gia quy định phải mã hóa bản tin gốc trước khi gửi đi bằng cách thêm các ký tự # vào các vị trí trong bản tin. Chính vì vậy khi cô văn thư của công ty ABC nhận được một văn bản của cấp trên cô không thể đọc được, tiếp theo sau đó cô nhận được một bản hướng dẫn giải mã như sau: trong một xâu nếu tính từ trái sang phải của xâu nếu gặp ký tự # thì # là dấu hiệu yêu cầu xoá đi một ký đứng ngay trước nó và chính nó, nếu ký tự # đứng đầu một từ thì chỉ xóa ký tự #. Em hãy viết chương trình giúp cô văn thư giải mã các văn bản nhận được.
Dữ liệu vào: Cho trong file văn bản GIAIMA.INP gồm một dòng có không quá 255 kí tự.
Kết quả: Ghi vào tập tin GIAIMA.OUT là nội dung văn bản sau khi được giải mã 
Ví dụ: 
GIAIMA.INP
GIAIMA.OUT
Ta#oi thi hoc sinu#h gioi tin hoj#c
 Toi thi hoc sinh gioi tin hoc
Bài 2. (5điểm) Xếp hàng	 Tên chương trình: XEPHANG.PAS
Một nhóm học sinh gồm nam và nữ tổ chức sinh hoạt tập thể. Trong buổi sinh hoạt bạn nhóm trưởng muốn tổ chức một trò chơi nên đã yêu cầu các bạn học sinh chọn N bạn trong nhóm xếp thành hàng ngang sao cho không có 2 bạn nam nào đứng kề nhau (1≤N≤20). 
Yêu cầu: Hãy liệt kê tất cả các cách xếp hàng thoả mãn yêu cầu trên.
Dữ liệu vào: cho bởi File XEPHANG.INP gồm một dòng ghi số N
Kết quả: ghi ra file XEPHANG.OUT có cấu trúc như sau:
- Dòng 1: ghi số nguyên dương k là số cách xếp thoả mãn yêu cầu
- k dòng tiếp theo, mỗi dòng là một phương án xếp hàng.
Ví dụ: giả sử ta mã hoá bạn nam là 1 và bạn nữ là 0, với N =4 ta có kết quả như sau:
XEPHANG.INP
XEPHANG.OUT
4
8
0000
0001
0010
0100
1000
0101
1001
1010
Bài 3: (6 điểm) Chọn đề thi	 Tên chương trình: CANSU.PAS
	Một lớp học có MxN chỗ ngồi, gồm M hàng ghế, mỗi hàng ghế có N học sinh. Để chuẩn bị cho kỳ thi học sinh giỏi Tin học, ban cán sự lớp mỗi người sáng tác một đề thi sau đó sao thành nhiều bản và đưa cho các bạn ngồi bên cạnh (trái, phải, trước, sau) mỗi người đúng 1 bản, Sau đó mỗi người trong lớp thông báo số đề mình đã nhận được. 
Yêu cầu: Xác định vị trí của những người trong ban cán sự lớp.
Dữ liệu vào: cho bởi File CANSU.INP có cấu trúc như sau:
	- Dòng 1: ghi 2 số ( Với 1<=M, N (M,N<=50)
	- M dòng tiếp theo, với dòng i gồm các số i1, i2, , in cho biết số đề mà mỗi người ở hàng ghế thứ i nhận được. Các số được viết cách nhau một dấu cách
Kết quả: ghi ra file CANSU.OUT có cấu trúc như sau: có M dòng, trên mỗi dòng gồm có N ký tự “ . “ hoặc “x”, trong đó ký tự “x” thể hiện vị trí của ban cán sự lớp, nếu không có phương án thi ghi là “Không có nghiệm”. 
Ví dụ: 
CANSU.INP 
CANSU.OUT 
6 6
0 1 0 1 1 0
1 0 3 1 1 1
0 2 0 2 1 0
0 0 1 0 1 0
0 1 0 1 0 2
1 0 1 0 2 0
. . . . . .
. x . x x .
. . x . . .
. . . . . .
. . . . x .
. x . . . x
Bài 4: (5 điểm) Xóa điểm game	Tên chương trình: XOADIEM.PAS 
Flappy Bird là một game rất được người dùng điện thoại thông minh trên toàn thế giới ưa thích, nó được sáng lập bởi một lập trình viên Việt nam.
An đã chơi game này n ván. Điểm của ván chơi thứ i là ai (1 ≤ ai ≤ 5000). Mặc dù rất cố gắng nhưng kết quả của mỗi ván chơi không hoàn toàn tốt như nhau. An muốn xóa bớt một số điểm của các ván đã chơi sao cho số điểm của các ván còn lại không có ván nào có số điểm lớn hơn gấp hai lần số điểm của ván khác.
Em hãy giúp An tính xem cần phải xóa ít nhất bao nhiêu ván đã chơi.
Dữ liệu: vào từ file văn bản XOADIEM.INP có cấu trúc như sau:
Dòng đầu ghi n là số lượng ván đã chơi;
Dòng thứ hai ghi n số nguyên a1,a2,,an lần lượt là điểm số của các ván đã chơi.
Các số trong file cách nhau ít nhất một dấu cách.
Kết quả: ghi ra file văn bản XOADIEM.OUT ghi duy nhất một số là số lượng ván ít nhất cần xóa.
Ví dụ:
XOADIEM.INP
XOADIEM.OUT
6
4 5 3 8 3 7
2
4
4 3 2 4
0
Giới hạn: Thời gian thực hiện không quá 1s.
Có 60% test n≤1000 tương ứng 60% số điểm;
Có 40% test n≤100000 tương ứng 40% số điểm;
----------------- Hết -------------------
Lưu ý: Thí sinh tạo trên ổ đĩa D thư mục có tên là số báo danh, làm bài và lưu vào thư mục vừa tạo. Ví dụ thí sinh có SBD là 15 sẽ tạo thư mục D:\15 và lưu bài làm vào thư mục này.