1

Тема: Допоможіть розібратись в чому помилка

Допоможіть розібратись. Недавно попалась задача:
Зеник з Марічкою зголосились допомагати на кухні. Всього є три різні страви: борщ, картопля і салат. У Зеника і Марічки є N друзів. i-тий друг хоче зїсти Ai - грам борщу, Ві - грам картоплі і Сі- грам салату. Якщо друг Зеника і Марічки хоче зїсти X грам певної страви, а йому  у тарілку поклали Y грам, то ступінь недовіри до Зеника і Марічки зросте на abs(X-Y) одиниць. Зенику з Марічкою наказали всім покласти однакові порції певної страви. Тобто кожному другу необхідно покласти А- грам борщу, В- грам картоплі і С-грам салату. Допоможіть Зенику і Марічці обрати такі А, В, С, щоб сумарний ступінь недовіри всіх друзів був якомога меншим.

Вхідні дані: В першому рядку задане ціле число N кількість друзів.
В наступних N рядках записано по три цілих числа Ai, Bi, Ci кількість борщу, картоплі і салату, що хоче отримати і-тий друг.
Обмеження: 2<=N<=100000
                   0<= Ai, Bi, Ci<=10000
Приклад:   
Вхідні дані: 2
            10   50  100
            70   10  50
Результат: 150
Примітки: Одним з оптимальних варіантів вибору для Зеника і Марічки буде А=40, В=30, С=75.

Я написав код, але проходить лише 5 тестів. Ось він:

var
  A: array of int64;
  B: array of int64;
  C: array of int64;
  i, Ai, Bi, Ci, Ac, Bc, Cc, n, s: int64;

begin
  s := 0; Ac := 0; Bc := 0; Cc := 0;
  read(n);
  setlength(A, n);
  setlength(B, n);
  setlength(C, n);
  for i := 0 to n - 1 do 
  begin
    read(A[i]);
    Ac := Ac + A[i];
    read(B[i]);
    Bc := Bc + B[i];
    read(C[i]);
    Cc := Cc + C[i];
  end;
  Ac := Ac div n; Bc := Bc div n; Cc := Cc div n;  
  for i := 0 to n - 1 do 
    s := s + abs(Ac - A[i]) + abs(Bc - B[i]) + abs(Cc - C[i]);
  write(s);
end.

2

Re: Допоможіть розібратись в чому помилка

A,B,C тут будуть, вочевидь, середніми арифметичними (насправді є ще варіанти, якщо кількість парна і числа вдалі). Але оскільки вони мають бути цілими (а чи точно мають? в умові я щось не бачу), то треба їх округлити. div округлює завжди вниз, тобто 21,9 він округлює до 21. Якщо ви скористаєтеся функцією round:

Ac := round( Ac / n );

то має вийти краще.

3

Re: Допоможіть розібратись в чому помилка

Результат виводу одне ціле число

4

Re: Допоможіть розібратись в чому помилка

bogdandacik написав:

Результат виводу одне ціле число

Тобто крім того, що ви скопіювали вище, є ще якісь умови? Можна усе разом написати?

5

Re: Допоможіть розібратись в чому помилка

Вихідні дані: одне ціле число сумарний ступінь недовіри всіх друзів Зеника і Марічки.
Примітки: Одним з оптимальних для Зеника і Марічки варіантів вибору А, В, С буде А=40; B=30; C=75. Тоді сумарний ступінь недовіри буде наступний:
Друг1: |40-10|+|30-50|+|75-100|=75
Друг2: |40-70|+|30-10|+|75-50|=75
Сумарний ступінь недовіри 75+75=150

6

Re: Допоможіть розібратись в чому помилка

Пробував через Ac := round( Ac / n ); Але іде тільки 5 тестів.
Ось код:

var A:array of int64;
      B:array of int64;
            C:array of int64;
       N,i,s,Ac,Bc,Cc:int64; 
begin
   s:=0; Ac:=0; Bc:=0; Cc:=0;
   readln(n);
   setlength(A,n);
     setlength(B,n);
       setlength(C,n);
    for i:=0 to n-1 do begin 
     read(A[i]);
       Ac:=Ac+A[i];
              read(B[i]);
              Bc:=Bc+B[i];
                  readln(C[i]);
                 Cc:=Cc+C[i];
             end;
              Ac:=round(Ac/n);
              Bc:=round(Bc/n); 
             Cc:=round(Cc/n);
               for i:=0 to n-1 do 
            s:=s+abs(Ac-A[i])+abs(Bc-B[i])+abs(Cc-C[i]);
                  write(s);
                   end.


Дивно, що 5 тестів видає і при Ac := round( Ac / n )-2

7

Re: Допоможіть розібратись в чому помилка

Скажіть, у вас у самого від такого коду очі не витікають? У чому сенс цих випадкових відступів - зробити читання якомога складнішим, чи що?

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

8

Re: Допоможіть розібратись в чому помилка

Вибачте пане наступного разу врахую ваше зауваження. Але це не має ніякого відношення до проблеми яка виникла. Я пробував тестувати на власному компютері і побачив що набагато менший результат одержується не для середнього значення елементів масивів Ai, Bi, Ci. Я не прошу вас написати мені код а дати якусь ідею розвязку, чи ви і надалі будуте мене критикувати за невідформатований код?

9

Re: Допоможіть розібратись в чому помилка

bogdandacik написав:

Але це не має ніякого відношення до проблеми яка виникла.

Звісно, до проблеми це відношення не має.
Але це має відношення до зручності читання коду тими, у кого ви просите допомоги.
Допомагайте їм допомагати вам, інакше на що ви розраховуєте?

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

10

Re: Допоможіть розібратись в чому помилка

Пропоную Ac, Bc і Cc зробити дробовими, наприклад Extended. І тоді округлювати уже при підрахунку недовіри кожного окремого друга. Причому округлювати можна банківським способом, щоб накопичення похибки було меншим, ніж зараз.

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

11

Re: Допоможіть розібратись в чому помилка

Результат виводу має бути одне ціле число. Якщо Ac, Bc, Cc взяти дробовими то результат виводу буде дробовий.
Я стоворив тест для одного набору Ai-тих:
2; 2; 2; 999; 1001
Якщо взяти Ac=401 то похибка буде:
abs(401-2)+abs(401-2)+abs(401-2)+abs(401-999)+abs(401-1001)=2395
Якщо взяти Ac=2 то похибка буде:
abs(2-2)+abs(2-2)+abs(2-2)+abs(2-999)+abs(2-1001)=1996
Отже, Ac не завжди є середнім арифметичним. Як знайти оптимальне Ac? Допоможіть будь ласка!

12

Re: Допоможіть розібратись в чому помилка

Отже, Ac не завжди є середнім арифметичним.

Ви праві. Бо тут не середнє арифметичне потрібне, а медіана. Зсув з медіани на 1 в будь-який бік призведе до того, що відстань до більшої частини точок зросте на 1, а до меншої - зменшиться на 1; але оскільки збільшується більше відстаней, то і загальна збільшиться.
Тобто:
1. Вводите
2. Сортуєте
3. Знаходите медіану
4. ...
5. PROFIT!

    for i:=0 to n-1 do begin 
      read(A[i]);
      read(B[i]);
      readln(C[i]);
    end;
    for i:=2 to n do begin
      for j:=0 to n-i do begin
        if A[j]>A[j+1] then begin
          tmp := A[j]; A[j]:=A[j+1]; A[j+1]:= tmp;
        end;
        if B[j]>B[j+1] then begin
          tmp := B[j]; B[j]:=B[j+1]; B[j+1]:= tmp;
        end;
        if C[j]>C[j+1] then begin
          tmp := C[j]; C[j]:=C[j+1]; C[j+1]:= tmp;
        end;
      end;
    end;
    if n mod 2 == 1 then begin
      Ac:=A[n div 2];
      Bc:=A[n div 2];
      Cc:=A[n div 2];
    end else begin
      Ac:=(A[n div 2]+A[n div 2 + 1]) div 2;
      Bc:=(B[n div 2]+B[n div 2 + 1]) div 2;
      Cc:=(C[n div 2]+C[n div 2 + 1]) div 2;
    end;
Подякували: leofun01, bogdandacik, Torbins3

13

Re: Допоможіть розібратись в чому помилка

Пане Koala, дякую вам. Дійсно хороша ідея