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.