Задача 3
Категория: Софтуер
PC MAGAZINE
четвъртък, 15 Декември 2005 0:00ч
След като показа на приятелите си, че може да отслабне, Мечо Пух реши да им покаже, че може да се върне към нормалния си начин на живот и да си върне нормалната фигура без никакви усилия. И докато се тъпчеше с мед, Мечо реши да посети и поговори с приятелите си, които не беше виждал отдавна заради безсмисленото тичане.
Един от тези приятели – Кристофър Робин – се случи да не е в добро настроение. Той отскоро имаше компютър и вече можеше да прави какви ли не неща, като да слуша музика, да си говори с приятели, дори да пише програми, които смятат факториел. Фактът, който натъжи Кристофър Робин, е, че попадна на сайта на Конкурса на PC Magazine Bulgaria и Musala Soft и видя задачите, които решават състезателите. Той видя и новата задача и нямаше никаква идея как да я реши.
Пух беше мъдро мече, въпреки че ядеше много мед или може би именно затова. Той каза на своя приятел, че вместо да се натъжава, трябва да се радва на успехите на другите и да се учи от тях. И така Кристофър Робин възвърна своята усмивка и взе с нетърпение да очаква решенията на участниците, за да може да се поучи от тях, а и да напише свое собствено.
А задачата, която трябва да се реши, не е лесна. В нея са дадени N задачи, които трябва да се изпълнят на нов суперкомпютър. Компютърът изпълнява по една задача в даден момент, като е известно колко време му отнема изпълнени- ето и. Резултатът от изпълнението на задача е определен обем данни, които биват използвани при изчисляването на други задачи. Задача не може да бъде изпълнена, преди да има всичките необходими данни. Изчислените резултати се съхраняват в паметта, докато не бъдат изпол- звани, след което биват изтривани. Данните се изтриват след приключване на задачата, за която са нужни. Трудната част в задачата идва от факта, че съхраняването на данните в паметта е „скъпа“ операция. Цената й се измерва във време умно- жено по обем – „времеобем“. За съхраняването на единица данни за единица време е необходим един времеобем.
Имайки цялата информация за задачите, за зависимостите между тях и за големината на генерираните данни, напишете програма TASKS, която подрежда задачите в ред, за който сумата от изразходваните времеобеми при изчислението е колкото се може по-малка.
Входните данни са записани в текстовия файл TASKS.INP. На първия ред е записано едно число N (1 ≤ N ≤ 512) – броят на задачите. Задачите са номерирани с числата от 1 до N. Следват N реда, като P-тият от тях се отнася за задачата с номер P. В началото на всеки ред са записани две числа – L (1 ≤ L ≤ 1024) и M. L показва колко време е нужно, за да бъде изпълнена дадената задача. Числото M показва колко други задачи зависят от данните, генерирани от текущата задача. Следват M двойки числа, като първото показва поредната задача, която зависи от текущата, а второто колко е обемът на генерираната информация. Между задачите няма циклична зависимост – например не е възможно задача 1 да зависи от 2, задача 2 от 3 и задача 3 от 1.
Програмата ви трябва да записва резултата в изходния файл TASKS.OUT. Той съдържа N реда, като на всеки е записано по едно число от 1 до N и не трябва да има повтарящи се числа. Всеки ред показва поредната задача, която трябва да се изпълни.
ПРИМЕР
TASKS.INP
4
1 2 2 5 3 6
2 1 4 7
2 1 4 4
10 0
TASKS.OUT
1
3
2
4
Програмата ви трябва да завършва всеки тест за по-малко от 5 секунди. За всеки тест максимален брой точки ще получи състезателят, чиято програма е намерила коректно решение с минимален брой изразходвани времеобеми. Всички останали решения ще получат точки пропорционално на времеобемите, изразходвани от тях.
При това разпределение на задачите сумата на изразходваните времеобеми е 150. Инфор- мацията за задача 3, която се пази, е с обем 6 и се пази, докато се изпълни задача 3, която трае време 2. Необходимите времеобеми са 12. Информацията за задача 2 е с обем 5 и се пази, докато се изпълнят задачи 3 и 2, което трае време 4. Изразходваните времеобеми са 20. За задача 4 се пази информация, генерирана от задача 3, която е с обем 4, и се пази време 12. Изразходваните времеобеми са 48. Освен това за задача 4 се пази информация от задача 2 с обем 7 в продължение на време 10. Изразходваните времеобеми са 70.
