OLYMPIC 2016 - K10

SỞ GIÁO DỤC VÀ ĐÀO TẠO TỈNH KIÊN GIANG -------------	KỲ THI OLYMPIC LỚP 10 NĂM HỌC 2015-2016 -----------------------
ĐỀ CHÍNH THỨC (Đề thi gồm 02 trang)	MÔN: TIN HỌC Thời gian làm bài: 180 phút (không kể thời gian giao đề) Ngày thi: 24/4/2016

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ả	Điểm
Bài 1	Tổng các chữ số	TONG.PAS	TONG.INP	TONG.OUT	5
Bài 2	Min-Max	MINMAX.PAS	MINMAX.INP	MINMAX.OUT	5
Bài 3	Tìm chuỗi	CHUOI.PAS	CHUOI.INP	CHUOI.OUT	5
Bài 4	Cặp số	CAPSO.PAS	CAPSO.INP	CAPSO.OUT	5

Thí sinh lập trình giải các bài toán sau, lưu bài thi vào thư mục có tên là số báo danh:

Bài 1: Tổng các chữ số.

Cho một số nguyên dương N (N ≤ 99999).

Yêu cầu: tính tổng các chữ số của N.

Dữ liệu vào: từ tập tin TONG.INP có một dòng duy nhất chứa số nguyên dương N.

Dữ liệu ra: lưu vào tập tin TONG.OUT có một số duy nhất là tổng các chữ số của N

Ví dụ:

TONG.INP	TONG.OUT
3572	17

Bài 2:  Min-Max.

Cho một mảng 2 chiều kích thước nxm, giá trị các phần tử của mảng là số nguyên dương m bất kỳ (n,m ≤ 100).

Yêu cầu: hãy tìm giá trị lớn nhất và giá trị nhỏ nhất trong mảng đã cho.

Dữ liệu vào: từ tập tin MINMAX.INP gồm có:                   

-         Dòng 1 là số nguyên dương n.

-         n dòng tiếp theo mỗi dòng gồm n số nguyên dương.

Dữ liệu ra: lưu vào tập tin MINMAX.OUT gồm có:

-         Dòng 1 ghi số có giá trị nhỏ nhất tìm được.

-         Dòng 2 ghi số có giá trị lớn nhất tìm được.

Ví dụ:

MINMAX.INP	MINMAX.OUT
3 2 4 5 3 2 7 4 7 8	2 8

Bài 3: Kiểm tra chuỗi.

Cho một tập tin văn bản có n dòng (3 ≤ n ≤ 30000), mỗi dòng là một chuỗi s có tối đa 255 ký tự, các ký tự s[i] Î [‘a’,…,’z’] với 1 ≤ i ≤ length(s). Trong đó chỉ có duy nhất một chuỗi s có số lần xuất hiện là một số lẻ, các chuỗi khác có số lần xuất hiện là một số chẵn.

Yêu cầu: hãy tìm chuỗi s (có số lần xuất hiện là một số lẻ) đó.

Dữ liệu vào: từ tập tin CHUOI.INP gồm có:

-         Dòng đầu là một số nguyên n.

-         n dòng tiếp theo mỗi dòng là một chuỗi ký tự.

Dữ liệu ra: lưu vào tập tin CHUOI.OUT chứa chuỗi ký tự tìm được.

Ví dụ:

CHUOI .INP	CHUOI .OUT
7 ha tien phu quoc rach gia chau thanh ha tien chau thanh phu quoc	rach gia

Bài 4: Cặp số.

Cho dãy số nguyên dương có N phần tử (a1,a2,…,an ) và một số nguyên dương X.

Yêu cầu: hỏi có bao nhiêu cặp số liền kề (tính từ trái qua phải) có tổng gần X nhất? Biết rằng có tất cả n-1 cặp số trong dãy số.

Dữ liệu vào: từ tập tin CAPSO.INP gồm có 2 dòng:

-         Dòng thứ nhất: số nguyên đầu tiên là n (1 ≤ n ≤ 1000) là số phần tử của dãy Avà số nguyên dương X (1 ≤ X ≤ 10000).

-         Dòng thứ hai gồm n số nguyên a₁, a₂,..., a_n (1 ≤ a_i ≤ 100) là các phần tử của dãy A.

Dữ liệu ra: lưu vào tập tin CAPSO.OUT có một số nguyên duy nhất là số cặp số liền kề có tổng gần X nhất.

Ví dụ:

CAPSO.INP	CAPSO.OUT	Giải thích thêm
4 3 1 2 2 1	2	Cặp 1 2 Cặp 2 1
CAPSO.INP	CAPSO.OUT
5 3 1 1 4 3 1	1	Cặp 1 1 Cặp 31

---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.

OLYMPIC 2016 - K11

SỞ GIÁO DỤC VÀ ĐÀO TẠO TỈNH KIÊN GIANG -------------	KỲ THI OLYMPIC LỚP 11 NĂM HỌC 2015-2016 -----------------------
ĐỀ CHÍNH THỨC (Đề thi gồm 02 trang)	MÔN: TIN HỌC Thời gian làm bài: 180 phút (không kể thời gian giao đề) Ngày thi: 24/4/2016

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ả	Điểm
Bài 1	Giải nén	GIAINEN.PAS	GIAINEN.INP	GIAINEN.OUT	5
Bài 2	Chuyển đổi hệ đếm	HEDEM.PAS	HEDEM.INP	HEDEM.OUT	5
Bài 3	Bò sữa	BOSUA.PAS	BOSUA.INP	BOSUA.OUT	5
Bài 4	Hoán vị	HOANVI.PAS	HOANVI.INP	HOANVI.OUT	5

Thí sinh lập trình giải các bài toán sau, lưu bài thi vào thư mục có tên là số báo danh:

Bài 1: Giải nén.       

Để bảo mật dữ liệu và tiết kiệm dung lượng lưu trữ dữ liệu trong bộ nhớ máy tính. Người ta thường nén dữ liệu ban đầu (dữ liệu gốc) về một dạng khác (dữ liệu nén). Có rất nhiều phương pháp chuyển đổi từ dữ liệu gốc về dữ liệu nén, quá trình chuyển đổi đó gọi là nén dữ liệu, tương tự quá trình chuyển từ dữ liệu nén về dữ liệu gốc gọi là giải nén. Phương pháp nén và giải nén được mô tả như sau:

-         Nén:  ‘aaaabbb’ thành ‘4a3b’

-         Giải nén: ‘4a3b’ thành ‘aaaabbb’

Cho xâu ký tự B (dữ liệu nén) gồm các ký tự thuộc tập 'a'..'z', ‘0’..’9’. Biết rằng xâu đã giải nén A (dữ liệu gốc) có chiều dài ≤ 255.

Yêu cầu: hãy giải nén xâu B về xâu A theo phương pháp giải nén mô tả ở trên.

Dữ liệu vào: từ tập tin GIAINEN.INP gồm một xâu B (dữ liệu nén). 

Dữ liệu ra: lưu vào tập tin GIAINEN.OUT là một xâu A (dữ liệu gốc).

Ví dụ:

GIAINEN.INP	GIAINEN.OUT
1a3c5b	acccbbbbb

Bài 2: Chuyển đổi hệ đếm.

            Tất cả các loại thông tin khi được đưa vào bộ nhớ máy tính gọi là dữ liệu. Đối với thông tin dạng số có thể được biểu diễn bởi một trong các hệ đếm (hệ thập phân, hệ nhị phân, hệ thập lục phân). Cho trước các dãy số nhị phân (độ lớn 1 byte).

Yêu cầu: chuyển đổi các số nhị phân đã cho sang hệ đếm thập lục phân tương ứng. Biết rằng phương pháp chuyển đổi theo quy tắc lần lượt chọn 4 bit từ phải sang trái trong dãy nhị phân và chuyển chúng sang hệ thập phân, nếu số thập phân tìm được lớn hơn hoặc bằng 10 thì ghi một trong các ký tự từ ‘A’..’F’ tương ứng.

Dữ liệu vào: từ tập tin HEDEM.INP gồm có:

-         Dòng đầu là số nguyên dương n (1 ≤ n ≤ 100), là số lượng các dãy số nhị phân.

-         n dòng tiếp theo, mỗi dòng là 1 dãy số nhị phân tương ứng.

Dữ liệu ra: lưu vào tập tin HEDEM.OUT gồm: n dòng, mỗi dòng biểu diễn một số trong hệ đếm thập lục phân tương ứng.

Ví dụ :

HEDEM.INP	HEDEM.OUT
3 11001101 00111010 01010111	CD 3A 57

           

Bài 3: Bò sữa.

Bác nông dân nuôi đàn bò gồm n con bò sữa (1 ≤ n ≤ 100). Bằng kinh nghiệm của mình bác tính toán được con bò thứ i có a_i lít sữa (1 ≤ i ≤ n). Tuy nhiên đàn bò của bác có đặc tính là cứ mỗi lần vắt sữa một con, những con còn lại bị giảm sản lượng mỗi con 01 lít sữa (nếu vắt sữa con bò thứ nhất, n-1 con còn lại bị giảm sản lượng; sau đó vắt sữa con bò thứ hai thì n-2 con bò còn lại bị giảm sản lượng...)

Yêu cầu: hãy giúp bác nông dân tìm một phương án vắt sữa sao cho tổng lượng sữa thu được sau khi vắt sữa của đàn bò là lớn nhất.

Dữ liệu vào: từ tập tin BOSUA.INP gồm có:

-         Dòng thứ nhất là số nguyên dương n là số lượng con bò của đàn bò.

-         Dòng thứ hai gồm n số nguyên không âm a₁, a₂,..., a_n (0 ≤ a_i ≤ 1000) là lượng sữa của các con bò tương ứng.

Dữ liệu ra: lưu vào tập tin BOSUA.OUT là một số nguyên dương duy nhất chỉ lượng sữa nhiều nhất mà bác nông dân có thể vắt được.

Ví dụ:

BOSUA.INP	BOSUA.OUT
4 2 1 4 3	6

Bài 4: Hoán vị.

Một hoán vị của {a1,a2,…,an} được gọi là hoán vị đầy đủ nếu a_i ≠ i, với mọi i =1,2, …,n. Cho một số nguyên dương n.

Yêu cầu: tìm tất cả các hoán vị đầy đủ của tập  {a1,a2,…,an}.

Dữ liệu vào: từ tập tin HOANVI.INP gồm có 1 số nguyên dương n.

Dữ liệu ra: lưu vào tập tin HOANVI.OUT gồm các dòng là các hoán vị tìm được, dòng cuối cùng là số lượng các hoán vị.

            Ví dụ:

HOANVI .INP	HOANVI .OUT
3	2 3 1 3 1 2 So hoan vi=2

---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.