主題

ZeroJudge - g541: 類題:兔子跳躍(TOIP) 解題心得

Not In My Back Yard | 2021-11-14 00:00:06 | 巴幣 2 | 人氣 133

題目連結:


題目大意:
輸入第一列給定三正整數 N 、 M 、 Q(1 ≦ N 、 M ≦ 200,1 ≦ Q ≦ 1000000),代表兔子每次可以往前跳(只能往前不能往後) N 或 M 個單位格子,且有 Q 筆詢問。接著第二列給定 Q 個正整數 D(1 ≦ D ≦ 2147483647),試問兔子是否可以從位置 0 藉由每步跳 N 或 M 格來抵達位置 D?如果可以輸出「YES」;反之,輸出「NO」。



範例輸入:
範例輸入 #1
2 3 5
1 2 3 4 5

範例輸入 #2
7 6 2
15 17


範例輸出:
範例輸出 #1
NO
YES
YES
YES
YES

範例輸出 #2
NO
NO


解題思維:
這題的簡化版,因為跳 N 步或 M 步沒有成本的問題(也可以看成是成本相同)。因此我們只需要看是否「有解」且是否「有非負整數解」(因為兔子只能往前跳)即可。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

相關創作

更多創作