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 Output The smallest score with which you can exit the grid Time Limit 1 Explanation Example 1 Input Input 4 0 3 9 6 1 4 4 5 8 2 5 4 1 8 5 9 Output 12 Explanation N=4. The set of scores are as given. The 4 X 4 scores look as follows One possible set of moves are down, right, down, right, right, down. The corresponding scores are 1, 4, 4, 7, 7, 12 Example 2 Input 5 0 82 2 6 7 4 3 1 5 21 6 4 20 2 8 6 6 64 1 8 1 65 1 6 4 Output 7 Explanation One possible set of moves are down, right, right, right, down, down, down, right
Answers
Textbook Solutions
Schools & Teachers
Content Guidelines
Honor code
Community
ghemanth1387
18.06.2020
Computer Science
Secondary School
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 Output The smallest score with which you can exit the grid Time Limit 1 Explanation Example 1 Input Input 4 0 3 9 6 1 4 4 5 8 2 5 4 1 8 5 9 Output 12 Explanation N=4. The set of scores are as given. The 4 X 4 scores look as follows One possible set of moves are down, right, down, right, right, down. The corresponding scores are 1, 4, 4, 7, 7, 12 Example 2 Input 5 0 82 2 6 7 4 3 1 5 21 6 4 20 2 8 6 6 64 1 8 1 65 1 6 4 Output 7 Explanation One possible set of moves are down, right, right, right, down, down, down, right
Explanation:
public class DP_codevita { public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
int a=sc.nextInt();
int arr[][]=new int[a][a];
for(int i=0;i<a;i++)
{ for(int j=0;j<a;j++)
{
arr[i][j]=sc.nextInt();
}
}
for(int i=0;i<arr.length;i++)
{ for(int j=0;j<arr[0].length;j++)
{ if(i==0 && j==0)
{
arr[i][j]=0;
}
else if(i==0 && j!=0)
{
arr[i][j]= (int)Math.floor((arr[i][j-1]/2)+arr[i][j]);
}
else if(i!=0 && j==0)
{
arr[i][j]= (int)Math.floor((arr[i-1][j]/2)+arr[i][j]);
}
else
{
int min=Math.min(arr[i][j-1], arr[i-1][j]);
arr[i][j]= (int)Math.floor((min/2)+arr[i][j]);
}
}
}
System.out.println(arr[a-1][a-1]);
} }