Cac de thi hoc sinh gioi cap tinh

Sở GD-ĐT Quảng Ninh
Kỳ thi chọn học sinh giỏi cấp tỉnh


 Lớp 12 THPT năm học 2005-2006



Môn: Tin Học – Bảng A
Số báo danh:


Thời gian: 180 phút (Không kể thời gian giao đề)
Chữ ký của giám thị số 1


Ngày thi: 26/11/2005







Tổng quan về bài thi
Tên bài
File chương trình
File vào
File ra
Giới hạn thời gian

Bài 1
PPRIME.PAS
PPRIME.IN
PPRIME.OUT
0,5 giây / 1 test

Bài 2
PIMP.PAS
PIMP.IN
PIMP.OUT
1 giây / 1 test



Hãy lập trình giải các bài toán sau:

Bài 1. Prime Palindromes
Số 151 là số nguyên tố đối xứng bởi vì nó vừa là số nguyên tố và vừa là số đối xứng (số đối xứng là số mà khi ta viết các chữ số của nó từ trái sang phải, hay từ phải sang trái đều cho cùng một số). Bạn hãy viết một chương trình tìm tất cả các số nguyên tố đối xứng nằm trong đoạn [a; b]

Dữ liệu: File vào gồm một duy nhất dòng, chứa đúng hai số nguyên a và b, ghi cách nhau bởi một dấu cách.

Kết quả: File ra ghi các số nguyên tố đối xứng nằm trong đoạn [a; b] theo thứ tự tăng dần, mỗi số viết trên một dòng. Nếu có nhiều hơn 10 số thì chương trình của bạn chỉ cần đưa ra 10 số đầu tiên. Tiếp theo là một dòng trắng. Dòng cuối cùng ghi số lượng các số nguyên tố đối xứng trong nằm đoạn [a; b]. Trong trường hợp không có số nguyên tố đối xứng nào nằm trong đoạn [a; b] thì file ra chỉ ghi đúng một số 0.

Ví dụ:
PPRIME.IN
PPRIME.OUT

5 500
5
7
11
101
131
151
181
191
313
353

12

12 100
0



Bài 2. Pimp My Ride
Hôm nay, bạn có nhiệm vụ tân trang lại một số ô tô, xe máy, xe tải và các phương tiện khác. Tất nhiên có quá nhiều việc phải làm, vì vậy bạn muốn thuê các xưởng sửa chữa làm các công việc khác nhau như sơn, trang trí nội thất, ... Không may, các xưởng đó lại rất chuyên môn hoá, cho nên bạn phải thuê các xưởng khác nhau cho các công việc khác nhau. Hơn nữa, họ có xu hướng lấy tiền của bạn nhiều lên khi tổng thể xe của bạn tốt lên. Chẳng hạn, người thợ sơn có thể đòi tiền nhiều hơn đối với một ô tô mà toàn bộ nội thất làm bằng da. Do đó “tiền trả thêm” phụ thuộc vào công việc nào được làm và các công việc nào đã được làm trước đó. Hiện tại bạn đang muốn tiết kiệm tiền bằng cách tìm một thứ tự tốt nhất cho các công việc.

Các công việc riêng lẻ được đánh số từ 1 đến n. Cho giá gốc p của mỗi công việc và tiền trả thêm s (tính theo đơn vị đồng) đối với mỗi cặp công việc (i, j) với nghĩa là bạn phải trả thêm s đồng cho công việc i nếu và chỉ nếu công việc j đã được làm xong trước đó. Bạn cần phải tính tổng giá tiền nhỏ nhất để hoàn thành tất c