Alexander Malinov



Дата06.01.2017
Размер228.32 Kb.
ТипЗадача



bul.“Alexander Malinov“ №33., Sofia, 1729, Bulgaria

academy.telerik.com







Telerik Algo Academy – November 2012 – Data Structures and STL

Задача 1 – Сортиране


Автор: Николай Костов

Дадено е числото N и списък с N на брой числа в интервала между 1 и 4 000 000 000, включително. Дадено е и числото X. Сортирайте списъка от числа в нарастващ ред по техния остатък с числото X. Ако две числа имат еднакъв остатък с X, сортирайте ги по тяхната стойност също в нарастващ ред.

Вход


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

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


Изход


На единствения ред на стандартния изход трябва да се изведат всички числа, сортирани по посочения начин.

Ограничения


  • N е цяло число между 1 и 100 000. X е цяло число между 1 и 4 000 000 000

  • Разрешено време за работа на програмата: 0.25 секунди. Разрешена памет: 16 MB.

Примери


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

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

9 4

1 2 3 4 5 6 7 8 9



4 8 1 5 9 2 6 3 7


10 1

2 55 100 293 1 2 9 1337 233 11



1 2 2 9 11 55 100 233 293 1337


1 3999999999

4000000000



4000000000

Задача 2 – Задачи


Автор: Николай Костов

Обичате да решавате задачи. Знаем. Също така знаем, че предпочитате да решавате първо най-лесните задачи. Ако две задачи са ви еднакво лесни ги решавате по азбучен ред. Ако нямате достатъчно време за решаване на задачи (например защото играете Diablo 3) си записвате задачите някъде и си ги пазите за момента, в който ще имате повече време за решаването им. Ако обаче ви се решават задачи и списъкът ви от задачи е празен, тогава просто си почивате.

Задачата ви е да напишете програма, която изпълнява бързо следните 2 команди:


  • Добавяне на задача в списъка ви от задачи за решаване:
    Форматът на командата е: "New {Complexity} {Task_name}". Трите части от командата са разделени от интервал. {Complexity} представлява сложността на задачата и е дадена като цяло число между 1 и 1 999 999 999, включително. Задача със сложност 3 е по-сложна от задача със сложност 2. {Task_name} представлява името на задачата и е дадено като последователност от малки латински букви ('a' – 'z'). Дължината на името на задачата е между 1 и 6 символа, включително.

  • Решаване на задача от списъка със задачи:
    Командата "Solve" взима най-лесната задача от вашия списък и я изкарва от него. Ако повече от 1 задачи са еднакво лесни, тогава се изкарва тази с лексикографски най-малкото име. Ако нямате задачи в списъка, вашата програма трябва да изкара "Rest".

Вход


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

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

На всеки от следващите N реда се намира по 1 команда в описания по-горе формат.

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


Изход


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

За всеки ред, който съдържа командата "Solve", изкарайте по 1 ред съдържащ името на задачата за решаване или "Rest", ако такава няма.


Ограничения


  • N е цяло число между 10 и 50 000, включително.

  • Поне една от командите ще е "Solve".

  • Разрешено време за работа на програмата: 0.25 секунди. Разрешена памет: 16 MB.

Примери



Вход

Изход

10

New 5 tk


New 8 tn

New 8 taa

New 8 tb

New 8 t


Solve

Solve


Solve

Solve


New 1999999999 task

tk

t

taa



tb




Вход

Изход

10

New 4 tf


New 5 tfive

New 4 tff

Solve

Solve


Solve

Solve


New 1 t

New 1 t


Solve

tf

tff


tfive

Rest


t

Задача 3 – Тръби


Автор: Николай Костов

Марто е много известен Пернишки бияч. Той има N тръби с различни размери. Марто има и M-1 приятели. Неговите приятели също се нуждаят от тръби, за да се бият.


Помогнете на Марто да разреже тръбите си на точно M части с еднаква дължина. Тази дължина трябва да е максималната възможна (по-голяма тръба = по-добър бияч).

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

Вход


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

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

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

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

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

Изход


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

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


Ограничения


  • N ще бъде между 1 и 20 000 включително.

  • M ще бъде между 1 and 2 000 000 000 включително.

  • Размерите на тръбите ще бъдат между 1 и 2 000 000 000.

  • Разрешено време за работа на програмата: 0.1 секунди.

  • Разрешена памет: 16 MB.

Примери



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

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

3

6

100



200

300


100





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

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

4

11

803



777

444


555

200

В първия пример можем да разрежем тръбите на 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. В новата Академия, майстор джедай Скайуокър въвел ред за ежедневната медитация на всички джедай. Първи били на ред майсторите джедай, след тях рицарите джедай, а падауаните били последни. Независимо кога дойде майстор джедай, той минавал пред всички рицари джедай и падауани докато не застане след друг майстор джедай. Рицарите джедай минавали пред всички падауани, докато стигнат до друг рицар джедай.


Жоро и Гошо са падауани в новата Академия на Джедайте на Явин 4. Те са много надъхани да усъвършенстват свойте умения със Силата и затова нямат търпение да дойте техния ред за медитация. Жоро и Гошо искат да разберат кога ще дойде и техния ред за медитация. По дадени N на брой джедай, наредени на опашката за медитация, изведете реда, който те ще медитират.

Вход


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

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

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

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


Изход


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

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


Ограничения


  • 0 < N <= 100 000

  • Разрешено време за работа на програмата: 0.10 секунди.

  • Разрешена памет: 16 MB.

Примери


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

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

Обяснение

3

m1 k1 p1


m1 k1 p1

Реда не се променя, тъй като джедайте са се наредили в правилния ред

7

p4 p2 p3 m1 k2 p1 k1



m1 k1 k2 p3 p2 p4 p1

m1 отива преди всички останали джедай и застава най-отпред, k2 минава всички падауани (p4, p2 и p3) и застава след m1. k1 минава падауаните (p4, p2, p1 и p1) и застава след k2. Накрая остават падауаните в реда, в които са се наредили първоначално

5

k2 m2 m1 p1 k1



m2 m1 k2 k1 p1

m2 и m1 пренават k2, k1 преминава p1.

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


Автор: Иван Тодоров

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

Вход


На първия ред на стандартния вход се задават три числа N – броя на популациите, Kmin – броя на търсените най-неперспективни популации и Kmax – броя на търсените най-перспективни популации.

Следва 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.

Примери



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

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

3 1 1

3 3


. . *

. . .


# . .

3 5


* . . * .

. # . . #

. . . . .

5 3


* * *

. . .


. . #

. # .


# . .

2

1


Средните стойности на манхатановите разстояния от водорасло до храна за съответните популации са: 4, 1, 3.

Номер 2 е най-перспективна, а номер 1 най-неперспективна.






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

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

5 2 2

3 3


. . *

. . .


# . .

3 5


* . . * .

. # . . #

. . . . .

5 3


* * *

. . .


. . #

. # .


# . .

4 4


* * . .

. . . #


. . . #

. # # #


3 3

* * *


. . .

# . .


2 4

1 5



Средните стойности на манхатановите разстояния от водорасло до храна за съответните популации са: 4, 1, 3,

безкрайно перспективна, безкрайно неперспективна. Най-перспективни са 2 и 4, най-неперспективни: 1 и 5.





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


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

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

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

Вход


На първия ред на стандартния вход стои едно число Т – брой редове в текста. Следват T реда с текст на латиница. На следващия ред има едно число W. Следват W реда с по една дума на ред (непразна последователност от латински букви).

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


Изход


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

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


Ограничения


  • Броят редове T в текста ще е в интервала [1 … 10 000]

  • Броят входни думи W ще е в интервала [1 … 1 000]

  • Дължината на думите в текста и на входните думи е до 50 символа

  • Размерът на входния файл няма да превишава 1 MB

  • Разрешено време за работа на програмата: 0.5 секунди. Разрешена памет: 64 MB

Примери


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

6

Telerik Software Academy has several divisions:

- Telerik Kids Academy - free training in C++ programming basics in 19 Bulgarian towns

- Telerik School Academy - software development for school students - 3 days every month

- Telerik Algo Academy - trains school students in algorithms - 2 full days every month

- Telerik Software Academy - trains anyone interested in modern software development

Telerik Software Academy is based in Sofia, Bulgaria.

7

goal



me

liker


IT

Kaspichan

a

ring


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

Пояснения

goal -> 2

me -> 3


liker -> 1

IT -> 5


Кaspichan -> 0

a -> 16


ring -> 3

Algo, algorithms

Academy, development, modern

Telerik

Telerik, training, trains, algorithms, interested



-

Software, Academy, has, several, training, programming, basics, Bulgarian, days, Algo, trains, algorithms, anyone, based, Sofia, Bulgaria

training, programming, Bulgarian

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


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

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



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

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

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


Вход


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

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



(първа станция) --> (разстояние) --> (втора станция) --> (разстояние) --> … --> (последна станция) --> (разстояние)

Следва броя на редовете с информация от камери C (цяло положително число). Следват точно C реда, описващи информацията, пристигнала от камерите в следния формат:

(дата и час във формат ден.месец.година час:минута) | име на станция | брой слезли пътници | брой качили се пътници | посока на движение на влака (<< или >>)

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

Изход


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

Ако не е засечено нито едно препълване на влак, отпечатайте "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

Цариградско --> 4 --> Младост-3 --> 3 --> Младост-1 --> 2 --> Мусагеница --> 2 --> Г.М.Димитров --> 3 --> Жолио Кюри --> 8 --> Стадиона --> 2 --> СУ

21

20.11.2012 18:54 | Жолио Кюри | 32 | 17 | <<



20.11.2012 18:53 | Младост-1 | 22 | 12 | >>

20.11.2012 18:57 | Г.М.Димитров | 57 | 42 | >>

20.11.2012 23:50 | Цариградско | 15 | 0 | >>

20.11.2012 18:40 | Цариградско | 75 | 0 | >>

21.11.2012 19:12 | Стадиона | 27 | 96 | >>

20.11.2012 18:50 | Младост-3 | 7 | 3 | >>

21.11.2012 00:01 | Г.М.Димитров | 157 | 12 | >>

20.11.2012 18:46 | Цариградско | 15 | 0 | >>

20.11.2012 18:57 | Г.М.Димитров | 57 | 42 | <<

20.11.2012 19:02 | Стадиона | 62 | 76 | >>

20.11.2012 19:04 | Младост-3 | 7 | 3 | <<

20.11.2012 19:08 | Стадиона | 106 | 27 | >>

20.11.2012 18:46 | Стадиона | 17 | 85 | <<

1.1.2012 0:00 | Жолио Кюри | 120 | 15 | <<

20.11.2012 18:44 | Младост-3 | 15 | 3 | >>

20.11.2012 18:51 | Г.М.Димитров | 47 | 22 | >>

20.11.2012 19:01 | Младост-1 | 122 | 12 | <<

20.11.2012 18:44 | СУ | 106 | 27 | <<

7.3.2009 23:59 | Жолио Кюри | 100 | 0 | <<

20.11.2012 18:54 | Жолио Кюри | 28 | 32 | >>

100


21.11.2012 0:01 | Г.М.Димитров | >> | 160

20.11.2012 19:04 | Младост-3 | << | 155

20.11.2012 19:08 | Стадиона | >> | 123

1.1.2012 0:00 | Жолио Кюри | << | 105

20.11.2012 18:51 | Г.М.Димитров | >> | 112

20.11.2012 19:01 | Младост-1 | << | 151

20.11.2012 18:54 | Жолио Кюри | >> | 108

Задача 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






Поделитесь с Вашими друзьями:


База данных защищена авторским правом ©obuch.info 2019
отнасят до администрацията

    Начална страница