Question

Java

Supermegastaurants have overtaken megastaurants as the latest trend in dining. A supermegastaurant is characterized by enormous menus, four categories of food, and a rule that you must choose exactly one item from each category. You have won a gift certificate of M dollars to use at a megastaurant. In order to maximize your dining value, you wish to choose an item from each category such that the price is as close to M as possible.

Input Format

Input begins with five integers, A, B, C, D, and M, subject to the following constraints:

1 <= A, B, C, D <= 2000
1 <= M <= 2,147,000,000

Next is a line with A positive integers, each less or equal to than 2,147,000,000. These integers are the prices of items in the first category.

Next is a line with B positive integers, each less or equal to than 2,147,000,000. These integers are the prices of items in the second category.

Next is a line with C positive integers, each less or equal to than 2,147,000,000. These integers are the prices of items in the third category.

Next is a line with D positive integers, each less or equal to than 2,147,000,000. These integers are the prices of items in the fourth category.

Output Format

You are to output the total cost of the meal with a price closest to M.

Note: This cost can be equal to M, greater than M, or less than M. In the case of a tie costs, choose the cheaper of the two costs.

Sample Input

3 2 1 2 50

15 10 49

11 17

10

13 23

Sample Output

50

Explanation

Here you can choose items that exactly equal M:

10 + 17 + 10 + 13 = 50

1) An argument of the correctness of your code:

a) State a loop invariant.

b) Argue that the loop invariant is true before the loop starts executing.

c) Argue that the loop invariant remains true after each iteration of the loop.

d) Argue for the correctness of your algorithm based on the loop invariant.

Answer 1

Program:

//importing the library

import java.util.*;

//start of main class

public class Main

{
//start of main method
  
   public static void main(String[] args) {
  
       Scanner read=new Scanner(System.in);
  
   //declaration of variables
  
       int A,B,C,D,M;
  
       int max=0,min=0,e=0;

//reading A,B,C,D and M from user
  
       A=read.nextInt();
      
       B=read.nextInt();
      
       C=read.nextInt();
      
       D=read.nextInt();
      
       M=read.nextInt();
      
       //decalring arrays to store items
      
       int a[]=new int[A];
      
       int b[]=new int[B];
      
       int c[]=new int[C];
      
       int d[]=new int[D];
      
       //taking item numbers from user and storing them in arrays
      
       for(int i=0;i<A;i++){
      
       a[i]=read.nextInt();
      
      
       }
  
       for(int i=0;i<B;i++){
  
       b[i]=read.nextInt();
  
       }
  
       for(int i=0;i<C;i++){
  
       c[i]=read.nextInt();
  
       }
  
       for(int i=0;i<D;i++){
  
       d[i]=read.nextInt();
  
       }
      
       //verifying the items which are greter than M and less than M and equal to M
      
       for(int i=0;i<A;i++){
  
       for(int j=0;j<B;j++){
  
       for(int k=0;k<C;k++){
  
       for(int l=0;l<D;l++){
   //if items are equal to M then print M
       if(a[i]+b[j]+c[k]+d[l]==M){
  
       e=1;
  
       System.out.println(M);
  
       }
  
       else if((a[i]+b[j]+c[k]+d[l]<max) && (a[i]+b[j]+c[k]+d[l])<50 ){
  
       max=(a[i]+b[j]+c[k]+d[l]);
  
       }
  
       else if((a[i]+b[j]+c[k]+d[l]>min) && (a[i]+b[j]+c[k]+d[l])>50 ){
  
       min=(a[i]+b[j]+c[k]+d[l]);
  
       }
      
       }
  
       }
  
       }
  
       }
      
   //if items are not equal to M
   //then we will check the closest item numbers
   //that may be greater than or less then M
       if(e==0){
  
       if( M-min > Math.abs(M-max)){
  
       System.out.println(max);
  
       }
  
       else{
       System.out.println(min);   
       }
   }
   }
}

Output: