Tin học trẻ Bình Định lần 14 - Bảng B
Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (111.54 KB, 2 trang )
TỈNH ĐOÀN BÌNH ĐỊNH
HỘI THI TIN HỌC TRẺ
LẦN THỨ XIV – NĂM 2008
Bảng B: TRUNG HỌC CƠ SỞ
Thời gian làm bài: 120 phút
TỔNG QUAN BÀI THI
Tên bài Tên chương trình File dữ liệu vào File kết quả Điểm
Bài 1 Đảo chữ cái DAOCHUCAI.PAS DAOCHUCAI.INP DAOCHUCAI.OUT 4
Bài 2 Duyệt binh DUYETBINH.PAS DUYETBINH.INP DUYETBINH.OUT 10
Bài 3 Số đặc biệt SUPERNUM.PAS SUPERNUM.INP SUPERNUM.OUT 6
Chú ý: Các file dữ liệu vào *.INP phải được đặt trong thư mục " \TRE08\"
Các file bài làm *.PAS và dữ liệu ra *.OUT đặt trong thư mục riêng của từng thí sinh,
ví dụ \TRE08\SBD01\
Bài 1: Đảo chữ cái
Bạn phải viết chương trình đưa ra tất cả các từ có thể có phát sinh từ một tập các chữ cái.
Ví dụ: Cho từ "abc", chương trình của bạn phải đưa ra được các từ "abc", "acb", "bac", "bca",
"cab", "cba" (bằng cách khảo sát tất cả các trường hợp khác nhau của tổ hợp ba chữ cái đã cho)
Dữ liệu vào: được cho trong file DAOCHUCAI.INP, có cấu trúc như sau:
– Dòng đầu tiên: chứa số tự nhiên N cho biết số từ được cho ở dưới.
– N dòng tiếp theo: mỗi dòng chứa một từ (gồm các chữ cái hoa hoặc thường từ A đến Z, các
chữ cái thường và hoa được coi là khác nhau. Một chữ cái nào đó có thể xuất hiện nhiều hơn
một lần).
Dữ liệu ra: ghi vào file DAOCHUCAI.OUT chứa tất cả các từ khác nhau được sinh từ các từ
trong file dữ liệu vào. Các từ sinh ra phải được sắp xếp tăng dần của bảng chữ cái.
Ví dụ:
DAOCHUCAI.INP DAOCHUCAI.OUT
2
abc
acba
abc
acb
bac
bca
cab
cba
aabc
aacb
abac
abca
acab
acba
baac
baca
bcaa
caab
caba
cbaa
Bài 2: Duyệt binh
Một trung đội có N người lính. Trong một buổi duyệt binh, N người lính được yêu cầu xếp hàng
dọc trước mặt trung đội trưởng. Trung đội trưởng cảm thấy không hài lòng về cách sắp xếp
những người lính của mình vì họ đứng theo thứ tự 1, 2, 3, …, N chứ không xếp theo chiều cao
của họ. Ông yêu cầu một vài người lính ra khỏi hàng và những người còn lại đứng yên, tạo
thành một hàng mới mà mỗi ngwòi lính có thể nhìn thấy đầu hàng trước hoặc sau lưng mình.
Một người lính có thể nhìn thấy đầu hàng nếu không có người nào cao hơn hoặc bằng đứng chắn
tầm nhìn của anh ta.
Yêu cầu: Cho biết chiều cao của mỗi người lính, hãy viết chương trình xác định số lượng nhỏ
nhất những người lính cần rời khỏi hàng để hàng còn lại thoả mãn tính chất trên.
Dữ liệu vào: cho trong file DUYETBINH.INP, có cấu trúc như sau:
– Dòng đầu tiên: chứa số nguyên N (1 ≤ N ≤ 1000)
– Dòng thứ 2: chứa N số là chiều cao của N người lính xếp theo hàng được liệt kê theo thứ tự
trong hàng. Các số cách nhau ít nhất một dấu cách.
Dữ liệu ra: ghi vào file DUYETBINH.OUT, có cấu trúc như sau:
– Dòng đầu tiên: ghi số nguyên K là số người lính phải rời khỏi hàng.
– Dòng thứ 2: ghi K số nguyên là số thứ tự của K người lính đó.
Ví dụ:
DUYETBINH.INP DUYETBINH.OUT
8
1.86 1.86 1.30 2.00 1.40 1.00 1.97 2.20
4
1 2 7 8
Bài 3: Số đặc biệt
Cho dãy số nguyen A[1], A[2], … A[N] khác nhau đôi một (N ≤ 10
5
, 1 ≤ A[i] ≤ N). A[i] được
gọi là một số đặc biệt đối với dãy số trên nếu A[i] thuộc ít nhất một dãy con tăng dài nhất của A,
với định nghĩa dãy con tăng dài nhất của A là dãy A[i
1
], A[i
2
], …, A[i
p
] thoả mãn:
+
p
i i i N
1 2
1 ...≤ < < < ≤
+
p
A i A i A i
1 2
...
< < <
+ p lớn nhất có thể được.
Yêu cầu: Chỉ ra tất cả các số đặc biệt của dãy A theo định nghĩa ở trên.
Dữ liệu vào: cho trong file SUPERNUM.INP, có cấu trúc như sau:
– Dòng đầu là số T (1 ≤ T ≤ 10) là số bộ test cần giải quyết.
– T nhóm dòng kế tiếp, mỗi nhóm gồm 2 dòng:
+ Dòng đầu là số N
+ Dòng thứ 2 chứa N số nguyên từ 1 đến N.
Dữ liệu ra: ghi vào file SUPERNUM.OUT gồm T dòng, mỗi dòng ghi các số đặc biệt của bộ
test tương ứng theo thứ tự tăng dần.
Ví dụ:
SUPERNUM.INP SUPERNUM.OUT
2
7
1 2 3 7 4 5 6
5
1 4 3 2 5
1 2 3 4 5 6 7
1 2 3 4 5
===========================
