De thi HSG tin khong chuyen Binh Dinh 2001

TỈNH ĐOÀN BÌNH ĐỊNH HỘI THI TIN HỌC TRẺ KHÔNG CHUYÊN
LẦN THỨ VII – NĂM 2001
Đề Thi Khối C: TRUNG HỌC PHỔ THÔNG
Thời gian làm bài: 180 phút

Bài 1: (6 điểm) Hoán vị liên tiếp
Cho số nguyên dương n, hãy liệt kê tất cả các hoán vị của tập {1,2,3,…,n} theo thứ tự từ điển.

Bài 2: (6 điểm) Mảng xoắn ốc
Cho một mảng 2 chiều NxN. Hãy sắp xếp các số tự nhiên từ 1 đến N2 vào mảng theo đường xoắn ốc (như hình vẽ)
1




Bài 3: (8 điểm) Đảo trên biển
Biển được biểu diễn bỡi một lưới ô vuông kích thước NxN (1<= N <= 8). Mỗi hòn đảo được đánh dấu bỡi số 1 trên lưới đó. Cho biết các thông số ngang và dọc của các đảo. Cần phải xây dựng lại bản đồ các đảo.

Ví dụ với bản đồ sau, ta có các thông số tương ứng:

Bản đồ Các thông số ngang Các thông số dọc
101100 1 2 1 1 1
011101 3 1 1 2
101010 1 1 1 4
011111 5 2 3
110101 2 1 1 2
000100 1 1 2

Chẳng hạn, dòng 1 các thông số ngang (“1 2”) cho biết dòng 1 có 2 nhóm đảo, nhóm 1 có 1 đảo, nhóm 2 có 2 đảo. Dòng 1 các thông số dọc (“1 1 1”) cho biết cột 1 có 3 nhóm đảo, mỗi nhóm có 1 đảo.
Yêu cầu kỹ thuật: - Dữ liệu vào cho ở file DAO?.INP
- Dữ liệu ra ghi vào file DAO.OUT


Ví dụ: DAO1.INP DAO.OUT
6 <- n=6 101100
1 2 0 <- bắt đầu dòng 1 011101
3 1 0 101010
1 1 1 0 011111
5 0 110101
2 1 1 0 000100
1 0
1 1 1 0 <- bắt đầu cột 1
1 2 0
4 0
2 3 0
2 0
1 2 0