Alexander Malinov
Изтегляне 169.76 Kb.
|
- Навигация на страницата:
- Задача 1 – Двоични пароли
- Изход Изходните данни трябва да се изведат на стандартния изход (конзолата). Единственият ред трябва да съдържа най-малко колко зайци живеят в града. Ограничения
- Задача 4 – Редица от цветни топчета
- Задача 5 – Зиг-Заг Редици
- Задача 6 – Сума на подредици
- Задача 8 – A плюс B на N-та
- Задача 9 – Двоични дървеса
- Задача 10 – Роботизирана Зомби Камила
Задача 1 – Двоични паролиАвтор: Николай Костов Ася е млада хакерка. От скоро тя се занимава с хакване на двоични пароли. Двоичните пароли са последователности от нули и единици. Ася е все още начинаещ хакер и от скоро тя може да намира части от двоични пароли. За съжаление тези пароли не са пълни и липсващите единици или нули са заместени със звездички. Така се получава една последователност от единици, нули и звездички, които образуват шаблон. Помогнете на Ася да сметне колко са възможните различни пароли, които могат да се образуват от тези шаблони. Всяка звездичка в шаблона може да бъде както единица, така и нула.ВходВходните данни се четат от стандартния вход (конзолата). На единствения ред на стандартния изход се намира шаблонът, който Ася е успяла да получи. Входните данни ще са винаги валидни и в описания формат.
ИзходИзходните данни трябва да се изведат на стандартния изход (конзолата). На единствения ред на стандартния изход трябва да се изведе броят на възможните двоични пароли, които могат да се получат от шаблона на Ася. Ограничения
Примери
Задача 2 – Цветни зайциАвтор: Николай Костов К Помогнете на Стиви да разбере най-малко колко зайци живеят в града.
ВходВходните данни се четат от стандартния вход (конзолата). На първия ред от козолата се прочита броя на зайците, които котаракът Стиви е попитал. На всеки следващ ред в конзолата се прочита по едно число, което представлява отговора на всеки от попитаните зайци. Входните данни ще са винаги валидни и в описания формат. ИзходИзходните данни трябва да се изведат на стандартния изход (конзолата). Единственият ред трябва да съдържа най-малко колко зайци живеят в града. Ограничения
Задача 3 – ДелителиАвтор: Николай Костов Дадена е редица цифри. Създайте цяло число, като използвате всеки елемент на редицата точно по един път. Ако една и съща цифра присъства няколко пъти в редицата, то тя трябва да бъде използвана точно толкова пъти. Намерете числото с най-малък брой делители. За делител се броят не само простите числа. Ако има няколко числа с еднакъв брой делители и всички те отговарят на предното условие, то намерете най-малкото от тях. Цифрата „0“ може да бъде използвана за водеща в числата например 06 е числото 6 (за повече яснота вижте втория пример).ВходВходните данни се четат от стандартния вход (конзолата). На първия ред от козолата се намира цяло естествено число N - броя елементи на редицата. На всеки от следващите N реда стои поредния елемент от редицата. Входните данни ще са винаги валидни и в описания формат. ИзходИзходните данните трябва да се изведат на стандартния изход (конзолата). На единствения ред от изхода трябва да изведете числото, което отговаря на критериите, описани по-горе. Ограничения
Примери
Задача 4 – Редица от цветни топчетаАвтор: Светлин Наков Един ден малкият Унуфри си играел на топчета. Той имал цяла торба с топчета с еднакъв размер и различни цветове. Унуфри решил да нареди шепа топчета в редица едно след друго и забелязал, че могат се получат много на брой различни редици, но не можал да разбере точно колко. След дълго блъскане Унуфри установил, че броят начини да направи редица от топчетата зависел от броя топчета от всеки един цвят, които участвали в редицата. Например, при 5 топчета, от които 3 са сини и 2 са жълти, той забелязал, че има точно следните 10 варианта да се подредят в редица: 
Помогнете на Унуфри да намери броя различни начини, по които може да подреди топчетата си. ВходВходните данни се четат от стандартния вход (конзолата). Те се състоят от точно един ред, който се състои единствено от главни латински букви. Всяка главна латинска буква съответства на различен цвят. Топчетата са толкова на брой, колкото са буквите, въведени на входа. Входните данни ще са винаги валидни и в описания формат.
ИзходИзходните данните трябва да се изведат на стандартния изход (конзолата). На единствения ред на стандартния изход изведете намерения брой различни редици. Ограничения
Примери
Задача 5 – Зиг-Заг РедициАвтор: Дончо Минков Жоро и Гошо били умни деца. Най-много от всичко обичали да разглеждат странни редици от числа. Така им дошла и идеята да проверят колко редици от числа на зиг-заг могат да генерират с числата от 0 до N-1.Зиг-заг редица е всяка редица от реда: a0 > a1 < a2 > a3 < a4 > a5 <..., като а0 винаги трябва да е по-голямо от а1 . Помогнете на Жоро и Гошо да преброят колко зиг-заг редици могат да генерират. ВходВходните данни се четат от стандартния вход (конзолата). От първия ред на стандартния вход прочетете две числа N и K, разделени с шпация (интервал). Входните данни ще са винаги валидни и в описания формат.
ИзходИзходните данни трябва да се изведат на стандартния изход (конзолата). Изведете броя зиг-заг редици, които са с точно на K брой елемента и са съставени от различни числа от 0 до N-1. Ограничения
Примери
Задача 6 – Сума на подредициАвтор: Валентин Бакоев Дадена е редица от n цели числа a1, a2, ..., an . Разглеждаме всички възможни подредици, които се получават от дадената чрез премахване на точно k елемента от нея. Напишете програма, която пресмята и извежда сумата на всички числа от всички получени по описания начин подредици. ВходВходните данни се четат от стандартния вход (конзолата). От първия ред на стандарния вход се въвежда едно цяло число t – брой на тестовите примери. На всеки от следващите t двойки редове от стандартния вход се въвеждат: от първия 2 цели числа – стойностите на n и k, съответно, разделени с интервал, а от втория – n цели числа, разделени с интервали – елементите на редицата в поредния тестов пример. Входните данни ще са винаги валидни и в описания формат.
ИзходИзходните данни трябва да се изведат на стандартния изход (конзолата). На стандартния изход се извежда получената като резултат сума – на нов ред за всеки тестов пример. Ограничения
Примери
Автор: Светлин Наков Малкият Муньо обича цветните топчета. Той има цяла торба с топчета с еднакъв размер и различни цветове. Веднъж Муньо решил да нареди шепа топчета в кръг едно след друго и забелязал, че могат се получат много на брой различни кръгове, но не можал да разбере точно колко. След дълго блъскане Муньо установил, че броят уникални начини да нареди кръг от топчета зависел от това с колко топчета разполага от всеки един цвят. Муньо забелязал още, че някои подредби на топчетата могат да се получат от други чрез завъртания и симетрии. Муньо установил, че такива подредби твърде много си приличат и решил да ги счита за еднакви. Например следните 10 подредби Муньо счита за еднакви с точност до завъртания и симетрии и сред тях Муньо вижда само едно уникално подреждане (кое да е от тях):
Муньо доста се заиграл с топчетата и дни наред се опитвал да разбере как точно може да сметне броя уникални кръгове, в които може да подреди шепа топчета, ако знае с по колко топчета от всеки цвят разполага. Например, при 5 топчета, от които 2 са сини и 2 са жълти и 1 е оранжево, той установил, че има точно 4 уникални начина да се подредят в кръг: 
За съжаление Муньо така и не можал да измисли универсален начин да пресмята броя уникални подредби на шепа топчета в кръг и почти се отказал. Един ден Муньо пак се върнал на тази задача и решил, че трябва да може да измисли някакво решение, ако използва компютъра си. Помогнете на Муньо като му напишете програма, която той може да преброи уникалните начини за нареждане на шепа топчета в кръг (като завъртените и симетричните варианти на коя да е кръгова подредба се броят само веднъж).
ВходВходните данни се четат от стандартния вход (конзолата). Те се състоят от точно един ред, който се състои единствено от главни латински букви. Всяка главна латинска буква съответства на различен цвят. Топчетата са толкова на брой, колкото са буквите, въведени на входа. Входните данни ще са винаги валидни и в описания формат.
ИзходИзходните данни трябва да се изведат на стандартния изход (конзолата). На единствения ред на стандартния изход трябва да се изведе намереният брой различни уникални подредби на топчетата в кръг, без повторения с точност до симетрии и завъртания. Ограничения
Примери
Задача 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). Ограничения
Примери
Задача 9 – Двоични дървесаАвтор: Светлин Наков Дидо и Бойко са известни музиканти, които напоследък са се запалили по информатиката и много се вълнуват от дървовидни структури данни, комбинаторика и алгоритми, дървета най различни –(балансирани, с изместена тежест, недобалансирани, двоични, троични), всякакви дървеса, различни видове дървесина и икебан, и като цяло се интересуват от дървопреработваща и дърварската индустрия. Веднъж докато пишели нова песничка за дървесата, люцерната, дървесните жаби и смисъла на живота, им хрумнала следната интелектуална задача: ако имат една кофа цветни топки, колко различни двоични дървета могат да построят от тях. Например ако имат една кофа, в която има 1 жълта и 2 сини топки, от тях могат да направят 15 различни двоични дървета (вж. фигурата).
Можете ли да помогнете на Дидо и Бойко да си решат задачата, като им напишете програма, която смята броя двоични дървеса по дадено множество цветни топки? Имайте предвид, че топките с еднакъв цвят са неразличими една от друга и че коренът на дърветата е винаги най-горе, а листата – винаги най-долу, и се прави разлика между ляв и десен наследник, т.е. симетричните спрямо корена дървета се считат за различни (вж. фигурата).
ВходВходните данни се четат от стандартния вход (конзолата). Те се състоят от точно един ред, който се състои единствено от главни латински букви. Всяка главна латинска буква съответства на различен цвят. Топките са толкова на брой, колкото са буквите, въведени на входа. Входните данни ще са винаги валидни и в описания формат.
ИзходИзходните данни трябва да се изведат на стандартния изход (конзолата). На единствения ред на стандартния изход трябва да се изведе намереният брой различни уникални двоични дървета. Ограничения
Примери
Задача 10 – Роботизирана Зомби КамилаАвтор: Георги Георгиев Бат' ви Жоро се хванал да разследва как точно са построени пирамидите, като силно предполагал, че извънземни имат пръст в цялата работа. Съответно навлязъл в дебрите египетски, като междувременно се обадил на разни фирми туристически, за да търси отговор на този толкова отдавна съществуващ въпрос.Озовал се веднъж в една доста странна пирамида. Какво било странното ли? Ами била куха, колкото една негова бивша съученичка. И на това отгоре цялата била осеяна с обелиски, а в центъра ѝ имало един по-голям обелиск. На земята била начертана нещо като координатна мрежа – много на брой квадрати, със страна 1 м, които били долепени един до друг (хората на това му викат плочки, между другото). Дори всеки обелиск се намирал точно на един от ъглите на точно 4 плочки. Централния обелиск също се намирал на центъра на 4 плочки. Така ако си представим, че централният обелиск е центърът на координатната система, то всички останали обелиски ще се намират на точки с целочислени координати в тази координатна система. 
Жоро се зачел в текста върху големия централен обелиск. Там пишело: "За да спреш великия пазач на пирамидата, трябва да свържеш с въже един обелиск към централния. След това въжето ще изгори. След това трябва да вържеш друг обелиск към централния и въжето пак ще изгори. След като повториш това за всеки един обелиск, ще трябва да започнеш наново, но този път ще вържеш всеки 2 обелиска към централния, като отново след всяко връзване въжето ще изгаря. Ще повтаряш това, докато не стигнеш до момента, в който трябва да свържеш всички обелиски към централния. Плочките по земята са свещени. Нямаш право да ги пресичаш с въжето. Можеш обаче да поставяш въжето по ръбовете им." Жоро съответно го напушило на смях. Трябвало да направи всички комбинации от обелиски и да ги върже с централния, без да може да преизползва вече вързаните въжета, щото те изгаряли. На това отгоре въжето му трябва да се движи по ръбовете на плочките, айде няма нужда. И точно докато си мислел това, пирамидата се разтресла и в единия ѝ ъгъл се телепортирал стражът на пирамидата – роботизираната зомби камила, които извънземните оставили да пази пирамидата (да, имат лош вкус към пазачи, съгласен съм). Тя почнала да преследва Жоро из пирамидата, с цел да му причини лоши неща. За щастие не била особено бърза (зомбитата обикновено са бавнички, поне тези които аз познавам). Жоро знае какво трябва да направи, за да я спре, но не е сигурен дали има достатъчно въже. Да се мъчи ли изобщо да я спира, или да си плюе на петите? Помогнете му да прецени. Напишете програма, която по даден брой обелиски n и целочислени координати за всеки обелиск намира общо колко метра въже ще е нужно да се свърже първо всеки един обелиск към центъра на координатната система, след това всеки два обелиска и т.н. докато се стигне до всеки n обелиска включително, като се спазва условието, че въжето може да се опъва само по ръбовете на плочките, и че за всяко свързване на комбинация от обелиски с централния се ползва ново въже (забележка: тъй като центъра на координатната система се намира на ръбовете на точно 4 плочки, то следва, че координатните оси ще са разположени точно по ръбове на плочки). Хайде, че камилата идва! ВходВходните данни се четат от стандартния вход (конзолата). На първия ред от стандартния вход се въвежда числото n – броя на обелиските (без централния). На всеки от следващите n реда се въвеждат 2 цели числа – съответно координатите на всеки един обелиск. Входните данни ще са винаги валидни и в описания формат.
ИзходИзходните данни трябва да се изведат на стандартния изход (конзолата). На единствения ред от стандартния изход трябва да се изведе единствено цяло число – дължината на въжето, което е нужно. Тъй като резултатът може да е много голям, той трябва да бъде изведен по модул 18446744073709551616 (подсказка: 18446744073709551615 е най-голямото число, което може да се съдържа в 64-битов цeлочислен тип без знак, каквито са ulong в C# и unsigned long long в C++). Ограничения
Примери
Каталог: svn -> algo-academy svn -> Phone: (+359) 2 80-99-862; Fax: (+359) 2 80-99-888 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 Изтегляне 169.76 Kb. Сподели с приятели:
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
отаракът Стиви посетил града на зайците и попитал няколко от тях следния въпрос: „Ако не броиш себе си, колко зайци с еднакъв на твоя цвят, живеят в града?“. Всеки от попитаните зайци казал истината като бил попитан само веднъж от котарака. 
