Thursday, January 17, 2013

C++ program for jumps problem

Given an array of positive numbers, find the number of ways to reach the end of the array in minimum number of steps where the value at each index represents the maximum number of steps one can move.
Sample Input:
The first line contains a number n, the number of elements in the array. The second line contains n space separated numbers.
11
1 3 5 8 9 2 6 7 6 8 9
Sample Output
Output should contain n space separated numbers, each represents the number of ways at that index.
2 2 4 1 1 2 1 1 1 1 0
#include<iostream>
using namespace std;
int main()
{
int n,A[100];
cin>>n;
int max=-9999999;
for(int i=0;i<n;i++)
{
cin>>A[i];
if(A[i]>max)
{
max=A[i];
}
}
//cout<<max<<endl;
cout<<"The given array is:\n";
for(int i=0;i<n;i++)
{
cout<<A[i]<<" ";
}
cout<<endl;
int B[100]={0};
for(int i=0;i<n-1;i++)
{
B[i]=A[i];
}
for(int i=n-2;i>=0;i--)
{
if(i+A[i] >= n-1)
{
B[i]=1;
}
else
{
int min=max;
bool inside = false;
for(int j=i+A[i];j>i;j--)
{
if(B[j]!=0 && B[j]<=min)
{
min=B[j];
inside = true;
}
}
if(inside)
{
B[i]=min+1;
}
}
}
cout<<"The distance array is:\n";
for(int i=0;i<n;i++)
{
cout<<B[i]<<" ";
}
cout<<endl;
int num[100]={0};
for(int i=n-2;i>=0;i--)
{
if(B[i]==1)
{
num[i]=B[i];
}
else
{
for(int j=1;i+j<n && j<=A[i];j++)
{
if(B[i+j]==B[i]-1)
{
//cout<<i<<" "<<B[i]<<" "<<j<<endl;
num[i]+=num[i+j];
}
}
}
}
cout<<"Number of ways:\n";
for(int i=0;i<n;i++)
{
cout<<num[i]<<" ";
}
cout<<endl;
}
11
1 3 5 8 9 2 6 7 6 8 9
The given array is:
1 3 5 8 9 2 6 7 6 8 9
The distance array is:
3 2 2 1 1 2 1 1 1 1 0
Number of ways:
2 2 4 1 1 2 1 1 1 1 0

No comments:

Post a Comment