Alexander Malinov

Вашата задача е да напишете програма, която намира максималната възможна дължина на M-те тръби, които могат да бъдат изрязани от първоначалните тръби на Марто.

Вход

На първия ред от конзолата се прочита числото N – броят на тръбите на Марто.

На втория ред от конзолата се прочита числото М – броят на тръбите, от които Марто се нуждае.

На следващите N реда се четат дължините на тръбите на Марто.

Входните данни винаги ще бъдат валидни и в описания формат. Няма нужда да ги проверявате допълнително.

Изход

На единствения ред от изхода трябва да изведете максималния възможен размер на М-те тръби. Ако е невъзможно тръбите да бъдат разрязани по дадените критерии, изведете „-1“.

Ограничения

• 
  N ще бъде между 1 и 20 000 включително.
  
• 
  M ще бъде между 1 and 2 000 000 000 включително.
  
• 
  Размерите на тръбите ще бъдат между 1 и 2 000 000 000.
  
• 
  Разрешено време за работа на програмата: 0.1 секунди.
  
• 
  Разрешена памет: 16 MB.
  

Примери

В първия пример можем да разрежем тръбите на 6 части (всяка с дължина 100).

Във втория пример можем да разрежем първата тръба на 5 части (200, 200, 200, 200, 3), втората на 4 части (200, 200, 200, 177), третата тръба на 3 части (200, 200, 44) и четвъртата тръба на 3 части(200, 200, 155). След тези разрязвания ще имаме точно 11 тръби с размер 200. Разрязванията са оптимални, защото не можем да разрежем тръбите на 11 части с размер 201.

Задача 4 – Джедайска медитация

Преди много, много години, в далечна галактика, бутновниците и Галактическата Империя водили война. След битката на Ендор и свалянето на Галактическата Империя, Люк Скайуокър направил нова Академия на Джедайте, която се намирала на Явин 4. В новата Академия, майстор джедай Скайуокър въвел ред за ежедневната медитация на всички джедай. Първи били на ред майсторите джедай, след тях рицарите джедай, а падауаните били последни. Независимо кога дойде майстор джедай, той минавал пред всички рицари джедай и падауани докато не застане след друг майстор джедай. Рицарите джедай минавали пред всички падауани, докато стигнат до друг рицар джедай.

Вход

На първия ред на стандартния изход се намира числото N.

На следващия ред се намират N на брой джедаи, наредени на опашката за медитация. Всеки джедай представлява буква m (master), k(knight) или p(padawan) и число, пр. k12, m3, p111. Всеки джедай има уникален номер и не може да има двама джедай с еднакви кодове, например: може да има джедай с кодове p1 и k1, но не може да има k1 и k1.

Входните данни ще са винаги валидни и в описания формат.

Изход

На единствения ред на стандартния изход трябва да се изведе джедайте в реда, в който те ще медитират, разделени с една шпация.

Ограничения

• 
  0 < N <= 100 000
  
• 
  Разрешено време за работа на програмата: 0.10 секунди.
  
• 
  Разрешена памет: 16 MB.
  

Примери

Задача 5 – Еволюция

Група учени от Националния Институт за Наблюдение на ДНК на Живите Амебоподобни провеждали експеримент, който целял да установи начина на еволюция на вид водорасли. На този етап те се опитват да установят как тези водорасли са се научили да се хранят. За целта те извършвали наблюдения върху множество от възможни екосистеми с популация от водорасли. Една екосистема се представя като правоъгълна мрежа от клетки с целочислени координати, като всяка клетка съдържа информация дали в нея има храна, водорасло или е празна. Учените искали да установят кои са най-перспективните и най-неперспективните популации. Една популация се счита за по-перспективна от друга ако средното Манхатаново разстояние от водорасло до храна е по-малко. Освен това, популации, в които общия брой клетки с храна е повече от 2 пъти по-малък от броя на клетки с водорасли, се считат за безкрайно неперспективни (т.е. за обречени). Обратно, ако броя на водорасли е повече от 2 пъти по-малък от броя на клетки с храна, тази популация се счита за безкрайно перспективна (идеална). Манхатаново разстояние между клетките (R₁,C₁) и (R₂,C₂) се изчислява като |R₁ - R₂| + |C₁ - C₂|. Тъй като учените не разбират от програмиране, от вас се очаква да съставите програма, която да им помогне да намерят търсените популации.

Вход

Следва N пъти въвеждане на 2 числа – Ri и Ci означаващи размера на i-тата популация, като след тези 2 числа следват Ri реда с по Ci символа разделени с интервал. Символите могат да бъдат:

Входните данни ще са винаги валидни и в описания формат.

Изход

На първия ред на стандартния изход изведете индексите на най-перспективните популации в нарастващ ред по номера на индекса. Ако има две популации с еднаква перспектива, да се изведе тази с по малък индекс.

На втория ред на стандартния изход изведете индексите на най-неперспективните популации в нарастващ ред по номера на индекса. Ако има две популации с еднаква перспектива, да се изведе тази с по малък индекс. Популациите са индексирани с номерата от 1 до N.

Ограничения

• 
  1 <= N <= 100 000; 1 <= Kmin, Kmax <= 50 000
  
• 
  2 <= Ri,Ci <=10; 1 <= брой *, брой # в една популация <=10
  
• 
  Разрешено време за работа на програмата: 2.20 секунди. Разрешена памет: 128 MB.
  

Примери

Задача 6 – Думи

Даден е текст на латиница и списък с думи (на латиница). Да се напише програма, която намира за всяка входна дума броя уникални думи в текста, които съдържат всяка една от буквите на съответната входна дума.

За дума в текста се счита всяка последователност от съседни латински букви, оградени от разделители или начало / край на текст. За разделители се считат всички символи, които не са латински букви. Разлика между главни и малки букви не се прави.

Вход

Входните данни ще са винаги валидни и в описания формат.

Изход

Изходът трябва да съдържа точно W реда, всеки от които във формат "дума -> брой уникални думи в текста". Думите трябва да се изписват точно както са дадени във входния файл (без да се конвертират към малки букви).

Ограничения

• 
  Броят редове T в текста ще е в интервала [1 … 10 000]
  
• 
  Броят входни думи W ще е в интервала [1 … 1 000]
  
• 
  Дължината на думите в текста и на входните думи е до 50 символа
  
• 
  Размерът на входния файл няма да превишава 1 MB
  
• 
  Разрешено време за работа на програмата: 0.5 секунди. Разрешена памет: 64 MB
  

Примери

Задача 7 – Метро

В голям град една от линиите на метрото се състои от поредица от N станции: начална, втора, трета, …, последна. Известно е разстоянието в минути между всеки две поредни станции (цяло число). Ето пример с част от Софийското метро:

В началната станция влаковете пристигат винаги празни и на последната станция винаги слизат всички пътници. Понеже влаковете са напълно автоматизирани и безпилотни, те винаги се движат точно по разписание и никога не правят непредвидени забавяния, престои или закъснения. Чрез съвременни наблюдателни камери и специализиран софтуер в централата на метрото постоянно пристига информация за всеки отпътуващ влак: от коя станция тръгва, в колко часа на коя дата, в коя посока, колко пътници са слезли и колко пътници са се качили. Счита се, че ако в даден влак в някой момент има повече от P пътника, той е препълнен.

Дадена ви е информация за определена линия на метрото: имената на станциите от първата до последната и разстояния между всеки две съседни станции в минути. Дадени са ви и данните от камерите за качващи се и слизащи пътници от всяка гара. Данните от камерите могат да постъпват в случаен ред поради несъвършенства в комуникационната мрежа. Ако за даден влак липсва информация за дадена дата и час, считаме, че в този момент във влака никой не се е качил и никой не е слязъл. Липсващи данни е нормално да има, например когато системата с камерите на някоя гара е повредена. На последната спирка на даден влак камери няма и информация не се подава, тъй като се очаква всички пътници да слязат от влака.

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

Вход

На първия ред стои броят станции N (цяло положително число). На следващия един ред стоят станциите и разстоянията между тях в следния формат:

Изход

Ако не е засечено нито едно препълване на влак, отпечатайте "OK". В противен случай за всеки ред с информация от камерите, в който е засечено препълване на влак, отпечатайте по един ред в следния формат:

Ограничения

• 
  Броят станции N е цяло число в интервала [1 … 500]
  
• 
  Броят редове с данни от камерите C е цяло число в интервала [1 … 300 000]
  
• 
  Границата за препълване на влака е цяло число P в интервала [1 … 1000]
  
• 
  Всички дати (на входа и на изхода) са в 24-часове формат, без водещи нули за ден, месец и час. Правилно изписване е "1.6.2012 6:03". Грешни изписвания: "1.6.2012 06:03", "1.06.2012 6:03", "01.06.2012 6:03", "01.06.2012 06:03".
  
• 
  На една гара се качват и слизат брой пътници в интервала [0 … 500]
  
• 
  Имената на гарите са стандартни наименования на кирилица или латиница (вж. примера)
  
• 
  Разрешено време за работа на програмата: 2.5 секунди
  
• 
  Разрешена памет: 256 MB
  

Примери

Задача 8 – Пържолен комбинексоратор

Автор: Георги Георгиев

Жоро обича пържоли. Обаче никога не му стигат и затова решил да си направи машина, която по дадени пържоли, произвежда други пържоли. Даже измислим гениалното име "пържолен комбинексоратор" за своето гениално устройство.

Устройството работи, като ползва целочислена координатна система, в която в първи квадрант Жоро разполага пържоли. Всяка пържола е във формата на триъгълник, като всеки ъгъл на триъгълника се намира в целочислена точка от координатната система. Първоначално всички пържоли се намират в първи квадрант, тоест имат неотрицателни координати. След това машината започва да работи, като за всяка пържола създава произволен нечетен брой нейни еднакви пържоли (еднакви триъгълници), които могат да се разполагат във всеки квадрант на координатната система. Всяка пържола в координатната система е в точно един квадрант, като евентуално някои нейни координати могат да се намират върху някоя координатна ос. Допълнително, пържолите които машината на Жоро генерира имат някои определени свойства:

• 
  Ако една генерирана пържола е в първи квадрант, то тя или има същите координати като първообраза си, или всичките ѝ координати са отместени еднакво от първообраза ѝ
  
• 
  Ако една генерирана пържола е квадрант различен от първи, то тя или е създадена симетрично на първообраза си спрямо координатните оси, или е създадена симетрично и след това всичките ѝ координати са отместени еднакво от симетричния образ
  

С две думи, можем да си представим, че ако пържолите са триъгълници, то машината създава еднакви на тях триъгълници, като след това евентуално ги премества в някаква посока в първи квадрант, или ги слага симетрично на оригиналните триъгълници (спрямо една или две координатни оси) и допълнително евентуално ги премества в някаква посока в този квадрант, в който са попаднали… май не бяха две думи това.

Машината на Жоро също запазва логове всеки път, когато свърши работата си – в логът стои информацията колко пържоли е имало накрая на генерирането върху координатната система, както и координатите на тези пържоли (отново, това включва оригиналните и генерираните пържоли).

Един ден машината на Жоро почнала да функционира грешно – изяждала материала за точно една генерирана пържола. И понеже пържолите, които Жоро генерира са страшно много, той няма как да разбере колко материал точно е изгубен.

Помогнете на Жоро да живее отново в блаженство, като напишете програма, която по дадени логове с брой общи пържоли на едно поле и целочислени координати на ъглите на пържолите (пържолите са триъгълници), намира площта на пържолата, която е била изядена

Вход

Входните данни се четат от стандартния вход (конзолата).

На първия ред на стандартния вход стои едно число N – броят пържоли (триъгълници).

На всеки един от следващите N реда стоят по 6 цели числа – съответно X и Y координатите на първия, втория и третия ъгъл от триъгълника.

Входните данни ще са винаги валидни и в описания формат.

Изход

Изходните данните трябва да се изведат на стандартния изход (конзолата).

На единствения ред на стандартния изход изведете площта (лицето) на пържолата (фигурата) която машината е изяла.

Ограничения

• 
  N е цяло число, 0 < n < 200 000.
  
• 
  Координатите на обелиските са цели числа в интервала [-2000; 2000].
  
• 
  Числото на изхода трябва да бъде изведено с точност 6 цифри след десетичната запетая.
  
• 
  Разрешено време за работа на програмата: 0.28 секунди.
  
• 
  Разрешена памет: 1 MB.
  

Примери

Примерен вход	Примерен изход	Обяснение
3 1 1 10 0 5 5 20 20 30 25 20 25 40 40 50 45 40 45	20.000000	Уникалният триъгълник е (1,1) (10,0) (5,5) и има площ 20
3 42 43 51 22 67 69 10 2 11 3 12 4 -10 -2 -11 -3 -12 -4	379.500000	Уникалният триъгълник е (42,43) (51,22) (67,69), другите два триъгълника са подобни

Задача 9 – Интернет магазин

Автор: Светлин Наков

Интернет магазинът „112“ поддържа на склад голямо количество продукти. Всеки продукт има име, цена и производител(name, price, producer). Задачата е да се направи модел на интернет магазина, в който да се подберат най-добрите структури от данни, в които ще се запазват продуктите. Да се напише програма, която изпълнява N на брой команди, подадени като вход, като всяка от командите е на отделен ред:

• 
  AddProduct name;price;producer – добавяне на продукт по име, цена и производител. Ако продукт със същото име, цена или производител вече съществува, новосъздаденият такъв не променя съществуващия (повторението на продукт с еднакви характеристики е разрешено). Като резултат командата отпечатва “Product added”.
  
• 
  DeleteProducts name;producer – изтрива продукт или няколко продукта по дадено име или производител. Като резултат командата отпечатва “X products deleted”, където X е броя на изтритите продукти или “No products found”, ако такива продукти не съществуват.
  
• 
  DeleteProducts producer – изтрива всички продукти, произведени от даден производител. Като резултат командата отпечатва “X products deleted”, където X е броя на изтритите продукти или “No products found”, ако такива продукти не съществуват.
  
• 
  FindProductsByName name – намира всички продукти по зададено име на продукт. Като резултат командата отпечатва лист с продукти във формата {name;producer;price}. Продуктите в листа трябва да са подредени по азбучен ред и всеки от тях да е на отделен ред. Ако продукти със зададеното име не съществуват, командата отпечатва “No products found”.
  
• 
  FindProductsByPriceRange fromPrice;toPrice – Намира всички продукти, чиято цена е по-малка или равна на fromPrice и по-малка или равна на toPrice. Като резултат командата отпечатва лист с продукти във формата {name;producer;price}. Продуктите в листа трябва да са подредени по азбучен ред и всеки от тях да е на отделен ред. Ако няма продукти в зададения ценови интервал командата отпечатва “No products found”.
  
• 
  FindProductsByProducer producer – намира всички продукти по зададен производител. Като резултат командата отпечатва лист с продукти във формата {name;producer;price}. Продуктите в листа трябва да са подредени по азбучен ред и всеки от тях да е на отделен ред. Ако продукти за зададения производител не съществуват, командата отпечатва “No products found”.
  

Разгледайте примерите:

Вход

Входът на програмата трябва да се прочита от конзолата.

На първия ред ще бъде даден броя N на командите, които програмата ще трябва да изпълни.

На всеки от следващите N реда ще бъде дадена команда в някой от форматите, описани в условието.

Входните данни ще бъдат валидни и в описания формат. Няма нужда да бъдат проверявани изрично.

Изход

Изходът от програмата трябва да бъде отпечатан на конзолата.

Изходът на програмата трябва да съдържа(отпечатва) информацията от всяка команда, зададена на входа на програмата.

Ограничения

• 
  N е число в интервала [1, 100050]
  
• 
  Всяка дума в командите (например: име на продукт или производител) се състои от букви, цифри и интервали.
  
• 
  Цените са дадени като реални числа с най-много две цифри зад десетичната запетая, (например: 133.58 или 320)
  
• 
  Символът ‘.’ се използва като десетичен разделител.
  
• 
  Цените трябва да бъдат отпечатани с точно две цифри зад десетичната запетая (например: 320.30, а не 320.3 – този формат е грешен)
  
• 
  Разрешено време за изпълнение на програмта: 2.50 секунди.
  
• 
  Разрешена паметта: 256 MB.
  

Пример

Вход

Изход

14 AddProduct IdeaPad Z560;1536.50;Lenovo AddProduct ThinkPad T410;3000;Lenovo AddProduct VAIO Z13;4099.99;Sony AddProduct CLS 63 AMG;200000;Mercedes FindProductsByName CLS 63 AMG FindProductsByName CLS 63 FindProductsByName cls 63 amg AddProduct 320i;10000;BMW FindProductsByName 320i AddProduct G560;999;Lenovo FindProductsByProducer Lenovo DeleteProducts Lenovo FindProductsByProducer Lenovo FindProductsByPriceRange 100000;200000

Product added Product added Product added Product added {CLS 63 AMG;Mercedes;200000.00} No products found No products found Product added {320i;BMW;10000.00} Product added {G560;Lenovo;999.00} {IdeaPad Z560;Lenovo;1536.50} {ThinkPad T410;Lenovo;3000.00} 3 products deleted No products found {CLS 63 AMG;Mercedes;200000.00}

Задача 10 – Събития

Автор: Светлин Наков

Компания иска да разработи календарна система, за да следи различни събития. Всяко събитие има дата, час, заглавие и локация. Системата трябва да може да добавя събития, да трие събития и да извежда списък с предстоящите събития. Вашата задача е да моделирате календарната система и да подберете подходящите структури от данни, в които да пазите събитията. Трябва да напишете програма, която да изпълнява поредица от команди. Всяка команда се състои от един ред и като резултат връща нула, един или повече реда.

Командите са следните:

• 
  AddEvent date | title | location – добавя събитие по дадени дата и час, заглавие и незадължителна локация. Ако локацията не е упомената, командата придобива формата "AddEvent date | title". Ако събитието вече съществува, се добавя отново (т.е. приемат се повторения). Резултатът от изпълнението на командата е “Event added”.
  
• 
  DeleteEvents title – изтрива всички събития, които имат съответното заглавие (без значение от малките и главните букви a.k.a. case insensitive). Резултатът от изпълнението на командата е “X events deleted”, където X броят на изтритите събития или “No events found” (ако не са открити събития с това заглавие).
  
• 
  ListEvents date | count – извежда списък със събитията стартиращи след съотвените дата и час. Броят на изведените събития трябва е count на брой или по-малко (ако не са намерени достатъчно събития). Ако не са открити никакви събития, резултатът от командата трябва да е "No events found". Всяко събитие трябва да се изведе на отделен ред в следния формат "date | title | location". Ако събитието няма локация, трябва да бъде изведено във формат "date | title". Изведените събития трябва да се подредят хронологично по дата и час, след това по заглавие и по локация (във възходящ ред).
  
• 
  End – показва края на поредицата от входящи команди. "End" спира обработката на команди, без да извежда нищо като резултат. Винаги е последната команда в поредицата.
  

Вход

Входните данни се четат от конзолата. Състоят се от поредица команди, всяка на отделен ред.

Входните данни завършват с команда "End".

Входните данни винаги ще бъдат валидни и във описания формат. Няма нужда да ги проверявате допълнително.

Изход

Изходните данни се извеждат на конзолата. Те се състоят от резултатите от всички команди от входните данни.

Ограничения

• 
  Датата и часът (date) винаги ще бъдат въвеждани във формат "yyyy-MM-ddTHH:mm:ss" и трябва да бъдат извеждани в същия. Датите винаги ще бъдат в следния диапазон [01.01.2000T00:00:00…01.01.2020T00:00:00]. Тоест "2012-03-09T14:01:54" е валидна дата, но "2011-1-1T1:1:1" и "2011-3-22 6:43:28" не са.
  
• 
  Името (title) и локацията (location) ще се състоят от думи на латиница (с дължина от 1 до 1000 букви) и няма да съдържат символите "|" и "\n", както и интервали в началото и края.
  
• 
  Бройката на изведените събития от командата ListEvents т.е. count, винаги ще бъде в диапазона [1…100].
  
• 
  Има по един интервал вляво и вдясно от всеки “|” символ във входните данни.
  
• 
  Има по един интервал между всяка команда и нейните аргументите.
  
• 
  Входните данни няма да надвишават 2.5 MB.
  
• 
  Разрешеното време за работа на програмата е 1.00 секунда. Разрешената памет е 64 MB.
  

Съвет

Помнете, че при сортиране на елементи, липсата на стойност (null) е преди всяка друга стойност.

Примери

Примерен вход

Примерен изход

AddEvent 2012-01-21T20:00:00 | party Viki | home AddEvent 2012-03-26T09:00:00 | C# exam AddEvent 2012-03-26T09:00:00 | C# exam AddEvent 2012-03-26T08:00:00 | C# exam AddEvent 2012-03-07T22:30:00 | party | Vitosha ListEvents 2012-03-07T08:00:00 | 3 DeleteEvents c# exam DeleteEvents My granny's bushes ListEvents 2013-11-27T08:30:25 | 25 AddEvent 2012-03-07T22:30:00 | party | Club XXX ListEvents 2012-01-07T20:00:00 | 10 AddEvent 2012-03-07T22:30:00 | Party | Club XXX ListEvents 2012-03-07T22:30:00 | 3 End

Event added Event added Event added Event added Event added 2012-03-07T22:30:00 | party | Vitosha 2012-03-26T08:00:00 | C# exam 2012-03-26T09:00:00 | C# exam 3 events deleted No events found No events found Event added 2012-01-21T20:00:00 | party Viki | home 2012-03-07T22:30:00 | party | Club XXX 2012-03-07T22:30:00 | party | Vitosha Event added 2012-03-07T22:30:00 | party | Club XXX 2012-03-07T22:30:00 | party | Vitosha 2012-03-07T22:30:00 | Party | Club XXX

Telerik Algo Academy 2012	of	facebook.com/TelerikAlgoAcademy

Каталог: svn -> algo-academy
algo-academy -> Alexander Malinov
algo-academy -> Alexander Malinov
algo-academy -> Alexander Malinov
algo-academy -> Alexander Malinov
algo-academy -> Alexander Malinov
algo-academy -> Alexander Malinov
algo-academy -> Alexander Malinov
algo-academy -> Alexander Malinov

Изтегляне 228.32 Kb.

Сподели с приятели: