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.|

VCOWCAR - Xe ô tô của bò

Hiện tại, bài tập này đã có trên online judge chính thức của VNOI, bạn có thể truy cập ở đây: https://oj.vnoi.info/problem/vcowcar


N (1 <= N <= 50,000) con bò đánh số từ 1..N đang lái trên các chiếc xe khác nhau dọc theo đường cao tốc ở Xứ Bò. Bò i có thể lái ở bất kỳ làn đường nào trong số M (1 <= M <= N) làn đường cao tốc và có thể lái xe ở tốc độ tối đa là S_i (1 <= S_i <= 1,000,000) km/giờ.

Từ kinh nghiệm đụng xe khá nhiều, các con bò rất ghét đụng nhau và tiến hành các đo đạc để tránh đụng nhau. Trên đường cao tốc này, bò i sẽ giảm tốc độ của mình đi D (0<= D <= 5,000) km/giờ nếu có một con bò đang đi trước nó (tất nhiên là không bao giờ tốc độ của bò i nhỏ hơn 0 km/giờ cả). Như vậy, nếu có K con bò đi trước bò i thì bò i sẽ đi với tốc độ tối đa là max[S_i - D * K, 0].

Nếu một con bò đi nhanh hơn con bò ở ngay phía trước nó thì đảm bảo rằng các con bò cách nhau đủ xa để tai nạn không xảy ra khi các con bò giảm tốc độ (nhưng nếu sau khi giảm tốc độ mà bò đi sau vẫn phóng nhanh hơn bò đi trước thì sẽ xảy ra tai nạn).

Xứ bò cũng có một điều luật về giao thông đó là tốc độ của bò đi trên đường cao tốc tối thiểu phải là L (1 <= L <= 1,000,000) km/giờ, bởi vậy mà đôi khi vài con bò sẽ không thể tham gia giao thông vì phải tuân thủ luật giao thông. Bạn hãy viết chương trình tính xem tối đa có bao nhiêu con bò có thể đi trên đường cao tốc mà vẫn tuân thủ luật giao thông.

Dữ liệu

  • Dòng 1: 4 số nguyên cách nhau bởi dấu cách: N, M, D, và L
  • Dòng 2..N+1: Dòng i+1 mô tả tốc độ ban đầu của bò i là 1 số nguyên: S_i

Kết quả

  • Dòng 1: Một số nguyên cho biết số lượng bò nhiều nhất có thể tham gia giao thông.

Ví dụ

Dữ liệu
3 1 1 5
5
7
5

Giải thích:
Có 3 con bò và chỉ có một làn đường để đi, độ giảm tốc độ 
là 1 km/giờ và tốc độ tối thiểu phải đạt là 5 km/giờ.

Kết quả
2

Giải thích:
Tối đa 2 con bò là tham gia giao thông được, cách chọn 
là chọn 2 bò đầu tiên.

Được gửi lên bởi:Jimmy
Ngày:2008-05-24
Thời gian chạy:1s
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 US-Open 2008 - Bảng Bạc

hide comments
2015-07-31 14:21:01 N�ng D�n John
http://nhatkynghiencuu.blogspot.com/2015/07/xe-o-to-cua-bo-ma-vcowcar-spoj.html
2015-07-31 14:20:20 N�ng D�n John
Mấy con bò này muốn chết mà, chạy gì mà 1triệu km/h, ôi trời, xe thế kỉ 22 =)))
2013-11-15 16:51:52 a;slkfjasl;fkj
cũng khoai đấy ta :(
2012-04-16 11:37:20 2ez
van chua AC chan'
:((
2012-03-01 06:59:50 Tmbao
Đề có câu "Nếu một con bò đi nhanh hơn con bò ở ngay phía trước nó thì đảm bảo rằng các con bò cách nhau đủ xa để tai nạn không xảy ra khi các con bò giảm tốc độ (nhưng nếu sau khi giảm tốc độ mà bò đi sau vẫn phóng nhanh hơn bò đi trước thì sẽ xảy ra tai nạn)." Lừa tình vãi @@

Last edit: 2012-03-01 07:00:22
2011-03-21 16:06:15 LoneWolf
à rốt cuộc đã hiểu đề =.=
2011-03-21 02:54:25 LoneWolf
test vd :
nếu con bò 1 đi sau con bò 2 thì phải giảm vận tốc đi 1km/h tức là còn 4km/h chứ nhỉ ??
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.