|
Hôm nay nhé!
|
Quý vị chưa đăng nhập hoặc
chưa đăng ký làm thành viên, vì vậy chưa thể tải
được các tư liệu của Thư viện về máy tính của
mình.
Nếu chưa đăng ký, hãy
đăng ký thành viên tại
đây hoặc xem phim
hướng dẫn tại đây
Nếu đã đăng ký rồi, quý vị
có thể đăng nhập ở ngay ô bên phải.
Bai toan Day so trung binh
- 0 / 0
-
Nguồn: ST
Người gửi: Nguyễn Văn Hải (trang riêng)
Ngày gửi: 11h:23' 10-02-2011
Dung lượng: 29.0 KB
Số lượt tải: 6
Người gửi: Nguyễn Văn Hải (trang riêng)
Ngày gửi: 11h:23' 10-02-2011
Dung lượng: 29.0 KB
Số lượt tải: 6
Số lượt thích:
0 người
Bài toán: Dãy số trung bình
Tìm các dãy số trong dãy số nguyên cho trước nhận dãy số m đã cho làm dãy số trung bình....
Đề bài: Xét dãy số nguyên không giảm S1, S2, ..., Sn+1 (Si <= Si+1). Dãy m1, m2, ...mn được xác định bởi công thức mi = (si + si+1)/2 (1<=i<=n) gọi là dãy trung bình của dãy S. Ở đây ta chỉ xét trường hợp mi là số nguyên. Cho trước dãy m, nhiệm vụ của bạn là tìm tất cả những dãy S nhận dãy m làm dãy trung bình
Input: Dữ liệu vào từ file Mean.inp gồm
Dòng đầu tiên chứa số nguyên N (1<=N<=5 000 000)
N dòng sau, dòng thứ i chứ số nguyên mi(1<=mi<=1 000 000 000)
Output: Dữ liệu ra ghi lên file Mean.out gồm một số nguyên duy nhất là số lượng dãy S thỏa yêu cầu đề bài mà bạn tìm được
Ràng buộc: Chương trình không được phép sử dụng quá 16MB bộ nhớ.
MEAN.INP
MEAN.OUT
3 2 5 9
4
Thuật toán: Từ công thức mi = (si + si+1)/2 ta có mi >= si. Bản chất của bài toán thật ra là yêu cầu ta tìm tập giá trị của s1 mà thôi vì khi có s1 ta có thể tính ra toàn bộ dãy s theo công thức của dãy m: si+1 = 2mi-1-si.
Đặt s1 = a, ta có s2 = 2m1 - a <= m2 <=> a>= 2m1 - m2. Tương tự, với các bất đẳng thức s3 a >= x
a <= y
Gọi Xmaxlà giá trị lớn nhất trong số các cận dưới của a, Ymin là giá trị nhỏ nhất trong số các cận trên của A. Khi đó, dãy số S thỏa yêu cầu đề bài là Ymin - Xmax + 1. Độ phức tạp của thuật toán chỉ là O(n)!
Download chương trình (mean.pas) Theo tin học và tuổi trẻ
Tìm các dãy số trong dãy số nguyên cho trước nhận dãy số m đã cho làm dãy số trung bình....
Đề bài: Xét dãy số nguyên không giảm S1, S2, ..., Sn+1 (Si <= Si+1). Dãy m1, m2, ...mn được xác định bởi công thức mi = (si + si+1)/2 (1<=i<=n) gọi là dãy trung bình của dãy S. Ở đây ta chỉ xét trường hợp mi là số nguyên. Cho trước dãy m, nhiệm vụ của bạn là tìm tất cả những dãy S nhận dãy m làm dãy trung bình
Input: Dữ liệu vào từ file Mean.inp gồm
Dòng đầu tiên chứa số nguyên N (1<=N<=5 000 000)
N dòng sau, dòng thứ i chứ số nguyên mi(1<=mi<=1 000 000 000)
Output: Dữ liệu ra ghi lên file Mean.out gồm một số nguyên duy nhất là số lượng dãy S thỏa yêu cầu đề bài mà bạn tìm được
Ràng buộc: Chương trình không được phép sử dụng quá 16MB bộ nhớ.
MEAN.INP
MEAN.OUT
3 2 5 9
4
Thuật toán: Từ công thức mi = (si + si+1)/2 ta có mi >= si. Bản chất của bài toán thật ra là yêu cầu ta tìm tập giá trị của s1 mà thôi vì khi có s1 ta có thể tính ra toàn bộ dãy s theo công thức của dãy m: si+1 = 2mi-1-si.
Đặt s1 = a, ta có s2 = 2m1 - a <= m2 <=> a>= 2m1 - m2. Tương tự, với các bất đẳng thức s3
a <= y
Gọi Xmaxlà giá trị lớn nhất trong số các cận dưới của a, Ymin là giá trị nhỏ nhất trong số các cận trên của A. Khi đó, dãy số S thỏa yêu cầu đề bài là Ymin - Xmax + 1. Độ phức tạp của thuật toán chỉ là O(n)!
Download chương trình (mean.pas) Theo tin học và tuổi trẻ
Các ý kiến mới nhất