Cho dãy số nguyên ai, i=1,2,…,n. Dãy số này dùng để mã hoá các thông báo, mỗi thông báo có n bit. Nếu dãy bit của thông báo là t1,t2,…,tn (ti bằng 1 hoặc 0) thì nó được mã hoá thành số: S = t1a1 + t2a2 + … + tnan
Yêu cầu: Cho thông báo đã mã hoá và dãy số ai. Hãy giải mã thông báo.
Dữ liệu: Vào từ file văn bản cipher.inp:
- Dòng đầu tiên chứa số nguyên dương n (5 <= n <= 30);
- Dòng thứ i trong n dòng tiếp theo chứa số nguyên ai, tổng các ai không vượt quá 2×109
- Dòng thứ n+2 chứa số nguyên S – thông báo đã mã hoá, S <=a1 + a2 + … + an.
Kết quả: Đưa ra file văn bản cipher.out thông báo đã giải mã dưới dạng chuỗi bit. Dữ liệu vào đảm bảo có nghiệm.
Thuật toán - Với n giới hạn, ta có thể giải quyết bài toán bằng phương pháp vét cạn: xét tất cả các trạng thái có thể có của dãy bit thông báo, với mỗi trạng thái, kiểm tra xem sau khi mã hoá có khớp với S đã cho trước hay không, dãy bit cho kết quả mã hoá trùng với S chính là dãy cần tìm. - Dễ thấy, độ phức tạp để vét tất cả các xâu nhị phân có độ dài n là O(2n). Do đó với n lớn, thuật toán vét cạn cho chương trình chạy khá chậm. Dựa trên ý tưởng vét trên, ta có thể cải tiến thêm để chương trình chạy tốt hơn. Chia xâu n bit thành 2 phần, phần 1 gồm n/2 bit đầu tiên, phần 2 gồm n/2 bit còn lại. Trước tiên xét tất cả các trạng thái phần 1, có 2n/2 trạng thái (tối đa là 215) nên ta có thể lưu tất cả các trạng thái này lại, mỗi trạng thái lưu dưới dạng 1 số duy nhất là số mã hoá của phần 1. Sau đó, vét tiếp các trạng thái của phần 2, tương tự phần 1, có tối đa 215 trạng thái, ứng với mỗi trạng thái cũng có 1 số mã hoá. Dễ dàng nhận thấy, nếu tổng của số mã hoá của phần 1 và phần 2 bằng S, thì 2 trạng thái tương ứng ghép lại chính là trạng thái đúng của xâu n bit cần tìm. Bài toán đưa về việc tìm 2 số thuộc 2 dãy có tổng bằng số S cho trước. Ứng với mỗi số mã hoá của phần 2 tìm được, ta tìm nhị phân trên dãy số mã hoá của phần 1 đã lưu để xác định trạng thái cho tổng số mã hoá là S. Như vậy ta đã thực hiện 2 lần bước vét các trạng thái của xâu nhị phân độ dài n/2, độ phức tạp là O(2n/2), và 2n/2 lần vét nhị phân trên mảng gồm 2n/2 phần tử, độ phức tạp là O(2n/2 x log2n/2). Độ phức tạp giảm đáng kể và cho chương trình chạy trong thời gian chấp nhận được. Download chương trình (cipher.pas) Dãy số trung bình
Tháng Tư 10, 2007 lúc 3:52 chiều (HỌC HÀNH)
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ớ.
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<m3, s4<m4, …, sn < mn ta cũng suy ra được các giới hạn khác của a. Tuy nhiên, chỉ có hai dạng chung là: 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)
|
