Alexander Malinov
Изтегляне 27.35 Kb.
|
- Навигация на страницата:
- Задача 6 – Таен език
- Ограничения
- Примери
Задача 6 – Таен езикАвтор: Николай Костов Малката Сиси и приятелите ѝ разбрали, че родителите им следят „тайната“ им комуникация. Затова те решили да си измислят нов език, който да им позволи да си говорят свободно. В крайна сметка измислили език, в който съобщенията се преобразуват по специален начин.Програмата ви ще получи списък от всичките валидни думи в езика. Тези думи се състоят единствено от латински малки букви. Едно съобщение представлява конкатенация на валидни думи от езика (т.е. „залепени“ думи). Всяка една валидна дума от езика може да се среща в съобщението 0 или повече пъти. Това, което прави езика специален, е че всяка дума може да бъде преобразувана, като буквите и се разместят преди да бъдат записани в съобщението. Цената на преобразуване на една дума е дефинирана като броят на позициите в първоначалната и променената дума, между в които има разлики. Например, ако „abc“ е пренаредена към „abc“ цената е 0, ако е пренаредена към „acb“, „cba“ или „bac“ цената е в (има по 2 позиции в които първоначалната и крайната дума се различават), а ако е пренаредена към „bca“ или „cab“, цената е 3.Тъй като едно съобщение може да е резултат от няколко различни трансформации (преобразувания и залепяния на думи), за съдържание на съобщението се взема тази трансформация, която има най-малка обща цена (обща цена на една трансформация е сборът от цените за пренареждане на всяка една дума, ползвана в трансформацията). Предимството на новия език е, че родителите вече не разбират съобщенията между децата. Недостатъкът е, че децата също не ги разбират. Те имат нужда от вашата помощ. По дадени думи в езика и съобщение, програмата ви трябва да върне най-ниската цена на трансформация, чрез която може да се получи това съобщение. Ако една дума е вече ползвана с едно пренареждане, тя може да бъде ползвана отново със същото или с друго пренареждане.
ВходВходните данни се четат от конзолата. На първият ред от входа ще бъде съобщението. На следващия ред ще се намира числото N – броят думи в езика. На следващия ред ще бъдат думите от езика, разделени с интервали. Входните данни ще са винаги валидни, в описания формат и няма нужда да бъдат проверявани.
ИзходИзходните данни се печатат на конзолата. На единственият ред от изхода програмата трябва да изведе най-ниската цена на трансформация. Ограничения
Примери
Каталог: svn -> algo-academy -> 2012-04-Dynamic-Programming algo-academy -> Alexander Malinov algo-academy -> Alexander Malinov algo-academy -> Alexander Malinov 2012-04-Dynamic-Programming -> Alexander Malinov algo-academy -> Alexander Malinov algo-academy -> Alexander Malinov algo-academy -> Alexander Malinov Изтегляне 27.35 Kb. Сподели с приятели:
| |||||||||||||||
