Йон
е мениджър на
преуспяваща
компания. Поради
динамиката
на работата,
всички
служители имат
мобилни телефони.
Фирмата
плаща всички
разговори
между
служителите
и стремежът
на Йон е да се
съкратят
разходите.
Неотдавна
беше обявена
услуга,
наречена „група”,
която може
сериозно да
намали
разходите
при
определени
условия.
По-специално,
Йон може да
избере група
от k
служители и
след
активирането
на услугата
за тази
група, те ще
плащат 50%
по-малко за
разговори
помежду си.
Останалите
разговори ще
се таксуват
по редовната
тарифа. Ако
служител от
групата се
обажда на
друг член на
групата, той ще
плаща по 10 ст.
на минута. За
останалите
разговори се
прилага
редовната
тарифа, която
е 20 ст. на
минута.
Сега Йон
анализира
обажданията
през изтеклия
месец и се
опитва да
сформира
група, така,
че общата
сума на
телефонните
разговори да
бъде
възможно най-малка.
Задача
Напишете програма, която определя група от k служители по такъв начин, че ако за тях се активира услугата, общите телефонни разходи да бъдат минимални.
Вход
Входният
файл grup.in
съдържа на
първия ред цяло
положително число
k,
представляващо
броя на
служителите,
които ще
образуват
група.
Вторият ред
съдържа цяло положително
число N,
представляващо
общия брой
разговори. На
всеки от
следващите N реда
е описан по
един отделен
разговор. За
всеки разговор
е дадено:
nume1 nume2 d
което
означава, че
служител с
име nume1 е
говорил със
служител с
име nume2
в
продължение
на d
минути.
Изход
Изходния файл grup.out трябва да съдържа на първия ред минималната обща сума за телефонни разговори, изразена в стотинки. На следващите k реда трябва да бъдат записани имената на служителите, които трябва да сформират група (по едно име на ред).
Ограничения и пояснения
Примери
grup.in |
grup.out |
Обяснение |
3 |
820 |
Стойността
на всеки
разговор: |
Време за работа на програмата: 0.15 секунди на тест
prof. Emanuela Cerchez
"Grigore Moisil" Iaşi IT High School
Contact:emanuela.cerchez@gmail.com