Добро пожаловать, гость
:: алгоритмы  и методы :: :: олимпиадные задачи :: :: связь :: :: о сайте :: :: форум ::

Форум работает в режиме архива, только для чтения и поиска.
Архив 2004 Архив 2007 Архив 2013

 
 
Опции темы Поиск в этой теме Опции просмотра
  #1  
Старый 01.11.2009, 19:35
Новичок

Отправить личное сообщение для lfin90 Посмотреть профиль Найти все сообщения от lfin90
 
Регистрация: 01.11.2009
Сообщений: 4

Задача №11 из раздела " Сортировки и последовательности"
Доброго времени суток. Меня заинтересовала олимпиадная задача с этого сайта. Вот ее условия:
Имеются числа А1,А2,...,АN и B1,B2,...,BN. Составить из них N пар (Аi, Bj) таким образом, чтобы сумма произведений пар была максимальна (минимальна). Каждое Ai и Bj в парах встречаются ровно по одному разу.
Решение: Чтобы сумма произведений пар была максимальна (минимальна) необходимо упорядочить наборы A и B одинаковым (различным) образом и пары будут составлять элементы стоящие на одинаковых позициях в упорядоченных наборах. Это следует из того факта, что если а<b и c<d,то а*с+b*d>=a*d+b*c.
У меня вопрос, кто-нибидь писал код этой программы?
  #2  
Старый 01.11.2009, 22:58
гость

 
Сообщений: n/a

А че тут сложного? Я на питоне с закрытыми глазами такое за 30 секунд написать могу.
  #3  
Старый 16.03.2010, 11:43
гость

 
Сообщений: n/a

[quote=гость;8934]А че тут сложного? Я на питоне с закрытыми глазами такое за 30 секунд написать могу.

Так бы и написал решение=)))))
  #4  
Старый 16.03.2010, 16:04
гость

 
Сообщений: n/a

Код:
A=[1,3,2]
B=[4,6,5]

print 'max: ', zip(sorted(A), sorted(B))
print 'min: ', zip(sorted(A), list(reversed(sorted(B))))
 


Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск
Опции просмотра


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Построение пирамиды из "Х" и " " с помощью for. Alexander_ua Задачи 3 10.11.2009 13:35
Задача №11 из раздела " Сортировки и последовательности" lfin90 Задачи 1 01.11.2009 22:54
[язык Си] Задача "Скрудж МакДак",поиск в глубину гость Задачи 0 18.03.2009 18:03
[язык Си] Задача "Скрудж МакДак",поиск в глубину гость Графы 0 18.03.2009 03:21
Ошибка в решении задачи из раздела "Олимпиадные задачи по программированию" WarMan Задачи 0 02.03.2009 00:49