Jumping on the Clouds

-

Emma is playing a new mobile game that starts with consecutively numbered clouds. Some of the clouds are thunderheads and others are cumulus. She can jump on any cumulus cloud having a number that is equal to the number of the current cloud plus   or  . She must avoid the thunderheads. Determine the minimum number of jumps it will take Emma to jump from her starting postion to the last cloud. It is always possible to win the game.

For each game, Emma will get an array of clouds numbered   if they are safe or   if they must be avoided. For example,   indexed from  . The number on each cloud is its index in the list so she must avoid the clouds at indexes   and  . She could follow the following two paths:   or  . The first path takes   jumps while the second takes  .

Function Description

Complete the jumpingOnClouds function in the editor below. It should return the minimum number of jumps required, as an integer.

jumpingOnClouds has the following parameter(s):

  • c: an array of binary integers

Input Format

The first line contains an integer  , the total number of clouds. The second line contains   space-separated binary integers describing clouds   where  .

Constraints

Output Format

Print the minimum number of jumps needed to win the game.

Sample Input 0 

7
0 0 1 0 0 1 0

Sample Output 0 

4

Explanation 0:
Emma must avoid   and  . She can win the game with a minimum of   jumps:

Sample Input 1 

6
0 0 0 0 1 0

Sample Output 1 

3

Explanation 1:
The only thundercloud to avoid is  . Emma can win the game in   jumps:


This is a simulation problem. Because the problem guarantees that it is always possible to win, we know that our input will never contain   consecutive thunderclouds. To reach the last cloud in a minimum number of steps, always try make a jump from   to  . If that is not possible, jump to  .

The Problem Setter's solution below uses this approach. Check out the Problem Tester's solution for a slightly different approach.


Problem Setter's code:

Python 2 

n = int(raw_input())
c = map(int, raw_input().split(" "))
ans = 0
i = 0
while i < n - 1:
    if i + 2 >= n or c[i + 2] == 1:   # Not possible to make a jump of size 2
        i = i + 1
        ans = ans + 1
    else:
        i = i + 2
        ans = ans + 1
print ans

Ruby 

#!/bin/ruby

n = gets.strip.to_i
c = gets.strip
c = c.split(' ').map(&:to_i)
ans = 0
i = 0
while i < n - 1
    (i + 2 >= n or c[i + 2] == 1 )? i=i+1: i=i+2
    ans = ans + 1
end
print ans

C++ 

#include <bits/stdc++.h>
using namespace std;

const int inf = 555;
int A[111], dp[111];

int main() {
    int n; cin >> n;

    for(int i=1; i<=n; i++) {
        cin >> A[i];
    }
    for(int i=2; i<=n; i++) {
        if(A[i] == 0) dp[i] = min(dp[i-1], dp[i-2]) + 1;
        else dp[i] = inf;
    }
    cout << dp[n] << "\n";
    return 0;
}

Comments

Post a Comment

Popular posts from this blog

Insertion Sort - Part 2 | C | HACKERRANK

-
In  Insertion Sort Part 1 , you inserted one element into an array at its correct sorted position. Using the same approach repeatedly, can you sort an entire array? Guideline:  You already can place an element into a sorted array. How can you use that code to build up a sorted array, one element at a time? Note that in the first step, when you consider an array with just the first element, it is already sorted since there's nothing to compare it to. In this challenge, print the array after each iteration of the insertion sort, i.e., whenever the next element has been inserted at its correct position. Since the array composed of just the first element is already sorted, begin printing after placing the second element. For example, there are   elements in  . Working from left to right, we get the following output: 3 4 7 5 6 2 1 3 4 7 5 6 2 1 3 4 5 7 6 2 1 3 4 5 6 7 2 1 2 3 4 5 6 7 1 1 2 3 4 5 6 7 Function Description Complete the  insertionSort2  function in the editor below. At ea
Read more

Array Reversal problem solution | C | HackerRank

-
Input Format The first line contains an integer,  , denoting the size of the array. The next line contains   space-separated integers denoting the elements of the array. Constraints , where   is the   element of the array. Output Format The output is handled by the code given in the editor, which would print the array. #include <stdio.h> #include <stdlib.h> int main () { int num , * arr , i ; scanf ( "%d" , & num ); arr = ( int * ) malloc ( num * sizeof ( int )); for ( i = 0 ; i < num ; i ++ ) { scanf ( "%d" , arr + i ); } /* Write the logic to reverse the array. */ int * left_ptr = arr ; int * right_ptr ; int temp ; for ( i = 0 ; i < num ; i ++ ) { if ( i == num - 1 ) { right_ptr = ( arr + i ); } } while ( left_ptr < right_ptr ) { temp = * right_ptr ; * right_ptr = * l
Read more

Insertion Sort - Part 1 | C | HackerRank |

-
Sorting One common task for computers is to sort data. For example, people might want to see all their files on a computer sorted by size. Since sorting is a simple problem with many different possible solutions, it is often used to introduce the study of algorithms. Insertion Sort These challenges will cover  Insertion Sort , a simple and intuitive sorting algorithm. We will first start with a nearly sorted list. Insert element into sorted list Given a sorted list with an unsorted number   in the rightmost cell, can you write some simple code to insert   into the array so that it remains sorted? Since this is a learning exercise, it won't be the most efficient way of performing the insertion. It will instead demonstrate the brute-force method in detail. Assume you are given the array   indexed  . Store the value of  . Now test lower index values successively from   to   until you reach a value that is lower than  ,   in this case. Each time your test fails, copy the value at the
Read more