Задачи - УПП, Седмица 4, 27.10.2023

GitHub classroom: classroom.github.com/a/jqKaO1ny

Задача 1 - Числен редактор

Получавате число N, което ще е в обхвата от 1 до 10000000000000000000. Вашата програма трябва да поддържа няколко операции върху това число, включително копиране на редица от цифри в него и поставянето им в друга част на числото. Подробните операции ще получите по-късно, и не е нужно да валидирате вход или дали след дадена операция числото се побира в типа данни.

Първо, в тази задача индексите на цифрите в едно число започват от 1 и се броят от ляво на дясно. Тоест, в числото “481395” на индекс 1 имаме 4, на индекс 2 имаме 8 и на индекс 6 имаме 5.

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

ВАЖНО: В решението НЕ може да изполвате масиви, вектори, …, както и каквито и да е функции, които не сте написали вие!

Подточка а) Примитивните функции

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

Имплементирайте функциите:

Подточка б) Композитните функции

Сега е време да имплементираме съществената логика в задачата. Използвайки само примитивните функции, имплементирайте функциите:

Подточка в) Вход и изход

Последно, време е да имплементираме интерфейса на програмата. Както вече казахме, първия вход е числото N с което ще извършим операция.

След това приемаме буква, която определя нашата (композитна) функция, като за всички функции използваме първата буква в името им, освен за cut, за която използваме x. Тоест, c означава, че ще “copy”-ваме, p че ще “prepend”-ваме, x че ще “cut”-ваме и так. нат.

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

Примери

Вход Изход
x 8504830028402847111 9 6 7 8504832840280047111
p 8 968824945839039458 9688249458390394588
a 968824945839039458 1 9688249458390394581
r 9938175002843839 1 10 86998385021 86998385021843839

Задача 2 - Умножение на полиноми

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

Пример: първото число е 13, a второто е 3052. Побитово 13 = 1101, тоест ще имаме

x³ * 1 + x² * 1 + x¹ * 0 + x⁰ * 1

След това, от второто получаваме всеки коефициент, става

3 * x³ * 1 + 0 * x² * 1 + 5 * x¹ * 0 + 2 * x⁰ * 1

Финално, нашия полином, кодиран от числата 13 и 3052 е 3x³ + 2.

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

ВАЖНО: В решението НЕ може да изполвате масиви, вектори, …, както и каквито и да е функции, които не сте написали вие!

Задача 3 - Дъската на Зар

Името си го измислих, няма връзка с нещо :)

Дъската на Зар е една много проста игра. Имаме два играча, които играят върху квадратна дъска, като на всяка “клетка” има цифра (0 до 9). Всеки играч има сегашната си позиция върху дъската и брой точки.

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

Пример: ако играем с дъска 5х5, намираме се на реда “25486” и позицията на първия играч е първата, тогава ходът му изглежда така (с “V” показваме къде се намира):

V
25486
Прочита цифрата 2, значи трябва да се премести с две клетки на дясно

  V
25486
Прочита цифрата 4, събира я към общия брой точки, сега се премества с една клетка на дясно

   V
25486
Прочита цифрата 8, трябва да се премести с осем клетки на дясно
Обаче редът е твърде къс, премества се с една клетка и на следващия си ход ще се премести със 7 клетки надясно

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

Тоест, ако първия ни ред е “131324” (в дъска 6x6), тогава първия играч ще посети първите 5 клетки (и ще има 6 точки), и чак тогава ще дойде реда на втория играч, който ще започне с 6тата клетка. Възможно е първия играч да посети всяка клетка в първия ред (примерно “131313”), и тогава втория играч ще трябва да се пробва да започне от втория ред. Възможно е през цялата игра втория играч никога да не започне.

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

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

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

ВАЖНО: В решението НЕ може да изполвате масиви, вектори, …, както и каквито и да е функции, които не сте написали вие!

Упътване: Лесно се получава, ако занулим цифрите които първия играч е посетил. Още по-лесно става ако използвате функции от първата задача.

︽