ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1005. Stone Pile

Who knows what is the test 7?
Posted by David Yin 3 Apr 2015 13:48
Who knows what is the test 7?
I failed at this test.

import java.util.Scanner;

public class T1005_Stone_Pile {

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

        for (int i = 0; i < count; i++) {
            weights[i] = in.nextInt();
        }
        weights = selectSort(weights);
        int sum = 0;

        for (int i = 0; i < weights.length; i++) {
            sum = sum + weights[i];
        }
        int middle = sum / 2;
        int pointer = count / 2 - 1;
        int[] solution = new int[count];
        int[] discrepancy = new int[count];

        int cursor = 0;
        int cursor2 = 0;
        // solution[0] = weights[count - 1];
        // discrepancy[0] = solution[0] - middle;
        int solutionSum = 0;
        for (int i = count - 1, j = 0; i > pointer; i--, j++) {
            solutionSum = solutionSum + weights[i];
            solution[j] = solutionSum;
            discrepancy[j] = solutionSum - middle;
            if (discrepancy[j] >= 0) {
                cursor = j;
                break;
            }
        }

        if (cursor == 0 || discrepancy[cursor] == 0) {
            System.out.println(Math.abs(sum - 2 * solution[cursor]));
            return;
        } else {
            solutionSum = solution[cursor - 1];
            for (int i = 0, j = cursor + 1; i < count; i++, j++) {
                solutionSum = solutionSum + weights[i];
                solution[j] = solutionSum;
                discrepancy[j] = solutionSum - middle;
                if (discrepancy[j] >= 0) {
                    cursor2 = j;
                    break;
                }
            }
        }
        if (discrepancy[cursor2] == 0) {
            System.out.println(Math.abs(sum - 2 * solution[cursor]));
            return;
        } else {
            int minIndex = cursor;
            if (Math.abs(discrepancy[minIndex]) > Math.abs(discrepancy[cursor - 1])) {
                minIndex = cursor - 1;
            }
            if (Math.abs(discrepancy[minIndex]) > Math.abs(discrepancy[cursor2])) {
                minIndex = cursor2;
            }
            if (Math.abs(discrepancy[minIndex]) > Math.abs(discrepancy[cursor2 - 1])) {
                minIndex = cursor2 - 1;
            }
            System.out.println(Math.abs(sum - 2 * solution[minIndex]));
            return;
        }
    }

    private static int[] selectSort(int[] arr) {
        int min = 0;
        int temp = 0;
        if (arr == null || arr.length == 0) {
            return null;
        }
        for (int i = 0; i < arr.length - 1; i++) {
            min = i;
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[min] > arr[j]) {
                    min = j;
                }
            }
            if (min != i) {
                temp = arr[i];
                arr[i] = arr[min];
                arr[min] = temp;
            }
        }
        return arr;
    }
}
Re: Who knows what is the test 7?
Posted by David Yin 3 Apr 2015 14:13
6
1 2 3 4 100 100
Will fail this program
Re: Who knows what is the test 7?
Posted by David Yin 3 Apr 2015 14:13
The solution is not correct
Re: Who knows what is the test 7?
Posted by Namjmus Sakib Rashid 12 Mar 2019 20:15
Thnx from bd