CSES - Hyppely

Pelaat peliä, jossa on n tasoa. Olet aluksi tasolla 0 ja sinun tulee päästä tasolle n. Joka askeleella voit hypätä a tai b tasoa ylemmäs. Monellako tavalla voit läpäistä pelin?

Esimerkiksi kun n=4, a=1 ja b=2, tapoja on 5:

  • 0 \rightarrow 1 \rightarrow 2 \rightarrow 3 \rightarrow 4
  • 0 \rightarrow 1 \rightarrow 2 \rightarrow 4
  • 0 \rightarrow 1 \rightarrow 3 \rightarrow 4
  • 0 \rightarrow 2 \rightarrow 3 \rightarrow 4
  • 0 \rightarrow 2 \rightarrow 4

Voit olettaa, että 3 \le n \le 50 ja 1 \le a < b \le n.

Python

Toteuta tiedostoon jumping.py funktio count, joka ilmoittaa vastauksen.

def count(n,a,b):
    # TODO

if __name__ == "__main__":
    print(count(4,1,2)) # 5
    print(count(10,2,5)) # 2
    print(count(10,6,7)) # 0
    print(count(30,3,5)) # 58
    print(count(50,2,3)) # 525456

Java

Toteuta tiedostoon Jumping.java metodi count, joka antaa vastauksen.

public class Jumping {
    public long count(int n, int a, int b) {
        // TODO
    }

    public static void main(String[] args) {
        Jumping j = new Jumping();
        System.out.println(j.count(4,1,2)); // 5
        System.out.println(j.count(10,2,5)); // 2
        System.out.println(j.count(10,6,7)); // 0
        System.out.println(j.count(30,3,5)); // 58
        System.out.println(j.count(50,2,3)); // 525456
    }
}