4588 . pF. 終末倒數 (Monopoly)

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

Description

題目 PDF 檔在這裡

yoyo正在看學弟妹玩他舉辦的新新大富翁，突然有個小隊從建中門口的蔣公銅像的頭頂找到了一張 終末倒數 卡，使用後所有人都開始持續扣血，連佑佑都沒有意識到這張卡的存在而警急發送通知請所有小隊馬上回到控制室。

已知現在你每一秒都會受到1點輻射傷害，同時終末倒數的鐘聲每 $p$ 秒會響起一次（第 $p,\ 2p,\ 3p$ 秒），對你造成 $d$ 的傷害，幸好在路上有一些避難所，可以幫你抵擋鐘聲的聲音，然而輻射傷害是不可避免的。

已知，所有避難所以及控制室都在一條一維數線上，而你現在在座標為0的地方，而控制室的座標為 $b$ ，已知你原點（座標0）以及控制室都可以抵擋鐘聲，然而你現在的地方隨時都有可能塌陷所以你還是需要趕往控制室，你每秒都可以選擇移動一單位的距離或是待在原地，請問你最少能在受到多少傷害的情況下抵達控制室？

Input Format

第一行有四個整數 $b,\ p,\ d,\ n$，分別代表控制室座標、鐘聲的傷害間隔、鐘聲傷害、避難所數量。
接下來有 $n$ 行，每行有一個整數，代表避難所的位置。

  • $0 \leq p, \, n < b$
  • $1 \leq b \leq 10 ^ {12}$
  • $0 \leq d \leq 10 ^ 6$
  • $0 \leq n \leq 10 ^ 5$

Output Format

請輸出一個整數代表你能受到的最小傷害。

Sample Input 1

18 4 5 2
8
15

Sample Output 1

29

Sample Input 2

18 4 0 2
8
15

Sample Output 2

18

Sample Input 3

18 10 100 2
8
15

Sample Output 3

20

Sample Input 4

18 4 100 0

Sample Output 4

418

Sample Input 5

65 20 100 3
14
25
33

Sample Output 5

172

Hints

Problem Source

TopCoder

cjtsai
$\href{javascript:alert(1);}{a}$

User's AC Ratio

20.0% (1/5)

Tags

學術上機考 112 學年度 終局之戰

Problem Setter

Created by cjtsai

Subtasks

No. Testdata Range Constraints Score
1 0~6 $p \leq 10 ^ 6$ 且你不需要在路上等待（可能還是需要在起點等待） 8
2 7~44 $b \leq 1000, p \leq 100, n \leq 10$ 5
3 7~56 $b \leq 1000$ 7
4 0, 7~70 $p \leq 10 ^ 6, n \leq 1000$ 15
5 0, 7~77 $p \leq 100$ 20
6 0~88 $p \leq 10 ^ 6$ 35
7 0~96 無其他限制 10

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 2000 1048576 65536 1 4 5 6 7
1 2000 1048576 65536 1 6 7
2 2000 1048576 65536 1 6 7
3 2000 1048576 65536 1 6 7
4 2000 1048576 65536 1 6 7
5 2000 1048576 65536 1 6 7
6 2000 1048576 65536 1 6 7
7 2000 1048576 65536 2 3 4 5 6 7
8 2000 1048576 65536 2 3 4 5 6 7
9 2000 1048576 65536 2 3 4 5 6 7
10 2000 1048576 65536 2 3 4 5 6 7
11 2000 1048576 65536 2 3 4 5 6 7
12 2000 1048576 65536 2 3 4 5 6 7
13 2000 1048576 65536 2 3 4 5 6 7
14 2000 1048576 65536 2 3 4 5 6 7
15 2000 1048576 65536 2 3 4 5 6 7
16 2000 1048576 65536 2 3 4 5 6 7
17 2000 1048576 65536 2 3 4 5 6 7
18 2000 1048576 65536 2 3 4 5 6 7
19 2000 1048576 65536 2 3 4 5 6 7
20 2000 1048576 65536 2 3 4 5 6 7
21 2000 1048576 65536 2 3 4 5 6 7
22 2000 1048576 65536 2 3 4 5 6 7
23 2000 1048576 65536 2 3 4 5 6 7
24 2000 1048576 65536 2 3 4 5 6 7
25 2000 1048576 65536 2 3 4 5 6 7
26 2000 1048576 65536 2 3 4 5 6 7
27 2000 1048576 65536 2 3 4 5 6 7
28 2000 1048576 65536 2 3 4 5 6 7
29 2000 1048576 65536 2 3 4 5 6 7
30 2000 1048576 65536 2 3 4 5 6 7
31 2000 1048576 65536 2 3 4 5 6 7
32 2000 1048576 65536 2 3 4 5 6 7
33 2000 1048576 65536 2 3 4 5 6 7
34 2000 1048576 65536 2 3 4 5 6 7
35 2000 1048576 65536 2 3 4 5 6 7
36 2000 1048576 65536 2 3 4 5 6 7
37 2000 1048576 65536 2 3 4 5 6 7
38 2000 1048576 65536 2 3 4 5 6 7
39 2000 1048576 65536 2 3 4 5 6 7
40 2000 1048576 65536 2 3 4 5 6 7
41 2000 1048576 65536 2 3 4 5 6 7
42 2000 1048576 65536 2 3 4 5 6 7
43 2000 1048576 65536 2 3 4 5 6 7
44 2000 1048576 65536 2 3 4 5 6 7
45 2000 1048576 65536 3 4 5 6 7
46 2000 1048576 65536 3 4 5 6 7
47 2000 1048576 65536 3 4 5 6 7
48 2000 1048576 65536 3 4 5 6 7
49 2000 1048576 65536 3 4 5 6 7
50 2000 1048576 65536 3 4 5 6 7
51 2000 1048576 65536 3 4 5 6 7
52 2000 1048576 65536 3 4 5 6 7
53 2000 1048576 65536 3 4 5 6 7
54 2000 1048576 65536 3 4 5 6 7
55 2000 1048576 65536 3 4 5 6 7
56 2000 1048576 65536 3 4 5 6 7
57 2000 1048576 65536 4 5 6 7
58 2000 1048576 65536 4 5 6 7
59 2000 1048576 65536 4 5 6 7
60 2000 1048576 65536 4 5 6 7
61 2000 1048576 65536 4 5 6 7
62 2000 1048576 65536 4 5 6 7
63 2000 1048576 65536 4 5 6 7
64 2000 1048576 65536 4 5 6 7
65 2000 1048576 65536 4 5 6 7
66 2000 1048576 65536 4 5 6 7
67 2000 1048576 65536 4 5 6 7
68 2000 1048576 65536 4 5 6 7
69 2000 1048576 65536 4 5 6 7
70 2000 1048576 65536 4 5 6 7
71 2000 1048576 65536 5 6 7
72 2000 1048576 65536 5 6 7
73 2000 1048576 65536 5 6 7
74 2000 1048576 65536 5 6 7
75 2000 1048576 65536 5 6 7
76 2000 1048576 65536 5 6 7
77 2000 1048576 65536 5 6 7
78 2000 1048576 65536 6 7
79 2000 1048576 65536 6 7
80 2000 1048576 65536 6 7
81 2000 1048576 65536 6 7
82 2000 1048576 65536 6 7
83 2000 1048576 65536 6 7
84 2000 1048576 65536 6 7
85 2000 1048576 65536 6 7
86 2000 1048576 65536 6 7
87 2000 1048576 65536 6 7
88 2000 1048576 65536 6 7
89 2000 1048576 65536 7
90 2000 1048576 65536 7
91 2000 1048576 65536 7
92 2000 1048576 65536 7
93 2000 1048576 65536 7
94 2000 1048576 65536 7
95 2000 1048576 65536 7
96 2000 1048576 65536 7
Submit
Back to Top