Title: Задача А
Author: Sky
Last saved by: anton.dimitrov

КОНТРОЛНО НА НАЦИОНАЛНИЯ ОТБОР ЗА XVII МОИ
София, 19 Юни 2005

Задача 1. ОПАКОВАНЕ
В бъдещето куриерските услуги ще са напълно автоматизирани. Робот идва до дома ви, взима пратката и я предава в централния офис. Там  се  извършва необходимата обработка и пратките адресирани за един и същ град се събират на едно място. След това те трябва да бъдат опаковани в удобен за транспортиране вид и натоварени на съответния камион. Машината, която опакова пратките приема по два пакета (пакетът е отделна пратка или няколко пратки опаковани заедно), опакова ги и се получава нов пакет, съдържащ началните два. Ако N пратки трябва да бъдат експедирани до някой град, след N – 1 манипулации на машината ще се получи един пакет, съдържащ всичките пратки.
Всеки пакет има големина и цената на опаковането му е равна на големината на пакета. Големината на пакет, получен от опаковането на два други пакета е сума на големините на съставящите го два. Напишете програма PACK, която определя минималната цена за опаковането на всички пратки в един пакет, използвайки гореописаната машина.
На първия ред на стандартния вход е зададен броят на пратките – естествено число N (2 ≤ N ≤ 500_000). Следват N реда, всеки от които съдържа по едно естествено число P_i –  големината на i-тата пратка (P_i ≤ 1 000 000). В 50% от тестовете броят на пратките няма да бъде по-голям от 4000.
На единствения ред на стандартния изход програмата трябва да изведе минималната цена за опаковането на всичките пратки в един пакет.
ПРИМЕР
Вход 4 1 1 1 1 | | Изход 8

КОНТРОЛНО НА НАЦИОНАЛНИЯ ОТБОР ЗА XVII МОИ
София, 19 Юни 2005

Задача 2. ИГРА
Онуфри и Пенчо са големи фенове на игрите. Те обичат да играят всякакви игри и навсякъде. За разлика от Пенчо, който обича игрите главно защото са източник на развлечение, Онуфри обича да анализира всяка нова игра, за да не загуби от Пенчо.
Съвсем наскоро, ровейки в библиотеката, Пенчо намерил книга, в която е описана извънредно интересна игра. Играят двама души, като се редуват да правят ходове върху безкрайна шахматна дъска, стълбовете и редовете на която са номерирани с естествените числа 1,2,3,.... Стълбовете са номерирани от ляво на дясно, а редовете − от горе на долу. Върху дъската са разположени N пула (N ≤ 100 000) така, че във всеки стълб и във всеки ред има най-много един пул. Играчът,  който е на ход, избира един от пуловете (например от клетката в стълб S и ред R)  и го премества в клетка S’,R  от същия ред (S’< S) или в клетка S, R’ от същия стълб (R’< R), като няма право да прескача или да настъпва с пула, който мести, ред или стълб, на който има друг пул. Губи този, който не може да направи ход.
След като започнали да играят играта и Онуфри загубил безславно няколко партии от по-опитния си съперник, той решил да промени това веднъж завинаги и да намери начин да победи Пенчо. За съжaление Онуфри има проблеми при работа с числа по-големи от 5 и затова трудно ще изпълни решението си. Помогнете му, като напишете програма BGAME, която по зададено раположение на пуловете преди ход на Онуфри да намира такъв ход, че както и да играе Пенчо след това, Онуфри да може да спечели.
На първия ред на стандартния вход е зададено числото N. На всеки от следващите N реда са зададени по две числа (по-големи или равни на 1 и по-малки от 1073741824), съответно стълба и реда на който се намира поредният пул. Пуловете са номерирани от 1 до N в реда, в който са зададени във входа.
На стандартния изход програмата трябва да изведе един ред, който трябва да съдържа 3 числа I, D и L, които описват хода, като I е номерът на пула, който се премества, D е 1, ако ходът е в стълб и 2, ако ходът е в ред, а L е броят позиции, на които се премества пула. Гарантирано е, че съществува поне един ход, който да удоволетворява горните условия.
ПРИМЕР 1							         ПРИМЕР 2
Вход 2 2 1 5 5 Изход 2 2 1 | | Вход 3 3 1 2 2 5 6 Изход 3 2 3

КОНТРОЛНО НА НАЦИОНАЛНИЯ ОТБОР ЗА XVII МОИ
София, 19 Юни 2005

Задача 3. ФАБРИКА
Мечо Пух реши да си построи фабрика за мед. Инвестира (почти) всичкия мед, който има във фабриката и ето, че дойде големият ден, в който Пух трябва да я пусне в действие! Но се появи проблем – той все още не е наел работници... Пух има нужда от точно K на брой работника, за да функционира фабриката му – ни повече, ни по-малко. Замисли се Мечо кои от приятелите си да наеме, така че да не обиди никой от тях. Мисли, мисли, но нищо не измисли. Накрая изяде един буркан мед и му дойде наум следната гениална идея: ще състави списък на всички свои приятели и ще ги оцени по два показателя. Първият показател ще бъде възрастта, а вторият – теглото. Така например Прасчо е по-млад и по-лек от Йори, който пък е по-лек, но по-стар от Тигър. След това ще ги раздели на N групи по всеки от двата показателя. Групите и по двата показателя са номерирани с целите числа от 1 до N, като група i съдържа по-млади (или по-леки) животни от група j тогава и само тогава, когато i<j. Всеки приятел на Пух попада в точно една група по тегло и точно една група по възраст.

Така на всяко животно в гората Пух съпостави две числа – група по възраст и група по тегло. След това той ще се изхитри и ще постави в гората обява, че търси за фабриката си работници, които са едновременно не по-стари от някаква възрастова група и не по-тежки от някаква категория тегло. Така няма да обиди никой, а ще постигне целта си – ще наеме точно K от приятелите си.. Но как да разбере какви горни граници да обяви? Тук вече се появи проблем. За щастие Мечо Пух разбра, че в България точно по това време има състезание, на което се събират най-изобретателните умове в областта на информатиката, и реши да остави на тях да му помогнат да намери точните възраст и тегло, които да обяви в гората.

За нещастие списъкът с данните на животните е поверителен и Мечо не може да Ви го предостави, но може да ви дава отговор на следния въпрос: “Колко животни има в гората, които са едновременно в група по възраст с номер не по-голям от P и в група по тегло с номер не по-голям от Q?”. Освен това, понеже времето е пари (а с всеки изминал ден Пух губи от меда, който фабриката можеше да произвежда), решението Ви трябва да отговори на Пух с колкото се може по-малко запитвания.

Напишете програма factory, която да помогне на Пух.

В началото на изпълнението си Вашата програма трябва да извика функцията 

void init(long *K, long *N);
procedure init(var K: LongInt; var N: LongInt);

която ще ви даде информация колко работника иска да наеме Пух, както и на колко групи е разделил Пух приятелите си по двата показателя. Вашата програма може да задава въпроси само за целите числа в интервала [1;N],[1;N].

След това Вашата програма може да се обърща към библиотечната функция 

long ask(long P,long Q); 
function ask(P,Q : LongInt):LongInt;

Тази функция връща броят на приятелите, които са едновременно в група по възраст с номер не по-голям от P и в група по тегло с номер не по-голям от Q. В случай, че P<1, P>n, Q<1 или Q>n, извикването се счита за невалидно и програмата Ви получава 0 точки за съответния тест. 

Когато определи отговора, решението Ви трябва да извиква функцията

void answer(long P,long Q);
procedure answer(P,Q: LongInt);

Числата P и Q трябва да са такива, че животните, отговарящи на условията, обявени от Пух, са точно K на брой. Гарантирано е, че такива две числа със сигурност има.

Ограничения: 
1≤N≤1024 

Оценяване: Ако програмата Ви не извика функцията init() преди някоя от функциите ask() и answer(), извика функцията init() повече от веднъж, извика функцията ask() повече от веднъж за едни и същи P и Q, даде грешен отговор или направи невалидно извикване към функцията ask(), то тя ще получи 0 точки за съответния тест. В противен случай, ако програмата Ви намира верен отговор и прави не повече от M запитвания, тя ще получи пълния брой точки за съответния тест. Ако програмата ви направи повече от М запитвания, тя ще получи 0 точки. Числото M е функция на N (т.е. не зависи от останалите параметри на теста), такава че всеки тест с размер N  може да бъде решен с не повече от М запитвания.

Пример:

init() | N=3 K=4 | Има 3 групи по тегло и 3 групи по възраст. Пух иска да наеме 5 работника
ask(2,3) | 7 | Има 7 кандидата, които са едновременно в групи 1 или 2 по възраст и групи 1,2 или 3 по тегло
ask(1,1) | 2 | Кандидатите в група 1 по възраст и група 1 по тегло са двама
ask(1,3) | 4 | Кандидате в група 1 по възраст и групи 1, 2 или 3 по тегло са общо трима.
answer(1,3) | - | Ако Пух определи за възрастова граница 1-ва група и граница за  теглото 3-та група, то ще има точно K кандидата за работата.

За да тествате решението си, създайте файл factory.in в директорията, в която се намира модула. Файлът има следния формат: на първия ред съдържа две цели числа F и N – съответно броят на приятелите на Пух и броят на групите. Всеки от следващите F реда трябва да съдържа по две цели числа всеки, описващи групата по възраст и групата по тегло на поредния приятел. Входният файл трябва да завършва с едно цяло число K – колко приятели иска да наеме Пух.

Модулът ще създаде изходен файл factory.out – на първият му ред ще е записан броят на заявките, които Вашето решение прави или -1 в случай на грешка. Вторият ред на файла ще съдържа текстова информация, описваща развитието на играта.

Пример:
factory.in
10 3
1 1
1 2
2 3
3 1
3 3
1 1
1 3
2 2
3 1
2 2
4