o365. 大黑膝蓋痛 - 高中生程式解題系統

內容

大黑在去竹科吃拉麵的路上摔車了！只好雇用 $N$ 個員工幫忙他的披薩餐廳工作數個工期

一個工期代表總共 $M$ 天的工作，每個員工都希望在一個工期能賺到至少 $C$ 元

但這 $N$ 個員工經驗不足，第一個工期第 $i$ 天的工資只有 $a_{i}$ ，而第i個員工對於工作的學習力是 $w_{i}$

為了保持最佳狀態防止披薩變黑薩，每個員工不能連續兩天都工作(不同工期互不影響)，每經過一個工期，第 $i$ 個員工每天的工資能漲 $w_{i}$ 元

例如 $M = 3$ ，一開始這3天的工資 $a$ 為{ $1, 2, 3$ }，某個員工的學習力為 $3$ ，他做完第一個工期後，這個員工的工資 $a$ 變為{ $1 + 3, 2 + 3, 3 + 3$ }，他做完第二個工期後，工資 $a$ 變為{ $1 + 3 * 2, 2 + 3 * 2, 3 + 3 * 2$ }，以此類推

每個員工的工作和工資互不影響，同一天可以有多個員工一起工作

大黑想知道每個人最少花幾個工期達到目標

輸入說明

第一行有一個正整數 $t$ ，代表有 $t$ 筆測資

每筆測資中:
第一行有三個正整數 $N$ $M$ $C$ ，代表 $N$ 個員工、 $M$ 天的工作，目標 $C$ 元
第二行有 $N$ 個整數，第 $i$ 個整數 $w_{i}$ ，代表第 $i$ 個員工的學習力
第三行有 $M$ 個整數，第 $i$ 個整數 $a_{i}$ ，代表第一個工期第 $i$ 天的工資

$1 \leq N, M \leq 10^{3}$
$1 \leq C \leq 10^{9}$
$1 \leq w_{i} \leq 10^{9}$
$1 \leq a_{i} \leq 10^{9}$

輸出說明

輸出 $N$ 個正整數代表這 $N$ 個人最少花幾個工期能達到目標，以空白隔開

範例輸入 #1

範例輸出 #1

4 
3 5

測資資訊：

記憶體限制： 64 MB
公開測資點#0 (5%): 3.0s , <1K
公開測資點#1 (5%): 2.0s , <1K
公開測資點#2 (10%): 3.0s , <1M
公開測資點#3 (10%): 2.0s , <1K
公開測資點#4 (10%): 3.0s , <1K
公開測資點#5 (10%): 2.0s , <1K
公開測資點#6 (25%): 3.0s , <1M
公開測資點#7 (25%): 2.0s , <1M

提示：

$子題 1$
$1 \leq N, M \leq 10$
$1 \leq C \leq 1000$
10分

$子題 2$
$1 \leq N, M \leq 100$
$1 \leq C \leq 1000$
20分

$子題 3$
$1 \leq N, M \leq 10$
20分

$子題 4$
$原題$
50分

標籤:

出處:

[管理者： CGSH (快加油吧~~) ]

編號	身分	題目	主題	人氣	發表日期
沒有發現任何「解題報告」