De thi tren may C

Hội thi Tin học trẻ tỉnh Quảng Ninh lần thứ IX-2008
ĐỀ THI TRÊN MÁY BẢNG C - THPT
Ngày thi: 25-6-2008
Thời gian làm bài: 150 phút
(Đề thi gồm 02 trang)

TỔNG QUAN VỀ ĐỀ THI
Bài toán
File chương trình
File vào
File ra
Giới hạn thời gian

Bài 1
bond.pas
bond.in
bond.out
1 giây / 1 test

Bài 2
pencil.pas
pencil.in
pencil.out
1 giây / 1 test

Bài 3
keys.pas
keys.in
keys.out
1 giây / 1 test


Bài 1. An Encrypted Message for James Bond
Điệp viên 007 (James Bond) có một nét đặc trưng riêng là các tài liệu của ông luôn được mã hóa. Nếu ông ta nhận được một thông báo đã được mã hóa bằng một xâu chỉ gồm các chữ số và có chứa bình phương của một số tự nhiên n nào đó (1 < n ≤ 10.000) thì ông ta trở nên hoang mang và điều này đôi khi làm giảm đáng kể khả năng làm việc của ông ta. Để tránh điều này, ông X đề xuất hành động như sau: Tìm bình phương của một số tự nhiên n2 (ở đó n là một số tự nhiên như mô tả ở trên) ở bên trái nhất trong thông báo mã hóa và thay thế nó bởi số n. Nếu có nhiều hơn bình phương của một số nguyên cùng bắt đầu tại vị trí trái nhất thì chọn số bình phương nhỏ nhất trong số chúng. Một bình phương của một số là không được bắt đầu với chữ số 0. Sau đó lặp lại hành động này với thông báo mã hóa mới cho đến khi không có một bình phương của số nguyên nào nằm trong đoạn cho trước trên trong thông báo mã hóa còn lại.

Công việc của bạn là viết một chương trình thực hiện thuật toán của ông X đề xuất.

Dữ liệu: Dòng đầu tiên của file vào chứa một xâu chỉ gồm các chữ số và không chứa bất kỳ dấu cách nào của thông báo mã hóa. Xâu này chứa ít nhất là 1 và nhiều nhất là 250 chữ số. Chữ số đầu tiên của xâu không là chữ số 0.

Kết quả: File ra gồm một dòng chứa xâu đã được sửa bởi thuật toán của ông X.

Ví dụ:
bond.in
bond.out

734424
268

8136045
605



Bài 2. Pencil Factory
Ở một nhà máy sản xuất bút chì, các bút chì được sản xuất theo cách sau: đầu tiên nó được sơn ở máy sơn, rồi ngay sau đó nó được chuyển tới máy đánh véc ni. Tuy nhiên không máy nào trong số hai máy này được điều chỉnh một cách hợp lý. Máy sơn sẽ không sơn một cái bút chì sau khi đã sơn n cái bút chì. Bên cạnh đó, máy đánh véc ni sẽ không đánh véc ni một cái bút chì sau khi đã đánh véc ni m cái bút chì. Vì vậy mà nhà máy đã sản xuất ra 4 loại bút chì: một loại hoàn thiện tức là được đánh cả sơn và véc ni; một loại không được sơn và cũng không được đánh véc ni; một loại được sơn nhưng chưa đánh véc ni và một loại được đánh véc ni nhưng không được sơn và.

Công việc của bạn là viết một chương trình được cho trước n, m và k (k là số bút chì đã được sản xuất) và tính số bút chì thuộc mỗi loại trên. Ví dụ, nếu n = 3, m = 5 và k = 17 thì việc xử lý các bút chì được minh họa qua bảng dưới đây là việc xử lý đã hoàn thành, là việc xử lý chưa hoàn thành):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

Sơn


















Véc ni



















Trong ví dụ trên, chỉ có 12 trong số 17 bút chì là được xử lý đầy đủ. Một cái bút chì (cái thứ 12) là không được xủ lý một công đoạn nào cả. Một cái bút chì (cái thứ 6) là được sơn nhưng không được đánh véc ni. Ba cái bút chì (cái thứ 4, 8 và 16) được đánh véc ni nhưng không được sơn.

Dữ liệu: File vào gồm một dòng chứa 3 số tự nhiên n, m, k (0 < n < 106, 0 < m < 106, 0 <