Bài tập ngày 29/10
CHI PHÍ TÍNH TỔNG
Nộp bàiPoint: 10
Trên một máy tính đặc biệt, thời gian để thực hiện việc tính tổng của hai số nguyên dương trên máy tính là phụ thuộc vào độ lớn của chúng. Trung bình để cộng hai số nguyên dương a và b ta phải trả chi phí thời gian có giá trị bằng 5% giá trị của tổng hai số này (a + b). Giả sử ta cần phải tính tổng của N số nguyên dương cho trước. Dễ thấy là có nhiều cách tổ chức thực hiện công việc tính toán này, mỗi cách đòi hỏi chi phí thời gian khác nhau.
Chẳng hạn như cần tính tổng các số 10, 11, 12, 13. Ta có thể thực hiện lần lượt:
- Cộng 10 và 11 (mất chi phí 1.05),
- Kết quả thu được đem cộng với 12 (mất chi phí 1.65),
- Và cuối cùng cộng với 13 (mất chi phí 2.3).
Tổng chi phí theo cách thực hiện này là 5.
Một cách thực hiện khác là:
- Cộng 10 và 11 (1.05),
- Tiếp đến cộng 12 với 13 (mất chi phí 1.25),
- Cuối cùng cộng hai kết quả thu được (mất chi phí 2.3).
Như vậy chi phí tổng cộng theo cách thứ hai là 4.6.
Yêu cầu:
Cho dãy gồm N số nguyên dương. Cần tìm cách tính tổng của các số này với tổng chi phí thời gian là nhỏ nhất.
Dữ liệu vào:
- Dòng đầu tiên chứa số nguyên dương N (~2 ≤ N ≤ 15000~).
- Trong các dòng tiếp theo ghi N số nguyên dương mà ta cần tính tổng, hai số liên tiếp được ghi cách nhau bởi ít nhất một dấu cách hoặc dấu xuống dòng.
Dữ liệu ra:
Ghi ra tổng chi phí theo cách thực hiện tính tổng tìm được. Kết quả được ghi với hai chữ số sau dấu chấm thập phân.
Ví dụ:
SUMATION.INP
4
10 11 12 13
SUMATION.OUT
4.60
SUMATION.INP
2
3 3
SUMATION.OUT
0.30
SỐ NGUYÊN TỐ BỀN VỮNG
Nộp bàiPoint: 10
Số nguyên dương n gọi là số nguyên tố bền vững nếu n là số nguyên tố và bỏ đi bất kỳ k chữ số cuối của n thì số còn lại cũng là số nguyên tố, với 1 ≤ k < số chữ số của n.
Cho hai số nguyên dương X, Y, hãy tìm tất cả các số nguyên tố bền vững lớn hơn hoặc bằng X và nhỏ hơn hoặc bằng Y.
Dữ liệu vào:
một dòng gồm hai số nguyên dương X, Y.
Dữ liệu ra:
- Dòng đầu là số số nguyên tố bền vững lớn hơn hoặc bằng X và nhỏ hơn hoặc bằng Y;
- Dòng thứ hai là tất cả các số nguyên tố bền vững tìm được, giữa các số cách nhau một khoảng cách.
Ví dụ:
NguyenTo.inp
5 100
NguyenTo.out
11
5 7 23 29 31 37 53 59 71 73 79
Ràng buộc:
- ~1 ≤ X ≤ Y ≤ 10^9~
Các bộ test:
- 50% bộ test có ~1 ≤ X ≤ Y ≤ 10^5~
- 50% bộ test còn lại có ~10^5 < X ≤ Y ≤ 10^9~
