основной форум
Архив сообщений 2004-2006 года

Алгоритмы, методы, исходники


Олимпиады >> Задачи

Страницы: 1
limper
новичок


Рег.: 08/27/06
Сообщений: 3
Задача с московской городской олимпиады
      #11955 - 08/28/06 08:54 AM

Здравствуйте! Меня очень интересует решение этой задачи.
Заранее спасибо!

Задача E. Сплоченная команда

Максимальное время работы на одном тесте: 1 секунда
Максимальный объем используемой памяти: 64 мегабайта


Как показывает опыт, для создания успешной футбольной команды важны не только умения отдельных её участников, но и сплочённость команды в целом. Характеристикой умения игрока является показатель его профессионализма (ПП). Команда является сплочённой, если ПП каждого из игроков не превосходит суммы ПП любых двух других (в частности, любая команда из одного или двух игроков является сплоченной). Перед тренерским составом молодёжной сборной Москвы была поставлена задача сформировать сплочённую сборную с максимальной суммой ПП игроков (ограничений на количество игроков в команде нет).
Ваша задача состоит в том, чтобы помочь сделать правильный выбор из N человек, для каждого из которых известен его ПП.
Формат входных данных
В первой строке входного файла записано целое число N<30000). В последующих N строках записано по одному целому числу Pi<60000), представляющему собой ПП соответствующего игрока.
Формат выходных данных
В первой строке через пробел выведите число игроков, отобранных в команду, и их суммарный ПП. В последующих строках выведите номера игроков, вошедших в команду, в произвольном порядке — по одному числу в строке. Нумерация игроков должна соответствовать порядку перечисления игроков во входном файле. Если ответов несколько, выведите любой из них.


Операции над сообщением Печать сообщения   Добавить тему в напоминания!   Известить модератора  
megabot007
приобщившийся


Рег.: 12/05/05
Сообщений: 60
Из: Москва
Re: Задача с московской городской олимпиады [Re: limper]
      #11958 - 08/28/06 09:35 AM

Для начала отсортируем игроков по ПП (по возрастанию).
Потом заведем два указателя (i, j) и поставим оба на начало массива. Затем перемещаем указатель j, пока можем (то есть пока ПП наилучшего игрока не превзойдет ПП i и i+1). Далее перемещаем на 1 вправо указатель i и выполняем те же действия с указателем j. И так пока не дойдем до конца.
Сложность - O(N*log N) + O(N) //Сортировка + проход.
Детали реализации: возможно, придется отдельно писать код для случаев
i = j, i + 1 = j.


Операции над сообщением Печать сообщения   Добавить тему в напоминания!   Известить модератора  
limper
новичок


Рег.: 08/27/06
Сообщений: 3
Re: Задача с московской городской олимпиады [Re: megabot007]
      #11960 - 08/28/06 10:31 AM

У меня вопрос - вы имеете ввиду что искомая сплоченная команда будет между указателями? Если так, то это неправда. Представьте последовательность из 1000 едениц, а потом три раза по сто. Указатель i сдвинется, хотя не должен.

Операции над сообщением Печать сообщения   Добавить тему в напоминания!   Известить модератора  
megabot007
приобщившийся


Рег.: 12/05/05
Сообщений: 60
Из: Москва
Re: Задача с московской городской олимпиады [Re: limper]
      #11963 - 08/28/06 08:49 PM

Вы не совсем поняли алгоритм.
Пусть у нас есть 1000 единиц и 3 раза по сто.
1 шаг: i = 1, j = 1, 2, ..., 1000. Сумма будет 1000*1 = 1000.
2, 3, ..., 999 шаг: i = 2, 3, ... , 999; j = 1000.
Сумма будет 999, 998, ... , 2.
1000 шаг: i = 1000, j = 1001, 1002, 1003. Сумма будет 1 + 100*3 = 303.
1001, 1002, 1003 шаг: i = 1001, 1002, 1003; j = 1003. Сумма будет 300, 200, 100.

Очевидно, что максимальная достигнутая сумма - 1000, поэтому ответом будут игроки между i = 1 и j = 1000 (включительно).

P.S.: Очевидно, что если сумма ПП двух худших игроков в группе (между i и j) не меньше, чем ПП лучшего игрока в группе, то условие (ПП каждого из игроков не превосходит суммы ПП любых двух других) выполняется для любых игроков в группе.


Операции над сообщением Печать сообщения   Добавить тему в напоминания!   Известить модератора  
Страницы: 1



Дополнительная информация
0 зарегистрированных и 382 анонимных пользователей просматривают этот форум.

Модератор:  Илья Кантор, Sergeyev, M_Gustokashin 

Распечатать тему

Права
      Вы не можете создавать новые темы
      Вы не можете отвечать на сообщения
      HTML выключен
      UBBCode включен

Рейтинг:
Просмотры темы: 10794

Rate this topic

Переход в