Форум программистов, компьютерный форум, киберфорум
Наши страницы
Turbo Pascal
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.67/3: Рейтинг темы: голосов - 3, средняя оценка - 4.67
reactive123
0 / 0 / 0
Регистрация: 20.10.2018
Сообщений: 1
1

Борщ, картошка и салат

20.10.2018, 13:51. Просмотров 524. Ответов 4
Метки нет (Все метки)

Сегодня в пластунов праздник! Привезли вдвое больше продуктов на обед. Зеник вместе с Марией согласились помогать на кухне. Всего есть три разных блюда: борщ, картофель и салат.

В пласте в Зеника и Маши есть N друзей. i-й друг хочет съесть Ai грамм борща, Bi грамм картофеля и Ci грамм салата. Если друг Зеника и Маши хочет съесть X грамм определенной блюда, а ему в тарелку положили Y грамм, то степень недоверия к Зеника с Марией у этого друга вырастет на | X-Y | единиц. Зеник с Марией приказали накладывать всем одинаковые порции определенной блюда. То есть каждому вторую нужно наложить A грамм борща, B грамм картофеля и C грамм салата.

Помогите Зенику и Марии выбрать такие A, B и C, чтобы суммарная степень недоверия всех друзей был как можно меньше.

Входные данные: В первой строке записано целое число N - количество друзей Зеника и Маши. В следующих N строках записаны по три целых числа Ai, Bi, Ci - количество борща, картошки и салата, которую хочет получить i-й друг.

Выходные данные: Одно целое число - суммарная степень недоверия всех друзей к Зеника и Маши.

Ограничение: 2 ≤ N ≤ 100000 (105) 30% тестов: 0 ≤ Ai, Bi, Ci ≤ 444 70% тестов: 0 ≤ Ai, Bi, Ci ≤ 10000 (104)

Пример ввода:
2
10 50 100
70 10 50
Пример вывода: 150
Подсказка: Одним из оптимальных для Зеника и Маши вариантов выбора чисел A, B, C будет A = 40, B = 30, C = 75. Тогда степень недоверия друзей будет следующим: Друг 1: | 40-10 | + | 30-50 | + | 75-100 | = 30 + 20 + 25 = 75 Друг 2: | 40-70 | + | 30-10 | + | 75-50 | = 30 + 20 + 25 = 75 Суммарный степень недоверия = 75 + 75 = 150
Пробовал так:
Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
program name;
var
   a,b,c:array[1..1000000] of word;
   n,i:2..1000000000;
   sa,sb,sc,s,a1,b1,c1:real;
begin
     read(n);
     for i:=2 to n+1 do
         begin
              read(a[i],b[i],c[i]);
              sa:=sa+a[i];
              sb:=sb+b[i];
              sc:=sc+c[i];
         end;
     a1:=sa/n;
     b1:=sb/n;
     c1:=sc/n;
     for i:=2 to n+1 do s:=s+abs(a[i]-a1)+abs(b[i]-b1)+abs(c[i]-c1);
     writeln(s:0:0);
end.
Это на основе того, что оптимальным вариантом выбора чисел, является среднее арифметическое всех А, В и С.

Добавлено через 14 минут
Но программа не проходит на 6-ом тесте
0
QA
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
20.10.2018, 13:51
Ответы с готовыми решениями:

Салат Фантези
Сижу на даче. Сыро. Не жарко. Наши дачники на вопрос какое сегодня число отвечают - "30 июбря":)...

Сволочной салат
Как-то еще при царе Горохе решил сам себе компенсировать весенний авитаминоз. Накупил всякой...

результат в результате, или я даже не знаю, как обозвать этот борщ
Вот, допустим, есть: $res = mysqli_query($db, запрос №1); $b = ''; $a = '<table id="mama">';...

Посоветуйте салат к 8 марта
подскажыте пожалуста, может у кого есть хорошый рецепт ко дню 8 марта... Хочу зделать девушке...

Элементарный чесночно-помидорный салат [любителям чеснока]
Элементарный чесночно-помидорный салат Преимущества этого блюда: + очень простой рецепт +...

4
кот Бегемот
Платежеспособный зверь
8593 / 4006 / 1569
Регистрация: 28.10.2009
Сообщений: 10,496
20.10.2018, 14:05 2
Цитата Сообщение от reactive123 Посмотреть сообщение
Но программа не проходит на 6-ом тесте
Это неверное решение. Вернее, неверная идея. Среднее арифметическое здесь совсем не причём. Разберём простой пример.
Пусть гостей будет пятеро. Введём данные (они взяты практически с потолка):
5
8 6 5
7 3 2
4 6 2
5 1 8
2500 3200 4700
Ваша программа выдаёт ответ 16617, а минимум, которого можно достичь= 10495
как говорится, почувствуйте разницу.
0
кот Бегемот
Платежеспособный зверь
8593 / 4006 / 1569
Регистрация: 28.10.2009
Сообщений: 10,496
20.10.2018, 14:28 3
Принцип решения очень простой. Для каждого блюда надо выбрать не среднее арифметическое, а среднее по порядку. Например, для чисел 1,2,3,4,638 средним будет 3. Если же число гостей чётное, то подойдёт как среднее с недостатком, так и среднее с избытком, например, если числа 2 4 9 345 можно брать и 4, и 9.
0
vlados124
1 / 1 / 0
Регистрация: 13.09.2018
Сообщений: 126
20.10.2018, 16:18 4
Вы все не так поняли. Имеется ввиду, среднее арифметическое каждого блюда. Например: в примере из задачи, среднее арифметическое блюда А равно (10+70)/2=40; блюда В - (50+30)/2=30; блюда С - (100+50)/2=75. И сумма равняется разности по модулю порции, предоставленной каждому другу и среднему арифметическому данного блюда.
0
кот Бегемот
Платежеспособный зверь
8593 / 4006 / 1569
Регистрация: 28.10.2009
Сообщений: 10,496
20.10.2018, 19:13 5
Вот же идиот, ему решение рассказывают, а он упирается
Я-то как раз всё прекрасно понял ( я уже решал эту задачу), а вот ты, похоже, не понял ни фига. Ну,я тупых учить не нанимался. Прощай

PS. А проведи эксперимент: для данных чисел примера вместо среднего возьми ЛЮБОЕ число от начального до конечного (включая границы) и посчитай вручную. Результат тебя удивит.
0
20.10.2018, 19:13
Answers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
20.10.2018, 19:13

Игра "Горячая картошка"
Демонстрация игры "горячая картошка", количество участников задается, расставляется по кругу, по...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
5
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2019, vBulletin Solutions, Inc.