CHO ĐỘI TUYỂN HSG

ĐỀ 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ờmbỗ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ờmhỏ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ố 𝐾
1≤𝑘≤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≤𝑁
10
9tìm số tự nhiên 𝑄 nhỏ nhất sao cho tích của tất cả các chữ số trong 𝑄 thì bằng 𝑁.
Dữ liệu:Một dòng duy nhất ghi số 𝑁(0≤𝑁
10
9)
Kết quả:In ra số được, nếu không tìm được số 𝑄 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