Đề thi đề xuất môn Tin 10 – THPT – Năm học 2013 - 2014

ĐỀ THI ĐỀ XUẤT MÔN TIN 10 – THPT – NĂM HỌC 2013 - 2014
Tổng quan đề thi:
Tên bài
File chương trình
File dữ liệu
File kết quả
Thời gian
Bài 1.
funmachi.*
funmachi.inp
gunmachi.oup
1 giây
Bài 2.
proddigi.*
proddigi.inp
proddigi.out
1 giây
Bài 3.
cost.*
cost.inp
cost.out
1 giây
Chú ý: Thí sinh thay * trong file chương trình là PAS hoặc CPP tùy theo ngôn ngữ lập trình mà thí sinh sử dụng là PASCAL hoặc C/C++.
Lập chương trình giải các bài toán sau đây.
Bài 1: Chiếc máy thú vị
Một ngày đẹp trời, Bờm bỗng dưng có được một cái máy rất thú vị! Nó có màn hình rất lớn và chỉ có 1 nút bấm. Khi Bờm tìm thấy nó, màn hình đang hiển thị duy nhất một ký tự là A. Sau khi Bờm bấm vào cái nút, ký tự đó chuyển thành B. Sau một vài lần bấm nút, từ ký tự B chuyển thành BA, sau đó chuyển thành BAB, và chuyển thành BABBA... Khi nhìn thấy dãy ký tự đó, Bờm nhận thấy rằng cái máy chuyển đổi ký tự theo cách là từ B chuyển thành BA và từ A chuyển thành B. 
Có vẻ thích thú với cái máy, Bờm hỏi bạn một câu hỏi khó: Sau K lần bấm nút, có bao nhiêu ký tự A và ký tự B sẽ được hiển thị trên màn hình?
Dữ liệu:
Một dòng duy nhất ghi số K1≤k≤45
Kết quả:
Một dòng duy nhất ghi 2 số nguyên cách nhau bởi một dấu cách thỏa mãn yêu cầu đề bài.
Ví dụ:
input
output
4
2 3
Bài 2. Tích các chữ số.
	Cho số nguyên N (0≤N≤109), tìm số tự nhiên Q nhỏ nhất sao cho tích của tất cả các chữ số trong Q thì bằng N.
	Dữ liệu: Một dòng duy nhất ghi số N(0≤N≤109)
	Kết quả: In ra số Q tìm được, nếu không tìm được số Q thỏa mãn yêu cầu, in ra -1.
Ví dụ:
input
output
10
25
Bài 3. Chi phí
	Cho dãy số nguyên a1, a2, . . ., an (0 ≤ ai ≤ 109, 1 ≤ n ≤ 106). Với dãy số nguyên này ta có thể thực hiện phép xử lý Reduce(i) thay thế 2 phần tử ai và ai+1 bằng max{ai, ai+1} với chi phí là max{ai, ai+1}. 
Sau n-1 lần thực hiện phép xử lý trên, ta được dãy số độ dài 1. Chi phí biến đổi dãy được tính bằng tổng chi phí của tất cả các phép xử lý đã thực hiện.
Yêu cầu: Cho n và các số ai. Hãy xác định chi phí nhỏ nhất đưa dãy về độ dài bằng 1.
Dữ liệu: Gồm n+1 dòng:
Dòng đầu tiên chứa số nguyên n,
Dòng thứ i trong n dòng tiếp theo chứa số nguyên ai.
Kết quả: In ra một số nguyên – chi phí biến đổi tìm được.
Ví dụ:
input
output
3
1
2
3
5