Đề thi thử học sinh giỏi môn Tin học THCS

 Bài 1: Một nhóm gồm N học sinh góp tiền mua một phần mềm, phần mềm đó có mật khẩu mới sử dụng được. Mật khẩu này chỉ có người bán phần mềm biết. Người này không đưa trực tiếp mật khẩu mà đưa cho mỗi bạn trong nhóm học sinh một con số và nói: “Mật khẩu là một số nhỏ nhất khác 0 có không quá 8 chữ số và chia hết cho bất cứ số nào trong các số đã đưa”. Hãy tìm mật khẩu đó. 
Dữ liệu vào: Đọc từ file BAI_1.IN: dòng đầu ghi số N (0 < N ≤ 100), dòng tiếp theo ghi N số nguyên dương mà chủ cửa hàng đưa (mỗi số nhỏ hơn hoặc bằng 2 000 000 000).
Dữ liệu ra: Kết quả ghi vào file BAI_1.OUT: một dòng duy nhất ghi mật khẩu tìm được, nếu không tìm được thì ghi -1.
Ví dụ về file input và output
BAI_1.IN
BAI_1.OUT
3 
4 6 3 
12
Bài 2: Cho một dãy N viên bi gồm 3 mầu xanh, trắng, đỏ xếp lẫn lộn. Bằng cách đổi chỗ từng cặp viên bi cho nhau, hãy xếp lại dãy bi trên theo trình tự xanh trước, trắng giữa, đỏ sau. Yêu cầu cần dùng một số ít nhất phép đổi chỗ.
Dữ liệu vào được cho bởi file BAI_2.IN. Dòng thứ nhất ghi số nguyên dương N ≤ 1000. Dòng tiếp theo, ghi dãy các ký tự thuộc ba loại: X, T, D thể hiện dãy bi ban đầu.
Dữ liệu ra ghi vào file BAI_2.OUT trong đó dòng thứ nhất ghi số lượng phép đổi chỗ cần dùng. Trong những dòng tiếp theo, mỗi dòng ghi một phép đổi chỗ dưới dạng hai số p, q có nghĩa là đổi chỗ các viên bi ở hai vị trí p và q cho nhau. Trình tự viết các dòng là trình tự các phép đổi chỗ được tiến hành.
Ví dụ về input và output
BAI_2.IN
BAI_2.OUT
9
TTXDDDTDX
4
1 3
4 7
5 9
2 5
Bài 3: Cho xâu S chỉ gồm các dấu mở và đóng ngoặc tròn “(“, “)”. Hãy xét xem liệu có thể viết thêm một số toán hạng và dấu phép toán giữa các dấu đó để nhận được một biểu thức số học đúng không.
Dữ liệu vào được cho bởi file BAI_2.IN trong đó mỗi dòng ghi một xâu ký tự. Với mỗi dòng đọc được của file BAI_2.IN, có ba khả năng:
- Nếu xâu tương ứng chứa ký tự khác với “(“ và “)”, ghi vào file BAI_2.OUT dòng chữ “KHONG HOP LE”
- Nếu xâu chỉ gồm các ký tự “(“ và “)” và có thể viết thêm một số toán hạng và dấu phép toán giữa các dấu đó để nhận được một biểu thức số học đúng thì ghi vào file BAI_2.OUT dòng chữ “DUNG”
- Nếu xâu chỉ gồm các ký tự ( và ) nhưng không thể viết thêm một số toán hạng và dấu phép toán giữa các dấu đó để nhận được một biểu thức số học đúng thì ghi vào file BAI_2.OUT dòng chữ “KHONG DUNG”
Ví dụ về file input và output
BAI_2.IN
BAI_2.OUT
(((abc))
((()()))()
(()(()()))))
KHONG HOP LE
DUNG
KHONG DUNG
Bài 4: Để khảo sát một khu dân cư người ta phân tích số liệu từ ảnh chụp do vệ tinh gửi về. Bức ảnh chụp có kích thước NxM, được chia thành N hàng và M cột. Ta coi mỗi ngôi nhà có dạng hình chữ nhật. Ô (i,j) là ô thuộc dòng i cột j trong bức ảnh có giá trị 1 hoặc 0 tương ứng thuộc hoặc không thuộc vào một ngôi nhà. Các ô trong cùng một ngôi nhà đều có giá trị bằng 1. Biết rằng các ngôi nhà không có phần trùng nhau có nghĩa là 2 ô thuộc vào 2 ngôi nhà khác nhau không kề cạnh. Từ một bức ảnh cho trước, em hãy cho biết diện tích của ngôi nhà lớn nhất trong bức ảnh (mỗi ô là một đơn vị diện tích).
Dữ liệu vào từ tệp văn bản NHA.INP có cấu trúc:
- Dòng 1 chứa 2 số N và M (N và M nguyên dương và nhỏ hơn 100)
- Trong N dòng tiếp theo, mỗi dòng chứa M số 0 hoặc 1. Số thứ j của dòng i thể hiện giá trị của ô (i,j).
Dữ liệu đưa ra tệp văn bản NHA.OUT chứa một số duy nhất là diện tích ngôi nhà lớn nhất tìm được.
Ví dụ:	
NHA.INP
NHA.OUT
3 5
4
0 1 1 0 1
0 1 1 0 1
0 0 0 1 0