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

PBCJUMP - Nhảy lò cò

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/pbcjump


AD đang bị đau chân sau một vụ tai nạn thảm khốc. Anh ấy không biết làm gì hơn ngoài việc ngồi chơi Tetris. Hôm đó em gái của AD chợt nghĩ ra một trò chơi đó là nhảy lò cò vượt chướng ngại vật, rất may mắn là vẫn còn một chân lành lặn nên anh ấy có thể tham gia. Trò chơi được chơi trên N bậc đánh số từ 1 đến N, bậc thứ i có độ cao Di. Nhiệm vụ của người chơi là nhảy từ bậc 1 đến bậc N. Mỗi người chơi có mức sức khỏe là K thì từ bậc i có thể nhảy đến các bậc i+1, i+2, ... , i+K. Một bước nhảy từ bậc i đến bậc j được gọi là gây mất sức nếu như Di <= Dj. Em gái của AD rất tinh quái nên bắt anh phải tính ra số bước nhảy mất sức ít nhất để hoàn thành trò chơi rồi mới cho chơi ! Không chỉ có thế, AD còn phải tính ra đáp án cho tất cả các bạn của em gái !

INPUT:

  • Dòng đầu chứa số N
  • Dòng thứ hai chứa N số Di
  • Dòng thứ ba chứa Q là số lượng người AD phải giúp tính ra kết quả
  • Q dòng tiếp theo mỗi dòng chứa một số K là mức sức khỏe của từng người

OUTPUT:

  • Q dòng mỗi dòng là kết quả đối với K tương ứng.

Example:

INPUT:
10
3 10 5 3 1 3 2 6 3 4
2
2
3

OUTPUT:
3

Giải thích:

  • Với K = 2 có thể nhảy như nhau: 1->2->4->6->8->10;
  • Với K = 3: 1->2->5->8->10;
10
3 10 5 3 1 3 2 6 3 4 
2
2
3

Giới hạn:

  •  Trong tất cả các test: 1 <= N <= 1000000; 1 <= Di <= 10^9; 1 <= Q <= 25; 1 <= K < N;
  • Trong 20% số test đầu tiên: N <= 1000;
  • Trong 20% số test tiếp theo: N <= 100000; Di <= 10;
  • Trong 20% số test tiếp theo: N <= 100000;
  • Trong 20% số test tiếp theo: Di <= 100;
  • Trong 20% số test còn lại: không có ràng buộc gì thêm.

 


Được gửi lên bởi:Le Anh Duc - A2K42 PBC
Ngày:2015-09-30
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ừ: ASM64 GOSU JS-MONKEY PERL6 PYPY RUST SED

hide comments
2017-09-22 16:42:10 minhsn
bai nay trau cung ac
2015-10-01 07:41:25 Thanga2pbc
hihi
2015-09-30 22:36:54 Nắng
đề bài từ 1 câu chuyện có thật của PS
2015-09-30 20:06:16 Lollipop
one shot.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.