Programming Geek
Rated 4.7/5 based on 1446 reviews

ACM ICPC Amritapuri Online Round Solution : Creating a Warmhole

No comments :
Dr Ryan Stone is the Mission Specialist, and she went out to fix some communications equipment when suddenly news came in about debris from other satellite heading towards them. Very quickly, she realizes that she does not have enough time to get all her equipments back in before the Debris field hits them. Therefore, she decided to adopt an alternative way of handling the debris. She has got “N” pieces of equipments. Each equipment is essentially an iron stick of some length. The i^th equipment has length a_i. She wants to join them end to end to form a closed polygon. She will then send some electric current through the polygon to create a giant magnetic field which will attract all debris. Thus, this polygon will act as a wormhole, sucking in all the debris and allowing rest of the satellite/crew to go unharmed. She wants to form as big a polygon as possible, and hence she wants to quickly know the maximum number of equipments she can use to form a polygon. Note that the area of polygon should be non-zero, otherwise debris can’t pass through it. You should output -1 if no polygon can be formed.
Input Format:
The first line contains the number of test cases T. For each test case, the first line contains N, the number of equipments. The following line contains N space delimited integers, the ith integer specifying the length of the ith equipment. Output: For each test case, output the maximum number of equipments which can be used to form a polygon.
Constraints:
1 <= T <= 100
3 <= N <= 10000
1 <= a_i <= 10^9
Sample Input:
2
7
1 12 3 2 5 1 50
3
1 1 2
Sample Output:
5
-1
Explanation:
For the first test case, we can use the equipments of lengths 1, 3, 2, 5, 1 and form a polygon out of them. There is no way to form a polygon using more than 5 equipments. For the second test case, we cannot form a valid polygon from the given equipments.
Time Limit
4 s
Memory Limit
256 MB 
Solution : 

The logic is quite simple.

  1. Sort the array.
  2. At ith index store the sum of elements upto ith index.
  3. now start comparing elements from last position.
          if ith element is smaller than all previous element than print (i+1)

       if no polygon can be formed than out -1.



import java.util.Arrays;
import java.util.Scanner;

/**
 *
 * @author VIK
 */
public class Solution {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        int tt[] = new int[t];
        for (int i = 1; i <= t; i++) {
            int n = sc.nextInt();
            int[] temp = new int[n];

            for (int j = 0; j < temp.length; j++) {

                temp[j] = sc.nextInt();

            }

            Arrays.sort(temp);
            for (int j = 1; j < temp.length; j++) {
                temp[j] += temp[j - 1];
            }
            boolean flag = true;
            for (int j = temp.length - 1; j > 1; j--) {
                if ((temp[j] - temp[j - 1]) < temp[j - 1]) {
                    tt[i - 1] = (j + 1);

                    flag = false;
                    break;

                }
            }
            if (flag) {
                tt[i - 1] = -1;

            }



        }
        for (int i = 0; i < tt.length; i++) {
            if (i != t) {
                System.out.println(tt[i]);
            } else {
                System.out.print(tt[i]);
            }
        }
    }
}


ACM ICPC Amritapuri Online Round Solution : Flee To Shelter

No comments :
Dr. Ryan Stone has been trying to fix the communications equipment at the Hubble Space telescope when the crew of the Explorer Shuttle receive the news of a debris field headed their way. She now needs to get all her “N” instruments back to the shuttle as soon as possible. But at the most, she can carry only “M” instruments with her at a time, and it takes her exactly “T”” minutes to go between the telescope and the shuttle.
What is the minimum amount of time she needs to get all her instruments back into the shuttle? Assume that she is at the shuttle while receiving the news.
Input Format:
The first line consists of the number of tests cases, C.
Each of the next C lines consist of 3 integers: N, M and T.
Output Format:
For each test case, output the least amount of time she needs to transfer all her instruments back to the shuttle.
Constraints
1 <= C <= 1000
1 <= N, M, T <= 100
time limit: 4 sec
memory limit: 256 mb
Sample Input:
1  
3 2 10  
Sample Output:
40  
Explanation:
Dr Stone takes 10 minutes to get from the shuttle to the telescope,
then she takes 10 minutes to carry 2 of the instruments back,
then she takes 10 minutes to get back to the telescope,
and then she takes 10 minutes to carry the remaining 1 instrument back.



import java.util.Scanner;

/**
 *
 * @author VIK
 */
public class Solution {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int c = sc.nextInt();

        int cost = 0;
        int[] arr = new int[c];
        int i = 1;
        while (i <= c) {
            cost = 0;
            int n = sc.nextInt();
            int m = sc.nextInt();
            int t = sc.nextInt();
            if (n > m) {
                cost = 2 * t * ((n / m));
                if (n % m != 0) {
                    cost += 2 * t;
                }

            } else {
                cost = 2 * t;
            }


            arr[i - 1] = cost;
            i++;
        }
        for (i = 0; i < arr.length; i++) {

            if (i != c - 1) {
                System.out.println(arr[i]);
            } else {
                System.out.print(arr[i]);
            }
        }
    }
}