КОНКУРС ПО ПРОГРАМИРАНЕ НА БАРС ЗА 2007 г.

За втора поредна година Българска асоциация на разработчиците на софтуер (БАРС) заедно с Musala Soft и PC Magazine / Bulgaria организира национален конкурс по програмиране. Задачата този път е с алгоритмичен характер и е отправена като предизвикателство към всички млади програмисти и софтуерни специалисти, които имат желание да участват.

ОРГАНИЗАТОРИ

СПОНСОР НА КОНКУРСА

СофтКонсултГруп ООД е софтуерна фирма с традиции в разработката на качествени решения. Фирмата е основана през 2001 година и днес е утвърдена като сериозен бизнес партньор и предпочитано място за работа за много хора. Основните сфери на дейност са разработка на системи за управление на бизнес процеси и консултации в областта на информационните технологии. Техническата компетентност, мотивираният екип и добрият мениджмънт правят СофтКонсултГруп предпочитан партньор на компании от цял свят. Посетете уеб сайта на компанията: http://www.softconsultgroup.com/.

УСЛОВИЕ НА ЗАДАЧАТА
ЗДРАВОСЛОВНО ХРАНЕНЕ

Един хубав слънчев ден, Мечо Пух решил да отиде на гости на стария си познайник – Карлсон, който живее на покрива. След като прекарали няколко часа, наблюдавайки небето от покрива на сградата, Пух и Карлсон решили да отидат на гости на Дребосъчето. 

В дома на Дребосъчето, те открили тайните запаси с храна на майката му. Запасите съдържали огромни количества от различни видове кюфтенца, тортички, сладолед, медени изделия и други. Тъй като станало време Мечо Пух да се прибира в Голямата гора, те решили да разпределят запасите в два чувала, като всеки вземе по един. 

Като разбрало какви количества храна се готвят да изядат неговите приятели, Дребосъчето се разтревожило за тяхното здраве. Това, което най-много го притеснило, било вредното въздействие на някой комбинации от храна. Например, според него никак не е полезно да се комбинират кюфтенца с мед или риба с боза и сладолед. Колкото повече съставки съдържа една вредна комбинация, толкова по-опасна е тя.

Помогнете на Дребосъчето да разпредели храната в двата чувала, като напишете програма NUTRITION, която по зададени хранителни продукти и списък с вредни комбинации, намира разпределение на продуктите в двата чувала, с възможно най-малка обща вреда за здравето (ОБЗ).

Общата вреда за здравето за дадено разпределение се пресмята, като сума от броя на елементите на всички вредни комбинации, всички части на които се намират в един и същ чувал (т.е. ще бъдат изядени от един и същ приятел на Дребосъчето). Всички хранителни продукти трябва да бъдат разпределени в някой от двата чувала (все пак Пух и Карлсон няма да се съгласят да оставят неизядена храна).

Входните данни се четат от файл NUTRITION.IN. На първия ред е записано числото N (N ≤ 1 100), което задава броя на всички хранителни продукти в тайните запаси. За удобство, хранителните продукти са номерирани с числата от 1 до N. На следващия ред е записано числото M (М ≤ 250) – броят на вредните комбинации известни на Дребосъчето. Следващите M реда съдържат информация за една вредна комбинация, като първото число задава броя на хранителните продукти, участващи в нея, а останалите – техните номера. Една комбинация не може да съдържа един и същ хранителен продукт повече от веднъж.

Изходните данни се печатат във файл NUTRITION.OUT. Програмата трябва да отпечата на един ред броя на хранителните продукти, които ще постави в първия чувал и номерата на тези продукти. Всички числа в изходния файл трябва да бъдат на отделен ред. Всички продукти, които не бъдат поставени в първия чувал, се считат за поставени във втория.

За всеки тест, максимален брой точки ще получи състезателят, чиято програма е намерила разпределение с най-малко ОБЗ. Всички останали решения ще получат точки пропорционално на ОБЗ на разпределението, намерено от тяхната програма. Програмата на участника трябва да завърши един тест за не повече от 5 секунди.

ПРИМЕР:
NUTRITION.IN
5
8
2 1 2
2 1 3
2 1 4
2 2 3
3 1 3 4
1 5
2 3 5
2 4 5	NUTRITION.OUT
3
1
2
4

	

ПОЯСНЕНИЕ: В първия чувал се поставят три хранителни продукта с номера 1, 2 и 4, като във втория остават два хранителни продукта с номера 3 и 5. Продукти 1 и 2 се намират в един и същ чувал, следователно имат ОБЗ равна на 2. Продукти с номера 1 и 4 се намират в един и същ чувал, следователно имат ОБЗ равна на 2. Продукти 3 и 5 имат ОБЗ равна на 2. Продукт 5 сам по себе си носи ОБЗ равна на 1. Няма други комбинации, частите, на които се намират в един и същ чувал, следователно общата вреда за здравето в това разпределение е равна на 2 + 2 + 2 + 1 = 7. Съществуват разпределения с ОБЗ равна на 3.

НАГРАДИ

 - Първа награда: 120 GB външен USB твърд диск + USB кутия
 - Поощрителни награди: 4 броя 1GB USB Drive (memory stick)

КАК ДА УЧАСТВАМЕ

За повече информация посетете уеб сайта на конкурса: http://konkurs.musala.com.