Робин Бобин Барабек

@goldolov_na · Регистрация: 31.03.2019

Студворк — интернет-сервис помощи студентам

Робин Бобин Барабек думает, сколько коров и быка он съест на обед. Он берет шестнадцатеричное число. За одно действие он может заменить один из знаков на соседний (0 заменить на 1 или F, А заменить на 9 или В и т.п.). Он ставит себе ограничение сверху на количество действий и старается максимизировать количество подслов BEEF.

Ваша программа в первой строке ввода получает последовательность цифр от 0 до 9 и букв от А до F. Всего не более 100000 знаков. Во второй строке написано ограничение на число ходов. Оно не превышает 1000.

Программа должна напечатать максимальное число подслов BEEF, которое можно получить, не превышая максимального числа ходов.

@eaa · 06.11.2020, 11:35

да вроде ничего сложного. "пробежаться" по строке один раз.
что конкретно не получается?

@goldolov_na · 06.11.2020, 14:49 **[ТС]**

eaa, реализовать(

Добавлено через 1 минуту

Python
1
2
a = input()
n = int(input())

то что смог

Добавлено через 2 часа 50 минут
eaa, можно хотя бы алгоритм выполнения программы без кода?

@htmlprogrammist · 07.11.2020, 20:31

Олимпиадные задания нужно решать самостоятельно))

@dprotas · 10.11.2020, 18:07

Задача красивая.

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

Добавлено через 4 часа 25 минут

Python
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
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
import random
 
B = [5, 6, 7, 8, 7, 6, 5, 4, 3, 2, 1, 0, 1, 2, 3, 4]
E = [2, 3, 4, 5, 6, 7, 8, 7, 6, 5, 4, 3, 2, 1, 0, 1]
F = [1, 2, 3, 4, 5, 6, 7, 8, 7, 6, 5, 4, 3, 2, 1, 0]
 
def subnumb (spisok): #аргумент - список
 
    H = ['0','1','2','3','4','5','6','7','8','9','A','B','C','D','E','F']
    
    res = [0]*len(spisok)
    
    for i in range(len(spisok)):
        for j in range(len(H)):
            if spisok[i] == H[j]:
                res[i] = j
            
 
                
    return res
 
#=====================end-of-function==============
 
#=================investigation of konvertacii cost======
 
def devide4 (lst):
    
    res = []
    elem = []
    
    
    for i in range(len(lst)-3):
        elem1 = []
        elem = lst[i:4+i]
        # stoimoct konvertacii chetverki v BEEF
        s1 = B[elem[0]] + E[elem[1]] + E[elem[2]] +F[elem[3]]
        elem1.append(i)
        elem1.append(s1)
        res.append(elem1)
 
    return res    
#============end-of-finction=============================== 
 
res = 0
 
#===============sting algorithm subs chetverki============
def reduction_sting(list2, res):
    
    global cash
 
 
    if len(list2) < 4 or cash < 0:
        
        return res  
        
    else: 
    
        list3 = devide4(list2)
        print('==========================================')
        print (list3)
        print('==========================================')
        
        sred_stoim = 0
        
        for elem in list3:
            sred_stoim += elem[1]
            
            
        sred_stoim = sred_stoim//(len(list2)-3)    
        
        
        min = list3[0][1]
        i = 0
        min_ind = 0
        
        for elem in list3:
            if elem[1] < min:
                min = elem[1]
                min_ind = i
            i += 1
        
        print(min)
        
        if cash >=  min:
            
            cash -= min
            
            list2[min_ind] = 11
            list2[min_ind+1] = 14
            list2[min_ind+2] = 14
            list2[min_ind+3] = 15
            
            
        
        print('===========================================')
        print('Cash =', cash)
        print('===========================================')
        
        print('===========================================')
        print('list2 =',list2)
        print('===========================================')
        
        res += 1
        
        print('===========================================')
        print('res=', res)
        print('===========================================')
        
        list21 = list2[:min_ind]
        list22 = list2[min_ind+4:]
        
        
        print('===========================================')
        print('list21 =',list21)
        print('===========================================')
        print('list22 =',list22)
    
        if len(list21) < 4:
           
            if len(list22) < 4:
            
                return res
               
            else:
                return reduction_sting(list22, res)
           
        else:
            
            
            if len(list22) < 4 :
                
                return reduction_sting(list21, res)
                   
            else:
                return reduction_sting(list22, reduction_sting(list21, res))
        
        
        
#==================enf-of-function======================
 
#===========schedriy algorithm subs chetverki============
def reduction(list2, res):
    
    global cash
    
    for i in range(0,len(list3),4) :   
        cash -= list3[i][1]
        
        list2[i] = 11
        list2[i+1] = 14
        list2[i+2] = 14
        list2[i+3] = 15
        res += 1
        
    
    print('===========================================')
    print('Cash =', cash)
    print('===========================================')
    
    print('===========================================')
    print('list2 =',list2)
    print('===========================================')
    
    
    
    print('===========================================')
    print('res=', res)
    print('===========================================')
        
    return res     
#==================enf-of-function======================
 
#++++++++++++++++++++++++++BODY++++++++++++++++++++++++++
cash = random.randint(1, 100)
 
print('===========================================')
print('Cash =', cash)
print('===========================================')
 
K = random.randint(10, 100)
A = '0123456789ABCDEF'
stroka = ''
 
list1 = []
for i in A:
    list1.append(i)
 
for i in range(K):
    stroka += list1[random.randint(0, 15)]
 
print('='*50)  
 
print(stroka)# сгенерированная строка
print('='*50)
print('lenght stroki = ', len(stroka))
print('='*50)
 
list = []
for i in stroka:
    list.append(i)
    
print(list)
print('='*50)
 
list2 = subnumb(list)#
 
print('list2 =',list2)
print('**********************************************')
print('**********************************************')
 
list3 = devide4(list2)
print('==========================================')
print (list3)
print('==========================================')
 
sred_stoim = 0
 
for elem in list3:
    sred_stoim += elem[1]
    
    
sred_stoim = sred_stoim//(len(list2)-3) 
 
print('==========================================')
print('sred_stoim =', sred_stoim)
print('==========================================')
 
if cash/sred_stoim > len(list2)//4:
     print('RESULT=', reduction(list2, 0))
else:
     print('RESULT=', reduction_sting(list2, 0))
 
 
print('%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%')

Добавлено через 35 минут
некорректно работала глобальная переменная

Python
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
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
import random
 
B = [5, 6, 7, 8, 7, 6, 5, 4, 3, 2, 1, 0, 1, 2, 3, 4]
E = [2, 3, 4, 5, 6, 7, 8, 7, 6, 5, 4, 3, 2, 1, 0, 1]
F = [1, 2, 3, 4, 5, 6, 7, 8, 7, 6, 5, 4, 3, 2, 1, 0]
 
def subnumb (spisok): #аргумент - список
 
    H = ['0','1','2','3','4','5','6','7','8','9','A','B','C','D','E','F']
    
    res = [0]*len(spisok)
    
    for i in range(len(spisok)):
        for j in range(len(H)):
            if spisok[i] == H[j]:
                res[i] = j
            
 
                
    return res
 
#=====================end-of-function==============
 
#=================investigation of konvertacii cost======
 
def devide4 (lst):
    
    res = []
    elem = []
    
    
    for i in range(len(lst)-3):
        elem1 = []
        elem = lst[i:4+i]
        # stoimoct konvertacii chetverki v BEEF
        s1 = B[elem[0]] + E[elem[1]] + E[elem[2]] +F[elem[3]]
        elem1.append(i)
        elem1.append(s1)
        res.append(elem1)
 
    return res    
#============end-of-finction=============================== 
 
res = 0
 
#===============sting algorithm subs chetverki============
def reduction_sting(list2, res):
    
    global cash
 
 
    if len(list2) < 4 or cash < 0:
        
        return res  
        
    else: 
    
        list3 = devide4(list2)
        print('==========================================')
        print (list3)
        print('==========================================')
        
        sred_stoim = 0
        
        for elem in list3:
            sred_stoim += elem[1]
            
            
        sred_stoim = sred_stoim//(len(list2)-3)    
        
        
        min = list3[0][1]
        i = 0
        min_ind = 0
        
        for elem in list3:
            if elem[1] < min:
                min = elem[1]
                min_ind = i
            i += 1
        
        print(min)
        
        if cash >=  min:
            
            cash -= min
            
            list2[min_ind] = 11
            list2[min_ind+1] = 14
            list2[min_ind+2] = 14
            list2[min_ind+3] = 15
            
            
        
        print('===========================================')
        print('Cash =', cash)
        print('===========================================')
        
        print('===========================================')
        print('list2 =',list2)
        print('===========================================')
        
        res += 1
        
        print('===========================================')
        print('res=', res)
        print('===========================================')
        
        list21 = list2[:min_ind]
        list22 = list2[min_ind+4:]
        
        
        print('===========================================')
        print('list21 =',list21)
        print('===========================================')
        print('list22 =',list22)
    
        if len(list21) < 4:
           
            if len(list22) < 4:
            
                return res
               
            else:
                return reduction_sting(list22, res)
           
        else:
            
            
            if len(list22) < 4 :
                
                return reduction_sting(list21, res)
                   
            else:
                return reduction_sting(list22, reduction_sting(list21, res))
        
        
        
#==================enf-of-function======================
 
#===========schedriy algorithm subs chetverki============
def reduction(list2, res, cash):
    
    
    for i in range(0,len(list3),4) :   
        cash -= list3[i][1]
        
        list2[i] = 11
        list2[i+1] = 14
        list2[i+2] = 14
        list2[i+3] = 15
        res += 1
        
    
    print('===========================================')
    print('Cash =', cash)
    print('===========================================')
    
    print('===========================================')
    print('list2 =',list2)
    print('===========================================')
    
    
    
    print('===========================================')
    print('res=', res)
    print('===========================================')
        
    return res     
#==================enf-of-function======================
 
#++++++++++++++++++++++++++BODY++++++++++++++++++++++++++
cash = random.randint(1, 100)
 
print('#####################BEGIN#####################=')
print('Cash =', cash)
print('===========================================')
 
K = random.randint(10, 100)
A = '0123456789ABCDEF'
stroka = ''
 
list1 = []
for i in A:
    list1.append(i)
 
for i in range(K):
    stroka += list1[random.randint(0, 15)]
 
print('='*50)  
 
print(stroka)# сгенерированная строка
print('='*50)
print('lenght stroki = ', len(stroka))
print('='*50)
 
list = []
for i in stroka:
    list.append(i)
    
print(list)
print('='*50)
 
list2 = subnumb(list)#
 
print('list2 =',list2)
print('**********************************************')
print('**********************************************')
 
list3 = devide4(list2)
print('==========================================')
print (list3)
print('==========================================')
 
sred_stoim = 0
 
for elem in list3:
    sred_stoim += elem[1]
    
    
sred_stoim = sred_stoim//(len(list2)-3) 
 
print('==========================================')
print('sred_stoim =', sred_stoim)
print('==========================================')
 
if cash/sred_stoim > len(list2)//4:
     print('RESULT=', reduction(list2, 0, cash))
else:
     print('RESULT=', reduction_sting(list2, 0))
 
print('%%%%%%%%%%%%%%%%%%%%%%%END%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%')

@Тюра · 10.11.2020, 23:30

Вот вам пример
"AABEEFAA" 1000
8 букв то есть макс 2 "BEEF"
16*8=128 1000>128 а значит ответ 2
а у вас ответ будет 1 т.к вы по очереди минимальные убираете

Добавлено через 4 минуты
Если честно то можно попробовать бин поиск по ответу с проверкой. В итоге получиться 16 операций т.к RESмакс=100000/4
+ проверка

Добавлено через 14 минут
А так лучше не спрашивать задачи во время олимпиады, можете спросить какую то часть кода описав что она должна делать, а не всю задачу

Добавлено через 1 час 4 минуты
там не 16*8 a 8 * 8 =64 1000>64

Добавлено через 2 часа 19 минут
Я тут подумал и понял что проверку вроде не получиться сделать(про бин поиск), но можно доработать ваше решение не уверен, что будет работать, но на последнем этапе рекурсии можно вместо случая где из 8 цифр только 1 beef получается сделать 2 beef и если подходит по ходам то увеличить результат)

@Gger · 11.11.2020, 13:17

можно код решения?

@goldolov_na · 11.11.2020, 13:22 **[ТС]**

Gger, 13 числа скину))

@Тюра · 14.11.2020, 00:09

Можно решение, просто очень интересно, олимпиада уже закончилась, желательно алгоритм или если лень писать то код по нему разберусь

@Тюра · 13.12.2020, 23:45

ну кидай

Новые блоги и статьи Все статьи Все блоги /
Модель ЗдрввоСохранения 7: больше работников, больше ресурсов. anaschu 08.04.2026 работников и заданий может быть сколько угодно, но настроено всё так, что используется пока что только 20%	Дальние перспективы сервера - слоя сети с космологическим дизайном интефейса карты и логики. Hrethgir 07.04.2026 Дальнейшее ближайшее планирование вывело к размышлениям над дальними перспективами. И вот тут может быть даже будут нужны оценки специалистов, так как в дальних перспективах всё может очень сильно. . .	Горе от ума kumehtar 07.04.2026 Эта мне ментальная установка, что вот прямо сейчас, мол, мне для полного счастья не хватает (нужное вписать), и когда я этого достигну - тогда и полный кайф. Одна из самых сильных ловушек на пути. . . .	Использование значений реквизитов справочника в документе, с определенными условиями и правами Maks 07.04.2026 1. Контроль срока действия договора Алгоритм из решения ниже реализован на примере нетипового документа "ЗаявкаНаРаботу", разработанного в конфигурации КА2. Задача: уведомлять пользователя, если. . .
Доступность команды формы по условию Maks 07.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "СписаниеМатериалов", разработанного в конфигурации КА2. Задача: сделать доступной кнопку (команда формы "ЗавершитьСписание") при. . .	Уведомление о неверно выбранном значении справочника Maks 06.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "НарядПутевка", разработанного в конфигурации КА2. Задача: уведомлять пользователя, если в документе выбран неверный склад. . .	Установка Qt Creator для C и C++: ставим среду, CMake и MinGW без фреймворка Qt 8Observer8 05.04.2026 Среду разработки Qt Creator можно установить без фреймворка Qt. Есть отдельный репозиторий для этой среды: https:/ / github. com/ qt-creator/ qt-creator, где можно скачать установщик, на вкладке Releases:. . .	AkelPad-скрипты, структуры, и немного лирики.. testuser2 05.04.2026 Такая программа, как AkelPad существует уже давно, и также давно существуют скрипты под нее. Тем не менее, прога живет, периодически что-то не спеша дополняется, улучшается. Что меня в первую очередь. . .

@goldolov_na 37 / 26 / 1 Регистрация: 31.03.2019 Сообщений: 585

	Робин Бобин Барабек 06.11.2020, 11:09. Показов 7756. Ответов 9 Метки python (Все метки) Робин Бобин Барабек думает, сколько коров и быка он съест на обед. Он берет шестнадцатеричное число. За одно действие он может заменить один из знаков на соседний (0 заменить на 1 или F, А заменить на 9 или В и т.п.). Он ставит себе ограничение сверху на количество действий и старается максимизировать количество подслов BEEF. Ваша программа в первой строке ввода получает последовательность цифр от 0 до 9 и букв от А до F. Всего не более 100000 знаков. Во второй строке написано ограничение на число ходов. Оно не превышает 1000. Программа должна напечатать максимальное число подслов BEEF, которое можно получить, не превышая максимального числа ходов. 0

@eaa Status 418 4584 / 2350 / 601 Регистрация: 26.11.2017 Сообщений: 5,262 Записей в блоге: 3
	06.11.2020, 11:35
	да вроде ничего сложного. "пробежаться" по строке один раз. что конкретно не получается? 0

@htmlprogrammist 0 / 0 / 0 Регистрация: 07.11.2020 Сообщений: 1
	07.11.2020, 20:31
	Олимпиадные задания нужно решать самостоятельно)) 0

@Тюра 8 / 8 / 0 Регистрация: 26.05.2019 Сообщений: 7
	10.11.2020, 23:30
	Вот вам пример "AABEEFAA" 1000 8 букв то есть макс 2 "BEEF" 168=128 1000>128 а значит ответ 2 а у вас ответ будет 1 т.к вы по очереди минимальные убираете Добавлено через 4 минуты* Если честно то можно попробовать бин поиск по ответу с проверкой. В итоге получиться 16 операций т.к RESмакс=100000/4 + проверка Добавлено через 14 минут А так лучше не спрашивать задачи во время олимпиады, можете спросить какую то часть кода описав что она должна делать, а не всю задачу Добавлено через 1 час 4 минуты там не 168 a 8 8 =64 1000>64 Добавлено через 2 часа 19 минут Я тут подумал и понял что проверку вроде не получиться сделать(про бин поиск), но можно доработать ваше решение не уверен, что будет работать, но на последнем этапе рекурсии можно вместо случая где из 8 цифр только 1 beef получается сделать 2 beef и если подходит по ходам то увеличить результат) 1

@Gger 0 / 0 / 0 Регистрация: 09.11.2020 Сообщений: 22
	11.11.2020, 13:17
	можно код решения? 0

@goldolov_na 37 / 26 / 1 Регистрация: 31.03.2019 Сообщений: 585
	11.11.2020, 13:22 [ТС]
	Gger, 13 числа скину)) 0

@Тюра 8 / 8 / 0 Регистрация: 26.05.2019 Сообщений: 7
	14.11.2020, 00:09
	Можно решение, просто очень интересно, олимпиада уже закончилась, желательно алгоритм или если лень писать то код по нему разберусь 0

@Тюра 8 / 8 / 0 Регистрация: 26.05.2019 Сообщений: 7
	13.12.2020, 23:45
	ну кидай 0

Робин Бобин Барабек

Решение