Question

You are given an N x N grid of squares. Each square except the top left is filled with a positive integer. You start at the top left corner with a score of 0 and move to the bottom right square by moving either right by one square or down by one square. As you move to the new square, your score becomes [S/2] + k, where S was the score at your previous square and k is the number written in the current square. In the above, [x] is the largest integer which is not greater than x. Thus, [5] is 5, and [5.5] is also 5.

Write a program to find the smallest score with which you can exit the grid.

Constraints
4 <= N <= 30

Number in each square <= 1000

Input Format
The first line contains a single integer N, representing the size of the grid

The next N lines, each having N space separated integers giving the numbers written on successive rows of the grid

Answer 1

Answer:

#include<iostream>

using namespace std;

int main()

{

int n,i,j,a,b,sum=0;

cin>>n;

int arr[n][n];

for(i=0;i<n;i++)

{

for(j=0;j<n;j++)

{

cin>>arr[i][j];

}

}

i=0;

j=0;

while(i!=n-1 && j!=n-1)

{

a=i+1;

b=j+1;

if(arr[i][b]>arr[a][j])

{

sum=(sum/2)+arr[a][j];

i=a;

}

else

{

sum=(sum/2)+arr[i][b];

j=b;

}

}

sum=(sum/2)+arr[n-1][n-1];

cout<<sum;

}

Explanation:c code