Футбол

Вход в контест

Этот листок посвящен игре в футбол (а также хоккей). 

В футбол играют две команды. В течение матча команды забивают голы команде противника. Если первая команда забила X голов, а вторая - Y голов, то говорится, что счет в матче X:Y (именно так и будет задаваться счет в матче, два целых неотрицательных числа, разделенных двоеточием. Будем предполагать, что максимальное количество голов, которое команда может забить за игру, равно 9999).
Если X>Y, то первая команда выиграла, а вторая - проиграла.
Если X<Y, то первая команда проиграла, а вторая - выиграла.
Если X=Y, то матч закончился вничью.

Победившая команда получает за матч 3 очка, проигравшая команда - 0 очков, если же была ничья, то каждая команда получает по 1 очку. 

В хоккее победившая команда получает 2 очка. 

Если в чемпионате участвует n команд и чемпионат проводится по круговой системе в один круг, то каждая команда сыграет с каждой другой ровно один матч, то есть общее количество матчей равно n(n-1)/2. 

Разница забитых и пропущенных мячей для команды - это разница двух величин: суммы количества голов, которое забила данная команда и суммы количества голов, которые забили все остальные команды в матчах с данной командой. 

У каждой команды есть название. Название представляет собой последовательность заглавных и строчных букв латинского алфавита (другие символы в названии встречаться не могут). Название имеет длину не более 50 символов.

Во многих задачах входные данные начинаются с задания количества команд, участвующих в турнире, и списка названий команд, участвующих в турнире. В турнире участвует не более 100 команд.

Пример задания списка команд: 

20
Arsenal
AstonVilla
BlackburnRovers
BoltonWanderers
Chelsea
Everton
Fulham
HullCity
Liverpool
ManchesterCity
ManchesterUnited
Middlesbrough
NewcastleUnited
Portsmouth
StokeCity
Sunderland
TottenhamHotspur
WestBromwichAlbion
WestHamUnited
WiganAthletic
После задания списка команд может задаваться список сыгранных матчей. Он задается таким образом: сначала записывается количество сыгранных матчей M. Затем идет M строчек, каждая строчка содержит названия двух команд, разделенных пробелом, затем идет счет матча, также отделенный пробелом от названия второй команды.

Пример задания списка матчей: 

3
Arsenal Chelsea 1:0
Chelsea Fulham 3:1
Fulham Arsenal 1:2

А. Разминка

Записан счет футбольного матча в виде X:Y, где X и Y - целые неотрицательные числа, не превосходящие 9999. Выведите два числа -  количество очков, которое получила в этом матче первая и вторая команды.

Пример

Ввод Вывод 
1:0
 
3 0
 
2:10
 
0 3
 
0:0
 
1 1

B. Сколько сыграно матчей

Задан список команд и список сыгранных матчей. Выведите список команд в порядке их ввода, выводя после названия каждой команды количество сыгранных ею матчей (через пробел). Количество команд в списке выводить не надо.

Пример

Ввод Вывод 
4
Arsenal
Chelsea
Fulham
ManchesterUnited
2
Arsenal Chelsea 1:0
Chelsea Fulham 3:1
 
Arsenal 1
Chelsea 2
Fulham 1
ManchesterUnited 0

C. Сколько очков набрала каждая команда

Задан список команд и список сыгранных матчей. Выведите список команд в порядке их ввода, выводя после названия каждой команды количество набранных ею очков.

Пример

Ввод Вывод 
3
Arsenal
Chelsea
Fulham
3
Arsenal Chelsea 3:2
Chelsea Fulham 1:1
Fulham Arsenal 3:3
 
Arsenal 4
Chelsea 1
Fulham 2

D. Разность забитых-пропущенных

Задан список команд и список сыгранных матчей. Выведите список команд в порядке их ввода, выводя после названия каждой команды разность числа забитых и пропущенных ею голов.

Пример

Ввод Вывод 
3
Arsenal
Chelsea
Fulham
3
Arsenal Chelsea 3:2
Chelsea Fulham 1:1
Fulham Arsenal 3:3
 
Arsenal 1
Chelsea -1
Fulham 0

E. Построить турнирную таблицу

Задан список команд и список сыгранных матчей. Все команды сыграли друг с другом ровно по одному матчу. Постройте турнирную таблицу - квадратную таблицу, показывающую, сколько очков набрала каждая команда в матчах с другой командой. Таблица должна быть заполнена числами 0, 1, 3, соответствующими исходу матча. Каждая строка таблицы должна предваряться выводом названия команды, после этого должно быть выведено один или больше пробелов так, чтобы столбцы таблицы находились один под другим (при этом выведенное количество пробелов должно быть минимальным, т.е. после самого длинного названия команды следует вывести ровно один пробел). На диагонали таблицы поставьте символ #.

Пример

Ввод Вывод 
4
Arsenal
Chelsea
Fulham
ManchesterUnited
6
Arsenal Chelsea 3:2
Chelsea Fulham 1:1
Fulham Arsenal 3:3
Arsenal ManchesterUnited 0:3
ManchesterUnited Chelsea 2:2
ManchesterUnited Fulham 3:2
 
Arsenal          # 3 1 0
Chelsea          0 # 1 1
Fulham           1 1 # 0
ManchesterUnited 3 1 3 #

F. Подводим результаты

Задан список команд и список сыгранных матчей. Все команды сыграли друг с другом ровно по одному матчу. После окончания турнира команды упорядочиваются следующим образом:
  1. В порядке убывания количества набранных очков.
  2. При равном количестве очков команды упорядочиваются в порядке убывания количества побед.
  3. При равном количестве очков и побед команды упорядочиваются в порядке убывания разности забитых и пропущенных голов.
  4. При равенстве всех перечисленных параметров команды упорядочиваются в порядке их следования во входных данных.
Упорядочите команды необходимым образом. Выведите упорядоченный список команд, указав для каждой команды количество набранных очков, количество побед, разность забитых и пропущенных головов. Эти данные отделяйте в строке одним пробелом.

Пример

Ввод Вывод 
4
Switzerland
Czech
Portugal
Turkey
6
Switzerland Czech 0:1
Portugal Turkey 2:0
Czech Portugal 1:3
Switzerland Turkey 1:2
Switzerland Portugal 2:0
Turkey Czech 3:2
 
Portugal 6 2 2
Turkey 6 2 0
Switzerland 3 1 0
Czech 3 1 -2

G. Турнир

В турнире по хоккею участвовало K команд, каждая сыграла с каждой по одному матчу. За победу команда получала 2 очка, за ничью - 1, за поражение - 0 очков. Известно, сколько очков в итоге получила каждая команда, однако результаты конкретных матчей были утеряны. Требуется восстановить одну из возможных турнирных таблиц.

Формат входных данных

В первой строке записано одно натурально число K, не превосходящее 100 - количество команд. Во второй строке записаны через пробел K целых неотрицательных чисел, не превосходящих 2(K-1), - количество очков, набранных командами, занявшими первое, второе, :, K-е места соответственно (то есть каждое следующее число не больше предыдущего).

Формат выходных данных

В выходной файл выведите турнирную таблицу в следующем формате. Таблица должна состоять из K строк с результатами игр команд, занявших первое, второе, :, последнее место (команды, набравшие одинаковое число очков, могут быть расположены в таблице в любом порядке). В каждой строке должно быть записано K чисел через пробел - количество очков, набранных в игре данной команды с первой, второй, : командами соответственно. Количество очков - это число 0, 1 или 2. В клетках на главной диагонали (соответствующих не существующей игре команды "самой с собой") нужно записать нули.

Гарантируется, что входные данные соответствуют реальному турниру, то есть хотя бы одна таблица, соответствующая входным данным, может быть построена. Если таких таблиц несколько, выведите любую из них.

Пример

Ввод Вывод 
4
6 4 2 0
 
0 2 2 2
0 0 2 2
0 0 0 2
0 0 0 0
 
4
3 3 3 3
 
0 2 0 1
0 0 2 1
2 0 0 1
1 1 1 0

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

Как показывает опыт, для создания успешной футбольной команды важны не только умения отдельных её участников, но и сплочённость команды в целом. Характеристикой умения игрока является показатель его профессионализма (ПП). Команда является сплочённой, если ПП каждого из игроков не превосходит суммы ПП любых двух других (в частности, любая команда из одного или двух игроков является сплоченной). Перед тренерским составом сборной страны была поставлена задача сформировать сплочённую сборную с максимальной суммой ПП игроков (ограничений на количество игроков в команде нет).

Ваша задача состоит в том, чтобы помочь сделать правильный выбор из N человек, для каждого из которых известен его ПП.

Формат входных данных

В первой строке входного файла записано целое число N (0≤N≤30000). Далее записано N целых чисел Pi (0≤Pi≤0000), представляющему собой ПП соответствующего игрока.

Формат выходных данных
В первой строке через пробел выведите число игроков, отобранных в команду, и их суммарный ПП. В последующих строках выведите номера игроков, вошедших в команду, в произвольном порядке - по одному числу в строке. Нумерация игроков должна соответствовать порядку перечисления игроков во входном файле. Если ответов несколько, выведите любой из них.

Пример

Ввод Вывод 
4
1 5 3 3
 
3 11
2
3
4
 
5
100 20 20 20 20
 
2 120
1 2