X конкурс по програмиране на PC Magazine Bulgaria и Musala Soft Ltd.

X конкурс по програмиране на PC Magazine Bulgaria и Musala Soft Ltd.

---

След като приготвил всичко за голямото интерпланетарно парти, на Малкия принц му останало приятното задължение да чака и да си мечтае за предстоящото събитие. Докато преглеждал листа с имената на гостите, нашият герой забелязал много интересни зависимости между тях. Някои имена започвали така, както завършвали други. Имало дори такива, които напълно се съдържали в други. През главата на Малкия принц минали какви ли не весели мисли, представяйки си, че някои негови приятели били реално в стомасите на други.
В крайна сметка Малкият принц писал в своя любим Starnet форум и оттам възникнала следната интересна задача. Имайки имената на приятелите му, да се намери колкото се може по-къс низ, съдържащ всичките имена като поднизове. Например, “ab” и “bc” са поднизове на “abc”, но “ac” не е.
Естествено Малкият принц именовал приятелите си само с едно име (кому е нужно повече от едно) и следователно крайният низ също не съдържа интервали. За по-голямо удобство имената са записани изцяло с малки латински букви.
Участвайте в търсенето на колкото се може по-добро решение. Напишете програма NAMES.EXE, която чете имената на приятелите на Малкия принц и намира колкото може по-къс низ, съдържащ всички имена като поднизове.
Входните данни са зададени в текстовия файл NAMES.INP. На първия ред е записано естественото число N (2 Ј N Ј 512), броят на познатите на Малкия принц. Следват N реда, задаващи имената на приятелите му, по едно на ред. Всеки от тях съдържа по един низ, съставен от малки латински букви и не по-дълъг от 4096 знака.
На първия ред от изходния текстов файл NAMES.OUT е записано естествено число - дължината на намерения низ. Вторият ред съдържа самия низ с дължина, указана на първия ред. Всеки от следващите N реда съдържа по едно число - позицията в намерения низ, от която започва съответното име (следвайки наредбата от входния файл). Номерацията на позициите започва от едно.
За всеки тест максимален брой точки ще получи състезателят, чиято програма е намерила най-къс низ, удовлетворяващ условието. Участник, чийто низ има дължина по-голяма или равна на общата дължина на имената от входния файл, ще получи нула точки. Всички останали верни решения ще получат точки, пропорционални на намерената от тях дължина на низа.

ПРИМЕР

NAMES.INP
2
computer
basscom

NAMES.OUT
12
basscomputer
1
5


Очакваме решенията на задача 6 не по-късно от 2.01.2005 г. на адрес konkurs@sagabg.net или konkurs@musala.com. На www.konkurs.musala.com и www.pcmagbg.net ще публикуваме съдържанието на задачите от текущия кръг 20 дни преди крайния срок за изпращане на решението, както и всички промени, актуализации, резултати и временното класиране. Там можете да намерите и правилата за участие в нашия конкурс.

---