← 返回题目列表

AtCoder · jag2017summer_day3_b

B. 瘦身计划

中文机器翻译题面 查看原题

问题陈述

Chokudai 非常喜欢吃。然而,他的医生Akensho告诉他,他体重超重,所以他最终决定减肥。

Chokudai制定了一个以$D$为周期的减肥计划。它由 $D$ 整数 $w_0, \ldots, w_{D-1}$ 表示。在计划的第 $0$ 天,他的体重为 $S$,他的目标是将其减少到 $T \ (S > T)$。如果他在计划的第 $i$ 天的体重为 $x$,则第 $(i+1)$ 天的体重将为 $x + w_{i \% D}$。注意$i\%D$是$i$除以$D$得到的余数。如果他的体重成功低于或等于$T$,他将立即停止减肥。

如果他的减肥计划花了太多天甚至永远不会结束,他应该重新考虑。

判断是否结束,如果结束则报告需要多少天。


输入

输入由单个测试用例组成,格式如下。

$S\T\D$ $w_0 \cdots w_{D-1}$

第一行由三个整数 $S, T, D \ (1 \le S,T,D \le 100{,}000, \ S > T)$ 组成。 第二行由 $D$ 整数 $w_0, \ldots, w_{D-1}$ 组成(每个 $i$ 为 $-100{,}000 \le w_i \le 100{,}000$)。

输出

如果Chokudai的减肥计划在第$d$天结束,则在一行中打印$d$。如果永远不会结束,则打印 $-1$。


示例输入 1

65 60 3
-2 3 -4

样本输入 1 的输出

4

Chokudai 的重量将发生如下变化:$65 \to 63 \to 66 \to 62 \to 60$。


示例输入 2

65 60 3
-2 10 -3

样本输入 2 的输出

-1

Chokudai 的重量将发生如下变化:$65 \to 63 \to 73 \to 70 \to 68 \to 78 \to 75 \to \cdots$。


示例输入 3

100000 1 1
-1

样本输入 3 的输出

99999

示例输入 4

60 59 1
-123

样本输入 4 的输出

1