You are on a line of N squares numbered in order from 1 to N. You are currently at square 1 and you want to get to square N. However, you are very picky with the number of squares you are willing to jump. There are K possible jump distances you are willing to jump. You have to get to square N using a few jumps as possible. This seems easy enough, but you see, some of the squares are covered in spikes and if you jump into those squares, you are as good as dead, so you must plan accordingly. Additionally, you might also be curious about how many ways there are to jump from square 1 to square N. When counting, you must consider all valid jump sequences, even the sub-optimal ones. This number may be very large so output it mod 10⁹ +7. Input Format Input consists of one test case beginning with a line containing two space-separated integers N and K which are the number of squares in the line and the number of jump values you are willing to use. The second line contains a single string S comprised of 1s and Os. If the ith character is a 1, there is a spike on square & and if it contains a 0, that square is empty and you may land on it. Squares 1 and N are guaranteed to be safe. The next K lines contain non-negative integers, the ith of which containing an allowed jump distance J₂ you are willing to use. You cannot jump forward a number of squares not included in this set of values. It is guaranteed that there will be no duplicate values among all Jį.

Database System Concepts

7th Edition

ISBN:9780078022159

Author:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Publisher:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Chapter1: Introduction

Section: Chapter Questions

Problem 1PE

See similar textbooks

Related questions

Question

Information is present in the screenshot and below. Based on that need help in solving the code for this problem in python. The time complexity has to be as less as possible (nlogn or n at best, no n^2). Apply dynamic programming. Do not use recursion. Make sure ALL test cases return expected outputs.

Sample Input 0:
5 2
00110
1
4

Sample Output 0:
1 1

Explanation 0:
The best way to jump from square 1 to square 5 is by jumping 4 squares. That requires only 1 jump.
In fact, that is the only solution, thus the second output is 1.

Sample Input 1:
6 3
010100
1
2
3

Sample Output 1:
2 2

Explanation 1
The best sequence is to jump 2 squares to square 3 then 3 squares to end in square 6.
This is one solution. The other solution is to jump from 1 -> 3 -> 5 -> 6. These are the only two solutions, therefore the second output is 2.

Sample Input 2:
7 2
0001100
3
7

Sample Output 2:
-1 0

Explanation 2:
It is impossible to reach square 7 with the specified jump values.

The actual code

MOD = 1000000007
n,k = list(map(int,input().rstrip().split(" ")))
s = input().rstrip()
jumps = []
for i in range(k):
jumps.append(int(input().rstrip()))

# compute and print answer here

You are on a line of N squares numbered in order from 1 to N. You are currently at square 1 and you want to
get to square N.
However, you are very picky with the number of squares you are willing to jump. There are K possible jump
distances you are willing to jump. You have to get to square N using a few jumps as possible.
This seems easy enough, but you see, some of the squares are covered in spikes and if you jump into those
squares, you are as good as dead, so you must plan accordingly.
Additionally, you might also be curious about how many ways there are to jump from square 1 to square N.
When counting, you must consider all valid jump sequences, even the sub-optimal ones. This number may be
very large so output it mod 10⁹ +7.
Input Format
Input consists of one test case beginning with a line containing two space-separated integers N and K which
are the number of squares in the line and the number of jump values you are willing to use.
The second line contains a single string S comprised of 1s and Os. If the ith character is a 1, there is a spike
on square i and if it contains a 0, that square is empty and you may land on it. Squares 1 and N are
guaranteed to be safe.
The next K lines contain non-negative integers, the ith of which containing an allowed jump distance J, you
are willing to use. You cannot jump forward a number of squares not included in this set of values. It is
guaranteed that there will be no duplicate values among all J₁.
Constraints
1 ≤ N, S, J; ≤ 105
1 ≤ K≤ 30
Output Format
Output consists of one line containing two integers X and Y separated by a single space.
• X is the minimum number of jumps needed to get from square 1 to square N using only the jump
distances allowed in the test case. If it is impossible, X will be equal to -1.
• Y is the total number of ways you can jump from square 1 to square N regardless of whether the solution
is optimal or not. Y must be printed mod 10⁹ +7.

Expert Solution

Step by step

Solved in 4 steps with 4 images

SEE SOLUTION Check out a sample Q&A here

Knowledge Booster

Learn more about

Need a deep-dive on the concept behind this application? Look no further. Learn more about this topic, computer-science and related others by exploring similar questions and additional content below.

Similar questions