Đề thi Tin học trẻ Vĩnh Phúc 2014

HỘI THI TIN HỌC TRẺ
TỈNH VĨNH PHÚC
LẦN THỨ IX - NĂM 2014
ĐỀ THI PHẦN LẬP TRÌNH - BẢNG B
Thời gian làm bài: 120 phút, không kể thời gian giao đề
————————————


TỔNG QUAN
STT
Tên bài
File chương trình
File dữ liệu
File kết quả
Điểm
Thời gian

1
Tìm số
Snumber.***
Snumber.Inp
Snumber.Out
40
1s/test

2
Khôi phục xâu
Cstring.***
Cstring.Inp
Cstring.Out
30
1s/test


Lưu ý:
Thí sinh thay “.***” bằng “.PAS” hoặc “.CPP” tuỳ thuộc theo ngôn ngữ lập trình mà thí sinh lựa chọn là Turbo Pascal (Free Pascal) hoặc C/C++;
Thí sinh đặt đúng tên file theo yêu cầu;
Đề thi có 02 trang.

Lập chương trình giải các bài toán sau:
Bài 1: TÌM SỐ
Ứng với mỗi số tự nhiên x, ta có số tự nhiên
bằng tổng bình phương các chữ số của x. Từ x ta xây dựng dãy
như sau:

với
.
Ví dụ:
với x = 195 ta có dãy:
195, 107, 50, 25, 29, 85, 89, 145, 42, 20, 4, 16, 37, 58, 89
với x = 1890 ta có dãy:
1890, 146, 53, 34, 25, 29, 85, 89, 145, 42, 20, 4, 16, 37, 58, 89
Dãy kết thúc khi phần tử vừa sinh ra trùng với một phần tử bất kỳ trước đó.
Yêu cầu:
Cho trước hai số
. Hãy tìm các số tự nhiên x
sao cho từ x ta có thể xây dựng được dãy
dài nhất.
Dữ liệu vào: (Snumber.Inp)
Dòng 1: Ghi hai số a, b cách nhau một dấu cách.
Dữ liệu ra: (Snumber.Out)
Dòng 1: Ghi 1 số là độ dài lớn nhất của một dãy số có thể xây dựng được.
Dòng 2: Ghi các số tự nhiên x tìm được theo thứ tự tăng dần, mỗi số cách nhau một dấu cách.
Ví dụ:
Input
Output
Giải thích

100 200
19
112 121
- Độ dài dãy số dài nhất là 19, có 2 số thoả mãn là 112 và 121.
- Với x=112 ta có dãy:
112, 6, 36, 45, 41, 17, 50, 25, 29, 85, 89, 145, 42, 20, 4, 16, 37, 58, 89
- Với x=121 ta có dãy:
121, 6, 36, 45, 41, 17, 50, 25, 29, 85, 89, 145, 42, 20, 4, 16, 37, 58, 89



Bài 2: KHÔI PHỤC XÂU
Cho một xâu gồm n cặp kí tự, mỗi cặp có kí tự “V” và kí tự “P”. Các cặp kí tự đặt trong xâu theo nguyên tắc rời nhau hoặc lồng vào nhau, không có trường hợp hai cặp kí tự giao nhau; trong các cặp, kí tự “V” luôn đứng trước kí tự “P”.
Ví dụ: Xâu có 10 cặp kí tự “VP”:


Người ta mã hoá thông tin của xâu bằng cách ghi số kí tự nằm trong các cặp kí tự theo thứ tự từ trái qua phải. Theo ví dụ trên, ta có dãy số: 12 6 0 0 0 0 0 4 0 0.
Lần lượt từ trái qua phải, có 12 kí tự nằm trong cặp thứ nhất; có 6 kí tự nằm trong cặp thứ 2; không có kí tự nào trong các cặp thứ 3, 4, 5, 6, 7; có 4 kí tự nằm trong cặp thứ 8; không có kí tự nào nằm trong cặp thứ 9, 10.
Yêu cầu:
Cho dãy số mã hoá xâu kí tự, hãy khôi phục lại xâu ban đầu.
Dữ liệu vào: (Cstring.Inp)
- Dòng 1: Ghi số tự nhiên
.
- Dòng 2: Ghi n số tự nhiên, là dãy số mã hoá, mỗi số có giá trị không quá 100.
Dữ liệu vào đảm bảo luôn đúng, xâu khôi phục có độ dài không quá 250 kí tự.
Dữ liệu ra: (Cstring.Out)
Ghi xâu sau khi khôi phục.
Ví dụ:

Input
Output

10
12 6 0 0 0 0 0 4 0 0
VVVPVPVPPVPVPPVVPVPP


=Hết=

(Cán bộ coi thi không giải thích gì thêm)















Họ và tên thí sinh:…………………………………………SBD:…………………….