BARIC - Bò Ba-ri

Giới hạn
  • Thời gian: 0.2s
  • Bộ nhớ: 1536MB
  • Mã nguồn: 50000 bytes

Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.

Link đọc đề trên VNOJ

Học theo những gì đọc được từ một bài báo viết về việc tăng sản lượng sữa, Bessie đã biến mình trở thành một con bò Ba-ri bằng cách tìm hiểu về áp suất không khí để lấy lòng Farmer John.

Cô ta đã làm N phép đo (1 <= N <= 100) trong ngày. Để thuận tiện, chúng lần lượt được gọi là M_1, M_2, ..., M_N (M_i <= 1 000 000). Các phép đo được đánh số theo thứ tự Bessie thực hiện chúng.

Để thể hiện được những phân tích về áp suất khí quyển trong ngày, Bessie đang để tâm đến việc tìm một tập hợp con của các phép đo, biểu thị bởi K (1 <= K <= N) chỉ số s_j (trong đó 1 <= s_1 <= s_2 <= ... <= s_K <= N), thể hiện chính xác được toàn bộ các phép đo, tức là, giới hạn sai số trong khoảng cho phép.

Trong bất kì tập hợp các phép đo nào, một lỗi xuất hiện ở mỗi phép đo có vị trí:

  1. trước phép đo đầu tiên trong tập hợp;
  2. giữa hai phép đo liên tiếp trong tập hợp;
  3. sau phép đo cuối cùng trong tập hợp.

Tổng sai số của tập hợp đó được tính bằng tổng các lỗi trong các phép đo.

Cụ thể, với mỗi phép đó có chỉ số i mà không nằm trong tập hợp các phép đo đang xét:

  • Nếu i < s_1 , sai số được tính như sau: 2 * | M_i - M_(s_1) |
  • Nếu s_j < i < s_(j+1), sai số được tính như sau: | 2 * M_i - Sum(s_j, s_(j+1)) |
    • trong đó Sum(x,y) = M_x + M_y
  • Nếu s_K > i, sai số được tính như sau: 2 * | M_i - M_(s_K) |

Cho biết sai số tối đa là E (E <= 1 000 000), xác định số phần tử của tập hợp nhỏ nhất tạo ra sai số không vượt quá E.

Dữ liệu

Dòng 1: Chứa hai số nguyên cách nhau bởi khoảng trắng: N và E

Dòng 2..N+1: Dòng i+1 chứa số nguyên M_i 

Dữ liệu mẫu
4 20
10
3
20
40

Giải thích

Bessie tiến hành 4 phép đo; sai số tối đa cho phép là 20. 
Giá trị các phép đo lần lượt là: 10,3,20,40

Kết quả

Dòng 1: Hai số nguyên cách nhau bởi khoảng trắng: số phần tử của tập hợp các phép đo nhỏ nhất tạo ra sai số không vượt quá E và sai số tập hợp đó tạo ra. 

Kết quả mẫu
2 17

Giải thích
Chọn phép đo thứ hai và thứ tự là giải pháp tốt nhất, cho sai số là 17. 
Sai số trong phép đo thứ nhất là 2*|10-3|=14; 
sai số trong phép đo thứ hai là |2*20-(3+40)|=3.

  • Người up: paulmcvn
  • Nguồn bài: Usaco January 2009 - Gold Division Translated by khanhptnk