croco
Професор Утониум създал нова порода домашни животни, които нарекъл крокобаузери. Той произвел N крокобаузера и започнал да изследва как се размножават. Открил, че всяка двойка може да даде потомство и за всяка двойка определил по колко малки крокобаузерчета може да има двойката за една година. Очевидно, ако всичките крокобаузери се поставят в една стая, всички възможни двойки ще дадат потомство и на края на годината ще има максимален брой от тези животни. Обаче стаите, които имал професорът били малки и нямало място за всичките животни да бъдат поставени само в една стая. Но се оказало, че две стаи са достатъчни за животните.
Задача
Помогнете на професора така да раздели крокобаузери в две стаи, че на края на годината да има максимално по брой потомство.
Вход
Първият ред на
входния файл croco.in
съдържа положително цяло число
N,
равно
на броя
крокобаузери.
Всеки от следващите
N реда съдържа по
N
положителни цели числа, разделени с интервали, като
j-тото
число от i-тия
ред от тях задава броя на потомството, което крокобаузери i
и j
могат да дадат, ако са в една и съща стая; очевидно, ако
i е равно на
j,
съответната стойност е 0,
и ако j
е по-малко от i,
съответната стойност е равна на i-тата
стойност в реда, съответсващ на j.
Изход
Изходният файл croco.out трябва да съдържа в първия си ред две цели числа, разделени с интервал - максималния брой на потомството в края на годината и броя крокобаузери, които трябва да се поставят в първата стая. Вторият ред трябва да съдържа номерата на тези крокобаузери, които са поставени в първата стая, като тези номера са разделени с по един интервал.
Ограничения
Пример
croco.in |
croco.out |
Пояснение |
5 0 4 1 1 0 4 0 0 0 1 1 0 0 4 0 1 0 4 0 4 0 1 0 4 0 |
12 2 1 2 |
В първата стая са
крокобаузери 1
и 2,
които
ще имат общо 4
броя потомство. Във втората стая са крокобаузери 3, 4 и 5. Крокобаузери 3 и 4 ще имат 4 броя потомство, крокобаузери 3 и 5 ще имат 0 броя потомство и крокобаузери 4 и 5 ще имат 4 броя потомство. Общо 12 броя потомство. |
Time limit: 1 сек/тест
Fechete Dan Ionut
University of Bucharest, Mathematics & IT Department
mailto:f.dan.ionut@gmail.com
Превод на български: Емил Келеведжиев