Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

BARIC - Bò Ba-ri

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.

Được gửi lên bởi:Duc
Ngày:2009-01-16
Thời gian chạy:0.200s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ERL GOSU JS-RHINO NODEJS PERL6 PYPY RUST SED VB.NET
Nguồn bài:Usaco January 2009 - Gold Division
Translated by khanhptnk

hide comments
2016-09-27 03:01:46
Code AC:
http://shink.in/rocE7
2016-05-24 10:58:30 Nguyen Cuong
ko để ý cmt làm mất 1 hit :'(
2015-11-15 15:06:32 Nguyễn Mai Phương
đừng nghe ông kia nói nhớ, phải in ra sai số nhỏ nhất! ==
2015-10-20 10:55:43
hy vọng giúp được cho mọi người : http://www.oni.vn/uR57W
2015-10-08 09:14:48
sol : http://www.oni.vn/Zp91g
code : http://www.oni.vn/6yrr5
2015-06-21 15:14:48 there's no salvation for me...
in ra sai số lớn nhất ms AC nhé
2014-06-14 17:57:56 a;slkfjasl;fkj
k có số âm chứ?
2011-10-09 14:44:44 Hoàng Hà
Nếu s_K > i, sai số được tính như sau: 2 * | M_i - M_(s_K) |

Phải là '<' chứ nhỉ
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.