1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
|
# Задачи - УПП, Седмица 4, 27.10.2023
GitHub classroom: [classroom.github.com/a/jqKaO1ny](https://classroom.github.com/a/jqKaO1ny)
## Задача 1 - Числен редактор
Получавате число `N`, което ще е в обхвата от 1 до 10000000000000000000.
Вашата програма трябва да поддържа няколко операции върху това число, включително копиране на редица от цифри в него и поставянето им в друга част на числото.
Подробните операции ще получите по-късно, и не е нужно да валидирате вход или дали след дадена операция числото се побира в типа данни.
Първо, в тази задача индексите на цифрите в едно число започват от 1 и се броят от ляво на дясно.
Тоест, в числото "481395" на индекс 1 имаме 4, на индекс 2 имаме 8 и на индекс 6 имаме 5.
Всичките операции трябва да бъдат отделени във функции.
Затова, и за улеснение, задачата е разделена на стъпки:
**ВАЖНО:** В решението **НЕ** може да изполвате масиви, вектори, ..., както и каквито и да е функции, които не сте написали вие!
### Подточка а) Примитивните функции
За да имплементираме всички нужни функционалности, първо ще направим няколко супер удобни функции, чрез които ще изразим останалите операции.
Имплементирайте функциите:
- `get`, която приема число, начален индекс и краен индекс (в този ред)
Тя връща подчислото, което започва от началния и завършва в крайния индекс.
Пример: `get(481395, 2, 4)` връща `813`
- `remove`, която приема число, начален индекс и дължина (в този ред)
Връща числото, без "дължина" на брой цифри от началния индекс
Пример: `remove(481395, 3, 3)` връща `485`
- `insert`, която приема число, начален индекс, дължина и число за вмъкване
Връща числото, като на началния индекс намираме началото на вмъкнатото число с дължина "дължина"
Ефектът, е че числото се вмъква на дадения индекс, обаче избутва цифрите в ляво от него, вместо тези от дясно.
Пример: `insert(495, 2, 4, 1001)` връща `4100195`
### Подточка б) Композитните функции
Сега е време да имплементираме съществената логика в задачата.
Използвайки **само** примитивните функции, имплементирайте функциите:
- `copy`, която приема число, начален индекс, дължина и втори начален индекс
Връща числото, като от втория начален индекс, следващите "дължина" на брой цифри съвпадат с "дължина" на брой цифри от първия начален индекс
Пример: `copy(481395, 3, 4, 2)` връща `4139581395`
- `cut`, която приема число, начален индекс, дължина и втори начален индекс
Връща числото, като "дължина" на брой цифри от (стария) начален индекс са преместени във втория начален индекс
Пример: `cut(481395, 3, 4, 2)` връща `413958`
- `replace`, която приема число, начален индекс, дължина и число за замяна
Връща числото, като "дължина" на брой цифри от начален индекс са заменени с числото за замяна
Заменените цифри и числото за замяна **може да имат различни дължини**!
Пример: `replace(481395, 4, 2, 705)` връща `4817055`
- `prepend`, която приема две числа
Връща долепени второто и първото число
Пример: `prepend(395, 81)` връща `81395`
- `append`, която приема две числа
Връща долепени първото и второто число
Пример: `append(395, 81)` връща `39581`
### Подточка в) Вход и изход
Последно, време е да имплементираме интерфейса на програмата.
Както вече казахме, първия вход е числото `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` цифри в десетичния си запис, като след получаване на едно число изпълнявате ходовете на всички играчи.
**ВАЖНО:** В решението **НЕ** може да изполвате масиви, вектори, ..., както и каквито и да е функции, които не сте написали вие!
**Упътване:**
Лесно се получава, ако занулим цифрите които първия играч е посетил.
Още по-лесно става ако използвате функции от първата задача.
|
