Alexander Malinov



Дата02.07.2017
Размер190.46 Kb.
#24858
ТипЗадача



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

academy.telerik.com







Telerik AlgoAcademy – Тренировъчно състезание – 26 април 2012

Задача 1 – Трибоначи


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

Редица на Трибоначи наричаме такава последователност от числа, при която всяко следващо число се образува като сума на предните три елемента от редицата:



Напишете програма, която намира N-тия елемент от редицата на Трибоначи по дадени N и първите три елемента от редицата. Математически казано: по зададени Т1, Т2 и T3, намерете TN.

Вход


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

На първия и единствен ред на конзолата ще бъдат дадени последователно числата T1, T2, T3 и N, разделени с точно 1 интервал.

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

Изход


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

На единствения ред на стандартния изход трябва да изведете N-тия елемент от зададената редица на Трибоначи.


Ограничения


  • T1, T2 и T3 ще бъдат цели числа в интервала между -2 000 000 000 и 2 000 000 000.

  • Числото N ще е положително цяло число интервала между 1 и 20, включително.

  • Всички числа в дадената редица ще са винаги в интервала между -1018 и +1018

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

Примери


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

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

Обяснение

1 1 1 4

3

Редицата е: 1, 1, 1, 3, 5, 9, ...

2 3 4 5

16

Редицата е: 2, 3, 4, 9, 16, 29, ...

Задача 2 – СуперСума


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

СуперСума е функция, която се дефинира като:


  • СуперСума(0, N) = N, за всяко положително цяло число N.

  • СуперСума(K, N) = СуперСума(К - 1, 1) + СуперСума(K - 1, 2) + … + СуперСума(K - 1, N), за всяко положително цяло число K и N.

Напишете програма, която по зададени K и N, връща резултата от извикването на СуперСума(K, N).

Вход


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

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

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

Изход


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

На единствения ред на стандартния изход трябва да изведете стойността на СуперСума(K, N)


Ограничения


  • K е цяло положително число между 1 и 14, включително.

  • N е цяло положително число между 1 и 14, включително.

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

Примери


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

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

Обяснение

1 3

6

Когато K = 1, СуперСума е равно на суумата на първите N = 3 числа: 1 + 2 + 3 = 6

2 3

10

СуперСума(2, 3) = СуперСума(1, 1) + СуперСума(1, 2) + СуперСума(1, 3) = 1 + 3 + 6 = 10

Задача 3 – Скоби

Дадена е последователност от символите "(", ")" и "?".


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

Ако вземете валиден математически израз и премахнете от него всичко друго освен скобите ще получите валиден израз от скоби. За пример: има точно 2 валидни израза от скоби с дължина точно 4: ()() и (()).


Вход


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

Последователността от скоби и въпросителни знаци ще бъде дадена на единствения ред от входа.

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

Изход


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

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


Ограничения


  • Дължината на последователността от символи е между 1 и 80, включително.

  • Броят възможности за образуване на валидни изрази винаги е между -1018 и 1018.

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

Примери


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

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

Обяснение

????(?

2

Решенията са: ()()() и (())()

()(?

1

Има само 1 решение и то е: ()()

??????

5

Има 5 възможни решения: ((())), (())(), ()(()), (()()) и ()()()

Задача 4 – Китара


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

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

Програмата ви ще получи списък от C на брой цели числа, където i-тото число означава с колко иска Боби да промени силата на звука преди i-тата песен (съответно първото число означава промяната преди първата песен, второто – преди втората и т.н.) . Освен това програмата ви ще получи и едно цяло число B – първоначалната сила на звука на китарата и едно цяло число M – най-високата възможна сила на звука за китарата. Тоест, Боби не може да свири с по-малка сила на звука от 0 и не може да свири с по-голяма сила на звука от М (но може с точно 0 или точно М). Програмата трябва да сметне колко е максималната сила на звука, която Боби може да ползва за свиренето на последната песен. Ако няма начин да се направят последователно всичките промени в силата на звука от списъка, без силата да стане над M или под 0, програмата трябва да изведе -1.

Вход


Входните данни се четат от конзолата.

На първия ред от входа ще бъде числото C – броят на числата, с които Боби иска да смени силата на звука на китарата си.

На втория ред ще има C на брой цели числа – където всяко поредно число означава промяната, която Боби иска да направи в силата на звука преди поредната песен.

На следващия ред ще бъде числото B – първоначалната сила на звука на китарата на Боби.

На следващия ред ще бъде числото M – максималната сила на звука на китарата на Боби.

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


Изход


Изходните данни се печатат на конзолата.

На единствения ред от изхода програмата трябва да изведе или числото -1, или максималната сила на звука, с която Боби може да изсвири последната песен.


Ограничения


  • C ще бъде число от 1 до 50 включително

  • Всяка промяна на звука ще бъде число от 1 до M

  • M ще бъде от 1 до 1000, включително

  • B ще бъде от 0 and M, включително

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

Примери



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

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

3

5 3 7


5

10


10





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

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

14

74 39 127 95 63 140 99 96 154 18 137 162 14 88

40

243


238





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

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

4

15 2 9 10

8

20


-1




Задача 5 – Играта на живота


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





0

1

2

0

съсед

съсед

съсед

1

съсед

КЛЕТКА

съсед

2

съсед

съсед

съсед
Игри, игри, игри и пак игри. Видяхме „Играта на играчките“, „Игра на тронове“, „Игрите на глада“, и още доста други. И щом сме тръгнали с това, защо да не поговорим за една друг игра. Животът също си има игра. Или ако трябва да сме честни, математиците си имат „играта на живота“. И понеже математиците обичат всичко да им е чисто и подредено (това беше най-нелепата лъжа, която съм написвал), тази игра се играе на компютър.

Сега, знам, че сте виждали игри с един човек, игри с двама и игри с много, ама тази е малко по-различна. Тази се играе сама. Да бе, сериозно, играта сама си се играе, вие само гледате. Ето как става цялата магия.

Игралното поле е матрица с R реда и C колони (тоест, таблица, двумерен масив, както искате го наречете). За всяка клетка в игралното поле има две възможности – тя е или жива, или нежива (мъртва). Освен това всяка клетка си има съседи (в същия смисъл на съседи в матрица) – ако клетката е на позиция [row, col], то съседите ѝ ще бъдат тези на позиции: [row-1, col-1], [row-1, col], [row-1, col+1], [row, col-1], [row, col+1], [row+1, col-1], [row+1, col], [row+1, col+1] (стига това да са също клетки от матрицата, тоест да не са извън границите на тази матрица)

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



  • Размножаване (раждане) – ако клетката е била мъртва и е имала точно 3 живи съседа, тя става жива в новото поколение

  • Пустеене – ако клетката е била мъртва и е имала по-малко или повече от 3 живи съседа, тя остава мъртва в новото поколение

  • Оцеляване – ако клетката е била жива и е имала 2 или 3 живи съседа, тя остава жива в новото поколение

  • Смърт от изолация – ако клетката е била жива и е имала по-малко от 2 живи съседа, тя става мъртва в новото поколение

  • Смърт от пренаселване – ако клетката е била жива и е имала повече от 3 живи съседа, тя става мъртва в новото поколение

На всеки ход, за всяка една клетка от новото поколение се проверява кое събитие ѝ се е случило. Така се получава новото поколение. На картинката е показано примерно развитие в матрица с 2 реда и 2 колони. В първо поколение 3-те първоначални клетки оцеляват (всяка има по 2 живи съседа), а в мъртвата клетка е станало размножаване (тя има точно 3 живи съседа). Във второ поколение всяка една клетка има точно 3 живи съседа и затова всички клетки оцеляват.


Играта винаги започва от някакво начално (нулево) поколение и се развива оттам нататък. Поколението след началното ще наричаме първо, след това второ и така нататък. Следователно можем да преброим колко живи клетки има в едно поколение ако знаем началното поколение и номерът на поколението, в което трябва да броим. Така например на картинката в първото и второто поколение имаме точно по 4 живи клетки

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


Напишете програма, която по даден номер на поколение (N), размери на игрално поле (R и C) и начално поколение върху това поле, преброява живите клетки в полето в поколението с дадения номер (N).

Вход


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

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

На втория ред се намират числата R и C, разделени с един интервал – броят редове и броят колони в игралното поле (матрицата)

На всеки от следващите R реда има по C числа разделени с интервали, като всяко от тези числа е 0 или 1 и описва състоянието на клетката на тази позиция в дъската в началното поколение. За жива клетка – 1, за нежива (мъртва) клетка – 0.

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


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

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

Обяснение

26

2 2


1 0

1 1


4

Примерът е същият като картинката. Още на първия ход живите клетки са 4 и оттам нататък в този случай не настъпват промени.

2

3 5


0 0 0 1 0

0 1 0 1 1

0 1 1 1 1


4

Ето как изглеждат първото и второто поколение:

0 0 1 1 1

0 1 0 0 0

0 1 0 0 1


0 0 1 1 0

0 1 0 0 1

0 0 0 0 0

Изход


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

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


Ограничения


  • N < 2048

  • 1 < R, C < 128

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

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



Задача 6 – Таен език


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

Малката Сиси и приятелите ѝ разбрали, че родителите им следят „тайната“ им комуникация. Затова те решили да си измислят нов език, който да им позволи да си говорят свободно. В крайна сметка измислили език, в който съобщенията се преобразуват по специален начин.

Програмата ви ще получи списък от всичките валидни думи в езика. Тези думи се състоят единствено от латински малки букви. Едно съобщение представлява конкатенация на валидни думи от езика (т.е. „залепени“ думи). Всяка една валидна дума от езика може да се среща в съобщението 0 или повече пъти. Това, което прави езика специален, е че всяка дума може да бъде преобразувана, като буквите и се разместят преди да бъдат записани в съобщението. Цената на преобразуване на една дума е дефинирана като броят на позициите в първоначалната и променената дума, между в които има разлики. Например, ако „abc“ е пренаредена към „abc“ цената е 0, ако е пренаредена към „acb“, „cba“ или „bac“ цената е в (има по 2 позиции в които първоначалната и крайната дума се различават), а ако е пренаредена към „bca“ или „cab“, цената е 3.


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

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

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

Вход


Входните данни се четат от конзолата.

На първият ред от входа ще бъде съобщението.

На следващия ред ще се намира числото N – броят думи в езика.

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

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

Изход


Изходните данни се печатат на конзолата.

На единственият ред от изхода програмата трябва да изведе най-ниската цена на трансформация.


Ограничения


  • Съобщението ще съдържа от 1 до 50 (включително) малки латински букви ('a'-'z').

  • Броят на думите в езика ще бъде от 1 до 50 включително.

  • Всяка дума от езика ще съдържа от 1 до 50 (включително) малки латински букви ('a'-'z').

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

Примери


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

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

Пояснение

neotowheret

4

one two three there




8


Следните пренареждания са възможни:

  • "one" -> "neo" с цена 3

  • "two" -> "tow" с цена 2

  • "three" -> "heret" с цена 3

  • "there" -> "heret" с цена 5

Тоест поредицата{"one", "two", "three"} носи смисъла на "neotowheret". Общата цена на трансформацията е 3 + 2 + 3 = 8

sepawaterords

3

this is meaningful




-1


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



Задача 7 – Задачи в Академията


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

В Академията на Телерик се дават задачи за решаване. Първо трябва да решите задача 0. След решаването на задачата i, можете да преминете директно на следващата (i+1), или да прескочите и да отидете на по-следващата (i+2). Не е разрешено да прескачате повече от 1 задача. {0, 2, 3, 5} е валиден ред на решаване, но {0, 2, 4, 7} не е валиден ред, защото от 4 до 7 прескачаме 2 задачи.

Даден е масив от цели числа приятност (започващ от 0), където приятност[i] показва колко ви е приятна задачата i. Можете да спрете да решавате задачи, когато разликата между най-приятната и най-неприятната задача стане по-голяма от числото разнообразие. Ако това не се случи, трябва да решите всички задачи. Напишете програма, която по дадени масив приятност и число разнообразие връща минималният брой задачи, които трябва да решите, изпълнявайки тези изисквания.

Вход


Входните данни се четат от конзолата.

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

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

На следващият ред ще бъде дадено числото разнообразие.

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

Изход


Изходните данни се печатат на конзолата.

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


Ограничения


  • N ще бъде от 1 до 50 включително

  • Всеки от елементите в приятност ще бъде между 0 и 1000 включително

  • Разнообразие ще бъде между 1 и 1000 включително

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

Примери


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

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

Пояснение

3

1 2 3


2

2


Решаваме нулевата задача и след това втората.

5

1 2 3 4 5

3


3


Явно трябва да решим поне нулевата и последната задача. Решаваме нулевата, прескачаме, решаваме, пак прескачаме и решаваме. Общо 3 задачи.

9

6 2 6 2 6 3 3 3 7

4


2


Решаваме нулевата и първата задача и можем да спрем.

Задача 8 – Врачка


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

Докато Пешо се разхождаше из морските ни курорти, наслаждавайки се на летния си отпуск, той се натъкна на стара несебърска врачка, която твърдеше, че може да му предксаже бъдещето срещу скромните пет лева.

Врачката твърдяла, че може да вижда много далеч в бъдещето (до 2500 дни напред), само че предсказанията ѝ не били много точни. Тя можела само да каже дали определен ден ще бъде хубав или лош. Освен това, тя можела да познава без да сгреши за най-много R поредни дни, и да сгреши за най-много W поредни дни.

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


Вход


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

На първия ред на стандартния вход ще бъдат зададени две числа: R и W. На втория ред на стандартния вход ще има низ S, състоящ се само от главните латински букви G и B. Всяка поредна буква от този низ означава предсказанието за съответния пореден ден като с G са означени добрите дни, а с B – лошите. В низа няма да има интервали или нови редове.

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

Изход


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

На единствения ред на стандартния изход изведете намерения максимален брой хубави дни,.


Ограничения


  • S не съдържа повече от 2500 знака.

  • 1 <= R,W <= 2500

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

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

Примери



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

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

4 1

GGGG


4

Тъй като R = 4, врачката може да е познала и за четирите дни




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

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

2 2

GGGG


3

Тук врачката не може да е права за всички дни. Начин за постигане на 3 хубави дни е предсказанията да бъдат:

вярно,грешно,вярно,вярно





Задача 9 – Архитект


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

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

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

Помогнете на Пешо да изчисли колко е максималната височина на сграда, която може да постигне с кубчетата с които разполага.


Вход


Входните данни се четат от стандартния вход (конзолата). На първия ред на стандартния вход ще бъде зададено едно естествено число N – броят на блокчетата на Пешо. На следващите N реда ще бъдат зададени по 3 естествени числа x, y и z, описващи размерите на поредното кубче. Входните данни ще са винаги валидни и в описания формат.

Изход


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

Ограничения


  • 1 <= N <= 15 1 <= x, y, z <= 10 000 000

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

Примери



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

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

5

10 10 10


50 50 50

40 40 40


20 20 20

30 30 30


150

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



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

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

2

20 20 20


30 30 10

30

Тук най-доброто решение е да поставим второто блокче със страната 30х30 към пода и след това първото блокче върху него. Друго валидно решение е да изпозваме само второто блокче със страната 30х10 към пода.
Задача 10 – Стая


Автор: Стефан Аврамов

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

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

Напишете програма, която покрива стаята с минимален брой дъски.


Вход


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

1-ви ред: Цяло число Т (1 <= Т <= 2); 2-ри ред: Две цели числа N и M (1 <= N, M <= 10)

3-ти до N+2-ри ред: N реда с по M символа – матрицата на стаята, като ‘.‘ означава непокрита клетка, а ‘#’ означава стълб

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


Изход


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

При Т = 1: изведете минималния брой дъски, необходими за покриване на стаята (при 60% от тестовете това е изпълнено)

При Т = 2: изведете решение с минимален брой дъски. Всяка дъска получава уникална главна буква от ‘A’ до ‘Z’ и замества символът ‘.’ от входа върху мястото, което покрива. Изведете така полученото решение. При няколко възможни решения – изведете най-малкото лексикографски при конкатениране на редовете последователно в един низ. Гарантирано е, че ако Т = 2, броят необходими дъски ще бъде <= 26.

Ограничения


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

Примери


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

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

Обяснение

1

2 4


#...

###.


2

Възможно решение е:

#XXX


###Y

2

3 4


....

###.


..#.

AAAA

###B


CC#B

AAAB

###B


CC#B също е решение, но при конкатениране на редовете:

“AAAA###BCC#B” < “AAAB###BCC#B”




У С П Е Х!







Telerik Algo Academy 2012

of

facebook.com/TelerikAlgoAcademy






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




©obuch.info 2024
отнасят до администрацията

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