Последовательность попарных сумм

ограничение времени на тест: 1 сек.
ограничение памяти на тест: 640 KB.

ввод: input.txt
вывод: output.txt

 

Дана последовательность чисел A={a1, a2,..., aN}. Последовательность попарных сумм P={p1, p2,..., pK} образована всеми числами вида ai+aj, где 1<=i<j<=N. Порядок элементов последовательности P несущественен. Нетрудно показать, что K=N(N-1)/2. Например, если A={1,2,3,4}, то P={3,4,5,5,6,7}. Заметим, что как A, так и P могут содержать повторяющиеся числа.
По заданной последовательности A нетрудно вычислить последовательность попарных сумм P, сложнее решить обратную задачу.
Ваша программа получает на вход последовательность P, и должна находить неубывающую последовательность неотрицательных целых чисел A, такую, что последовательность ее попарных сумм (после соответствующего переупорядочивания) совпадает с P.

Входные данные

В первой строке записано натуральное число K (1 <= K <= 1000) - количество чисел в последовательности P. Во второй строке содержится K чисел p1, p2,..., pK - элементы последовательности P. Все числа в последовательности P целые, неотрицательные, не превосходящие 1000. Числа в строках разделяются пробелами.

Выходные данные

В случае, если искомая неубывающая последовательность неотрицательных целых чисел A не существует или она не единственна, то выведите фразу NO SOLUTION, иначе выведите последовательность A. В первой строке выводите число N, а во второй последовательность a1, a2,..., aN. Числа разделяйте пробелами.

Пример

Ввод

Test #1
6
3 5 4 7 6 5

Test #2
6
5 6 7 9 10 11

Вывод

Test #1
4
1 2 3 4

Test #2
NO SOLUTION

Город Н-ск

ограничение времени на тест: 1 сек.
ограничение памяти на тест: 640 KB.

ввод: input.txt
вывод: output.txt

 

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

Входные данные

В первой строке записаны целые числа N, M (1 <= N <= 100, 1 <= M <= 1000), где N - количество площадей в Н-ске, а M - количество улиц. Во второй строке записано для каждой площади количество детей, проживающих на ней, в виде N неотрицательных целых чисел (каждое не превосходит 100). Далее в M строках содержится описание улиц. Каждая улица задается тройкой A, B, L, где A, B - номера площадей, которые она соединяет, а L - ее длина (1 <= L <= 100). Все числа в строках разделяются пробелами.

Выходные данные

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

Пример

Ввод

4 6
1 2 2 3
1 2 3
1 3 1
1 4 1
2 3 3
2 4 3
3 4 2

Вывод

5
2 3

Афины 2004

ограничение времени на тест: 1 сек.
ограничение памяти на тест: 640 KB.

ввод: input.txt
вывод: output.txt

 

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

Входные данные

В первой строке записано натуральное число N (1 <= N <= 500), где N - количество комплектов наград. Далее записано N строк, каждая в виде "XXX YYY ZZZ", формат которого описан выше. Все страны имеют различные трехбуквенные обозначения.

Выходные данные

Выведите строк, где M - количество стран, получивших хотя бы одну медаль. Выводите команды в порядке, описанном выше. Нумеруйте команды в соответствии с занятым местом в общекомандном зачете. Если две или более страны завоевали одинаковый комплект наград, они делят одинаковое место. Выводите строки в формате "NUM. AAA G S B", где "NUM" - место занятое командой, "AAA" - ее трехбуквенное обозначение, "G" - количество золотых медалей, "S" - серебряных, "B" - бронзовых.

Пример

Ввод

4
ITA JPN AUS
RUS TPE UKR
RUS RUS GBR
RUS CHN TPE

Вывод

1. RUS 3 1 0
2. ITA 1 0 0
3. TPE 0 1 1
4. CHN 0 1 0
4. JPN 0 1 0
6. AUS 0 0 1
6. GBR 0 0 1
6. UKR 0 0 1