1

Тема: Алготестер задача № 0012. Борщ, картопля і салат. Java

https://www.algotester.com/uk/ArchivePr … WithFile/3
Задача на перший погляд проста, але на шостому прикладі помилка.

import java.util.Scanner;

import static java.lang.Math.abs;

public class Main {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int arr[][] = new int[n][3];
        int sum_borsch = 0, sum_potato = 0, sum_salat = 0;
        for (int i = 0; i < n; i++){
            for (int j = 0; j < 3; j++){
                arr[i][j] = in.nextInt();
                if (j == 0) sum_borsch += arr[i][j];
                if (j == 1) sum_potato += arr[i][j];
                if (j == 2) sum_salat += arr[i][j];
            }
        }
        // щоб не створювати нові змінні для середніх значень
        sum_borsch /= n;
        sum_potato /= n;
        sum_salat /= n;
        //  sum_borsch, sum_potato і sum_salat - це середні значення
        int result = 0;
        for (int i = 0; i < n; i++){
            for (int j = 0; j < 3; j++){
                if (j == 0) result += abs(sum_borsch - arr[i][j]);
                if (j == 1) result += abs(sum_potato - arr[i][j]);
                if (j == 2) result += abs(sum_salat - arr[i][j]);
            }
        }
        System.out.println(result);
    }
}


Дякую за вашу допомогу!

2 Востаннє редагувалося koala (03.07.2020 10:37:43)

Re: Алготестер задача № 0012. Борщ, картопля і салат. Java

Яка помилка?
Ну і ви неправильний алгоритм обрали. Припустимо, є три друга, які хочуть 1,2 і 1000 грамів борщу. Тоді середнє (1000+2+1)/3 дасть 334 і, відповідно, 334-1+334-2+1000-334=1331 недовіри. Але якщо дати їм 2 грами, недовіра становитиме 2-1+2-2+1000-2=999.

Подякували: leofun01, zxzpogoncuk2

3

Re: Алготестер задача № 0012. Борщ, картопля і салат. Java

Рішення мовою Pascal

Подякували: zxzpogoncuk1

4

Re: Алготестер задача № 0012. Борщ, картопля і салат. Java

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

public class Main {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int arr_borsch[] = new int[n];
        int arr_potato[] = new int[n];
        int arr_salat[] = new int[n];
        for (int i = 0; i < n; i++){
            arr_borsch[i] = in.nextInt();
            arr_potato[i] = in.nextInt();
            arr_salat[i] = in.nextInt();
        }
        Arrays.sort(arr_borsch);
        Arrays.sort(arr_potato);
        Arrays.sort(arr_salat);
        int mediana_borsch = 0, mediana_potato = 0, mediana_salat = 0;
        if(n % 2 == 0) {
            mediana_borsch = ( arr_borsch[n/2 - 1] + arr_borsch[n/2] ) /2;
            mediana_potato = ( arr_potato[n/2 - 1] + arr_potato[n/2] ) / 2;
            mediana_salat = ( arr_salat[n/2 - 1] + arr_salat[n/2] ) / 2;
        } else {
            mediana_borsch = arr_borsch[n/2];
            mediana_potato = arr_potato[n/2];
            mediana_salat = arr_salat[n/2];
        }
        int result = 0;
        for (int i = 0; i < n; i++) result += Math.abs(arr_borsch[i] - mediana_borsch) + Math.abs(arr_potato[i] - mediana_potato) + Math.abs(arr_salat[i] - mediana_salat);
        System.out.println(result);
    }
}

Все ідеально працює. Дякую за допомогу. І пане koala мені не зручно коли до мене звертаються на ви, адже я лише школяр.

Подякували: leofun011

5

Re: Алготестер задача № 0012. Борщ, картопля і салат. Java

До речі, можна в кінці не перевіряти на парність.
Річ у тім, що тут не потрібна точна медіана. Дивіться. Якщо ми беремо число, менше за будь-яке з множини, то його збільшення на 1 зменшить недовіру на N. Наближаємося до центру далі: коли ми "перетнули" найменшого, недовіра на кожному кроці буде зменшуватися на (N-1)-1 - N-1 все ще отримують кращий результат, 1 - гірший. Коли ліворуч залишиться, скажімо, k значень, кожен крок праворуч даватиме зміну в N-2*k - доки не досягнемо центру. Якщо ліворуч і праворуч рівно N/2 значень, кожен крок змінюватиме виграш на N-2*(N/2)=0. Тобто будь-яке число від arr[n/2-1] до arr[n/2] включно даватиме один і той самий результат.

Подякували: zxzpogoncuk, leofun012