Задача 5: СПИСЪЦИ

Категория: ИТ бизнес

it FORUM

понеделник, 10 Април 2006 0:00ч

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

Зайо много обича реда. Обича всичко да е организирано и подредено. На това се дължи и навикът му да прави списъци. Списък за рождените дни на своите приятели, списък с нещата, които трябва да свърши утре, другата седмица или другия месец, кога трябва да яде мед с Пух или да обсъди важни теми с Бухал като “доматите плод ли са или зеленчук”.
На Зайо често се налага да преработва част от списъците, да обединява или разделя други. Освен това възниква и въпросът кое е най-важното или маловажно действие в някой списък.
Кристофър Робин се интересува не само от компютри, но и от проблемите на приятелите си. Той реши да направи програма, която да помогне на Зайо за организацията на неговите списъци, както и да изпробва своите знания в областта на програмирането. Ние решихме да изпробваме вашите.
Напишете програма LISTS, която поддържа работа със списъци, както е описано по-долу. Списъците съдържат числа, наредени последователно. Всяко число е в интервала [1, 109]. Позициите на числата се номерират от 1 до K, където K е големината на съответния списък. Всеки списък се идентифицира с уникално число в интервала [1, 106]. Програмата трябва да изпълнява следните операции, записани по една на ред във входния файл:
- create - създава нов списък, идентифициран с номер , съдържащ единствен елемент . В момента на изпълнението на командата на стойността няма да отговаря съществуващ списък.
- merge - обединява списъците, отговарящи на и , като след последния елемент на се поставя първият елемент на . Новият списък е идентифициран с , а става невалидна стойност до евентуално следващо дефиниране.
- split - разделя списъка на два списъка, съдържащи съответно числата на позиции от 1 до ( - 1) и от до K, където K е големината на списъка . Списъкът с числата от 1 до ( - 1) запазва номера на първоначалния списък - . Списъкът с числата от до K получава идентификационно число , което няма да отговаря на никой списък към момента на изпълнение на операцията. ще бъде число, по-голямо от 1 и по-малко или равно на K.
- reverse - обръща подредбата на елементите в списъка (първият става последен, вторият става предпоследен и т.н.)
- min - изписва в изходния файл стойността на най-малкия елемент в списъка с номер .
- max - изписва в изходния файл стойността на най-големия елемент в списъка с номер .
- stop – прекратява изпълнението на програмата.
Входните данни са записани в LISTS.INP. Всеки ред съдържа по една команда, както е описано по-горе. Последният ред на файла съдържа командата stop.
Изходният файл LISTS.OUT трябва да съдържа по един на ред отговорите, изисквани от командите min и max, в редa на тяхното появяване във входния файл.

LISTS.INP
create 1 4
create 2 3
merge 1 2
min 1
create 3 10
create 4 7
merge 3 4
max 3
reverse 1
merge 3 1
split 3 4 2
max 2
min 3
stop

LISTS.OUT
3
10
4
3