Alexander Malinov



Дата22.07.2016
Размер169.76 Kb.



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

academy.telerik.com







Задача 1 – Двоични пароли


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

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

Вход


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

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

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

Изход


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

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


Ограничения


  • Дължината на шаблона ще е не повече от 60 символа.

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

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

Примери


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

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

Обяснение

01001110

1

Единствената възможна парола е 01001110

1***0

8

Възможните пароли са: 10000, 10010, 10100, 10110, 11000, 11010, 11100, 11110

***101***

64

От този шаблон могат да се получат 64 на брой различни пароли.


Задача 2 – Цветни зайци


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

Котаракът Стиви посетил града на зайците и попитал няколко от тях следния въпрос: „Ако не броиш себе си, колко зайци с еднакъв на твоя цвят, живеят в града?“. Всеки от попитаните зайци казал истината като бил попитан само веднъж от котарака.

Помогнете на Стиви да разбере най-малко колко зайци живеят в града.

Вход


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

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


На всеки следващ ред в конзолата се прочита по едно число, което представлява отговора на всеки от попитаните зайци.

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


Изход


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

Единственият ред трябва да съдържа най-малко колко зайци живеят в града.


Ограничения


  • Броят на зайците, които котаракът Стиви е попитал е между 1 и 50, включително.

  • Всеки отговор на попитаните зайци, съдържа число в интервала [0, 1000000]

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


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

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

9

2

2



44

2

2



2

444


2

2


499

Примери


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

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

Обяснение

4

1

1



2

2


5

Ако има 2 заека с лилав и 3 заека с черен цвят (вижте картинката от условието), то тогава котаракът получава отговорите, описани в примерния вход след като попита 4-ри от тях.



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

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

1

0


1


Задача 3 – Делители


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

Дадена е редица цифри. Създайте цяло число, като използвате всеки елемент на редицата точно по един път. Ако една и съща цифра присъства няколко пъти в редицата, то тя трябва да бъде използвана точно толкова пъти. Намерете числото с най-малък брой делители. За делител се броят не само простите числа. Ако има няколко числа с еднакъв брой делители и всички те отговарят на предното условие, то намерете най-малкото от тях. Цифрата „0“ може да бъде използвана за водеща в числата например 06 е числото 6 (за повече яснота вижте втория пример).

Вход


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

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

На всеки от следващите N реда стои поредния елемент от редицата.

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


Изход


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

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


Ограничения


  • Броят на членовете на редицата (N) може да бъде между 1 и 5, включително.

  • Всяка цифра в редицата е в интервала [0, 9]. Поне една от цифрите в редицата не е нула.

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

Примери


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

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

Обяснение

2

1

2



21

Като използваме цифрите 1 и 2 може да създадем числата 12 и 21. Делителите на 12 са шест (1, 2, 3, 4, 6 и 12), а тези на 21 са четири (1, 3, 7, 21). Като резултат връщаме числото 21, защото то има по-малко делители от числото 12.


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

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

3

0

6



0

6




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

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

3

1

2



4

241


Задача 4 – Редица от цветни топчета


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

Един ден малкият Унуфри си играел на топчета. Той имал цяла торба с топчета с еднакъв размер и различни цветове. Унуфри решил да нареди шепа топчета в редица едно след друго и забелязал, че могат се получат много на брой различни редици, но не можал да разбере точно колко. След дълго блъскане Унуфри установил, че броят начини да направи редица от топчетата зависел от броя топчета от всеки един цвят, които участвали в редицата. Например, при 5 топчета, от които 3 са сини и 2 са жълти, той забелязал, че има точно следните 10 варианта да се подредят в редица:



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


Вход


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

Те се състоят от точно един ред, който се състои единствено от главни латински букви. Всяка главна латинска буква съответства на различен цвят. Топчетата са толкова на брой, колкото са буквите, въведени на входа.

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

Изход


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

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


Ограничения


  • Броят топчета е в интервала [1..30]

  • Броят различни цветове е в интервала [1..5]

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

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

Примери



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

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

BYYBB

10




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

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

RYYRYBY

105



Задача 5 – Зиг-Заг Редици


Автор: Дончо Минков

Жоро и Гошо били умни деца. Най-много от всичко обичали да разглеждат странни редици от числа. Така им дошла и идеята да проверят колко редици от числа на зиг-заг могат да генерират с числата от 0 до N-1.


Зиг-заг редица е всяка редица от реда: a0 > a1 < a2 > a3 < a4 > a5 <..., като а0 винаги трябва да е по-голямо от а1 . Помогнете на Жоро и Гошо да преброят колко зиг-заг редици могат да генерират.

Вход


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

От първия ред на стандартния вход прочетете две числа N и K, разделени с шпация (интервал).

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

Изход


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

Изведете броя зиг-заг редици, които са с точно на K брой елемента и са съставени от различни числа от 0 до N-1.


Ограничения


  • 1 <= N <= 20

  • 1 <= K <= 10 и 1 <= K <= N

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

Примери


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

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

Обяснение

4 2

6

Всички възможни редици са:

{0,1},{0,2},{0,3},{1,0},{1,2},{1,3},


{2,0},{2,1},{2,3},{3,0},{3,1},{3,2}

От тях зиг-заг редици са:
{1,0},{2,0},{2,1}
{3,0},{3,1},{3,2}


4 1

4

Всяка редица с 1 елемент е зиг-заг редица

4 4

5

Всички редици с по 4 елента са 24, но само 5 от тях са зиг-заг:

(1, 0, 3, 2),(2, 1, 3, 0),


(2, 0, 3, 1), (3, 1, 2, 0),
(3, 0, 2, 1)



Задача 6 – Сума на подредици


Автор: Валентин Бакоев

Дадена е редица от n цели числа a1, a2, ..., an . Разглеждаме всички възможни подредици, които се получават от дадената чрез премахване на точно k елемента от нея. Напишете програма, която пресмята и извежда сумата на всички числа от всички получени по описания начин подредици.


Вход


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

От първия ред на стандарния вход се въвежда едно цяло число t – брой на тестовите примери. На всеки от следващите t двойки редове от стандартния вход се въвеждат: от първия 2 цели числа – стойностите на n и k, съответно, разделени с интервал, а от втория – n цели числа, разделени с интервали – елементите на редицата в поредния тестов пример.

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

Изход


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

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


Ограничения


  • 0 < n < 1000

  • -1000 < ai < 1000 за i= 1,2, ..., n

  • 0 ≤ k ≤ 5, k

  • 1 ≤ t ≤ 10

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

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

Примери


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

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

2

4 2 40


1 2 3 4

5 3


1 –5 7 10 –3

30

40


Имаме два тестови примера (t = 2). В първия n = 4, k = 2, а елементите на редицата са 1,2,3,4. Всички възможни подредици, с премахнати 2 елемента са:

{1,2} Сума = 3

{1,3} Сума = 4

{1,4} Сума = 5

{2,3} Сума = 5

{2,4} Сума = 6

{3,4} Сума = 7

Общият сбор на сумите е 30.Решението за втората редица е еквивалентно.


Задача 7 – Кръгове


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

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

Муньо забелязал още, че някои подредби на топчетата могат да се получат от други чрез завъртания и симетрии. Муньо установил, че такива подредби твърде много си приличат и решил да ги счита за еднакви. Например следните 10 подредби Муньо счита за еднакви с точност до завъртания и симетрии и сред тях Муньо вижда само едно уникално подреждане (кое да е от тях):

Муньо доста се заиграл с топчетата и дни наред се опитвал да разбере как точно може да сметне броя уникални кръгове, в които може да подреди шепа топчета, ако знае с по колко топчета от всеки цвят разполага. Например, при 5 топчета, от които 2 са сини и 2 са жълти и 1 е оранжево, той установил, че има точно 4 уникални начина да се подредят в кръг:



За съжаление Муньо така и не можал да измисли универсален начин да пресмята броя уникални подредби на шепа топчета в кръг и почти се отказал. Един ден Муньо пак се върнал на тази задача и решил, че трябва да може да измисли някакво решение, ако използва компютъра си.

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

Вход


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

Те се състоят от точно един ред, който се състои единствено от главни латински букви. Всяка главна латинска буква съответства на различен цвят. Топчетата са толкова на брой, колкото са буквите, въведени на входа.

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

Изход


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

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


Ограничения


  • Броят топчета е в интервала [1..10]

  • Броят различни цветове е в интервала [1..10]

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

Примери



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

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

YBBOY

4




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

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

YYYBBBBB

5



Задача 8 – A плюс B на N-та


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

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


Най-вероятно сте запознати с изразa (a+b)2 и знаете, че той съответства на a2 + a1b1 + a1b1 + b2, което ако опростим и подредим по степените на първата променлива (а), като започнем от най-високата към най-ниската, ще получим израза a2 + 2a1b1 + b2. Подобни действия може да правим и с (a+b)3, (a+b)4, и така нататък. Дори не е нужно да ползваме буквите a и b, а може да ползваме които си искаме.

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

Трябва да напишете програма, която изпълнява степенуването на даден израз във формата (a+b)n и изписва полиномът (изразът), който се получава, като този израз трябва да бъде подреден по степените на първата променлива, започвайки от най-високата степен (n) към най-ниската (0). Допълнително, променливи, които са на нулева степен трябва да не се изписват в крайния резултат (защото тяхната стойност е 1).

Вход


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

На първия ред от стандартния вход се въвежда един израз (низ от символи) във формата (a+b), като втория символ (броим от 1) от този израз винаги е символът на първата променлива, а четвъртият символ е винаги символът втората променлива.

На следващия ред се въвежда едно число n, което обозначава степента, на която трябва да бъде вдигнат израза от първия ред

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


Изход


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

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



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

Ограничения


  • n цяло число, 0 < n < 51.

  • символите за всички променливи са малките букви от английската азбука

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

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

Примери


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

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

(a+z)

1


(a^1)+(z^1)

(c+y)

3


(c^3)+3(c^2)(y^1)+3(c^1)(y^2)+(y^3)



Задача 9 – Двоични дървеса


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

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

Веднъж докато пишели нова песничка за дървесата, люцерната, дървесните жаби и смисъла на живота, им хрумнала следната интелектуална задача: ако имат една кофа цветни топки, колко различни двоични дървета могат да построят от тях. Например ако имат една кофа, в която има 1 жълта и 2 сини топки, от тях могат да направят 15 различни двоични дървета (вж. фигурата).

Задачата се оказала трудна и макар и двамата музиканти да са учили висша математика в техническия университет, не могли да измислят формула, по която да сметнат колко различни двоични дървета може да построят от множество цветни топки, като се поставя по една топка във всеки връх.

Можете ли да помогнете на Дидо и Бойко да си решат задачата, като им напишете програма, която смята броя двоични дървеса по дадено множество цветни топки?

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

Вход


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

Те се състоят от точно един ред, който се състои единствено от главни латински букви. Всяка главна латинска буква съответства на различен цвят. Топките са толкова на брой, колкото са буквите, въведени на входа.

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

Изход


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

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


Ограничения


  • Броят топки е в интервала [1..20]

  • Броят различни цветове е в интервала [1..20]

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

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

Примери



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

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

YBB

15




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

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

YYYBBRBBB

2450448


Задача 10 – Роботизирана Зомби Камила


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

Бат' ви Жоро се хванал да разследва как точно са построени пирамидите, като силно предполагал, че извънземни имат пръст в цялата работа. Съответно навлязъл в дебрите египетски, като междувременно се обадил на разни фирми туристически, за да търси отговор на този толкова отдавна съществуващ въпрос.


Озовал се веднъж в една доста странна пирамида. Какво било странното ли? Ами била куха, колкото една негова бивша съученичка. И на това отгоре цялата била осеяна с обелиски, а в центъра ѝ имало един по-голям обелиск. На земята била начертана нещо като координатна мрежа – много на брой квадрати, със страна 1 м, които били долепени един до друг (хората на това му викат плочки, между другото). Дори всеки обелиск се намирал точно на един от ъглите на точно 4 плочки. Централния обелиск също се намирал на центъра на 4 плочки. Така ако си представим, че централният обелиск е центърът на координатната система, то всички останали обелиски ще се намират на точки с целочислени координати в тази координатна система.

Жоро се зачел в текста върху големия централен обелиск. Там пишело: "За да спреш великия пазач на пирамидата, трябва да свържеш с въже един обелиск към централния. След това въжето ще изгори. След това трябва да вържеш друг обелиск към централния и въжето пак ще изгори. След като повториш това за всеки един обелиск, ще трябва да започнеш наново, но този път ще вържеш всеки 2 обелиска към централния, като отново след всяко връзване въжето ще изгаря. Ще повтаряш това, докато не стигнеш до момента, в който трябва да свържеш всички обелиски към централния. Плочките по земята са свещени. Нямаш право да ги пресичаш с въжето. Можеш обаче да поставяш въжето по ръбовете им."

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

И точно докато си мислел това, пирамидата се разтресла и в единия ѝ ъгъл се телепортирал стражът на пирамидата – роботизираната зомби камила, които извънземните оставили да пази пирамидата (да, имат лош вкус към пазачи, съгласен съм). Тя почнала да преследва Жоро из пирамидата, с цел да му причини лоши неща. За щастие не била особено бърза (зомбитата обикновено са бавнички, поне тези които аз познавам).

Жоро знае какво трябва да направи, за да я спре, но не е сигурен дали има достатъчно въже. Да се мъчи ли изобщо да я спира, или да си плюе на петите? Помогнете му да прецени.

Напишете програма, която по даден брой обелиски n и целочислени координати за всеки обелиск намира общо колко метра въже ще е нужно да се свърже първо всеки един обелиск към центъра на координатната система, след това всеки два обелиска и т.н. докато се стигне до всеки n обелиска включително, като се спазва условието, че въжето може да се опъва само по ръбовете на плочките, и че за всяко свързване на комбинация от обелиски с централния се ползва ново въже (забележка: тъй като центъра на координатната система се намира на ръбовете на точно 4 плочки, то следва, че координатните оси ще са разположени точно по ръбове на плочки). Хайде, че камилата идва!


Вход


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

На първия ред от стандартния вход се въвежда числото n – броя на обелиските (без централния). На всеки от следващите n реда се въвеждат 2 цели числасъответно координатите на всеки един обелиск.

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

Изход


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

На единствения ред от стандартния изход трябва да се изведе единствено цяло число – дължината на въжето, което е нужно. Тъй като резултатът може да е много голям, той трябва да бъде изведен по модул 18446744073709551616 (подсказка: 18446744073709551615 е най-голямото число, което може да се съдържа в 64-битов цeлочислен тип без знак, каквито са ulong в C# и unsigned long long в C++).


Ограничения


  • n е цяло число, 0 < n < 51.

  • Координатите на обелиските са цели числа в интервала [-1000; 1000].

  • Числото на изхода трябва да бъде изведено по модул 18446744073709551616.

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

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

Примери


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

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

Обяснение

2

1 0


1 1

6

Комбинациите са (1-ва точка), (1-ва точка и 2-ра точка), (2-ра точка). Получава се (1) + (1 + 2) + (2) като сбор от разстоянията първо от (0,0) до (1,0) и от (0,0) до (1, 1),

след това от (0,0) до (1,1)



1

2 2


4

Имаме само една комбинация, тъй като имаме само 1 обелиск и разсоянието до него, спазвайки ограничението за движение по ръбовете, е 4.













Telerik Algo Academy 2012

of

facebook.com/TelerikAlgoAcademy





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

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