На складе хранятся кубические контейнеры двух цветов различного размера. Чтобы сократить занимаемое при хранении место, контейнеры вкладывают друг в друга. Чтобы вложенные контейнеры было лучше видно, их цвета при вложении обязательно должны чередоваться, то есть нельзя вкладывать контейнер в контейнер такого же цвета. Один контейнер можно вложить в другой, если размер стороны внешнего контейнера превышает размер стороны внутреннего
Зная размеры и цвета всех контейнеров, определите максимально возможное количество контейнеров в одном блоке и минимальное количество ячеек для хранения всех контейнеров.
Входные данные.
Каждая строка входного файла содержит натуральное число и
Число обозначает размер контейнера в условных единицах, буква — цвет этого контейнера
В ответе запишите два целых числа: сначала максимально возможное количество контейнеров в одном блоке, затем минимальное количество ячеек для хранения всех контейнеров.
Ответ:
Приведем решение на языке Python.
from sys import setrecursionlimit
setrecursionlimit(5000)
f = [[int(t[0]), t[1]] for i in open('26.txt').readlines() if (t:=i.split())]
spiblock = []
def creat_block(li, nvk, pb, f=''):
lila = len(li); global spiblock
for i, a in enumerate(li):
if a[1] == f and pb - a[0] >= 5:
del li[i]; nvk += 1; pd = a[0]; break
if lila != len(li):
creat_block(li, nvk, pd, ('A' if f == 'B' else 'B'))
else:
spiblock += [[li, nvk]]; return 0
vk, m = 0, 0
while f:
u = [i[1] for i in f]
if 'A' in u and 'B' in u:
f = sorted(f)[::-1]; M = f[0]; f = f[1:]
creat_block(f, 1, M[0], ('A' if M[1] == 'B' else 'B'))
t = spiblock[-1]
f, vk, m = t[0], max(vk, t[1]), m + 1
else:
m += len(f); f.clear()
print(vk, m)
Ответ: 2326 187.
Приведем решение Михаила Зорина на языке Python.
n = 10000
data = []
for s in open('26.txt', 'r').readlines():
size, color = s.strip().split()
data.append([int(size), 1 if color == 'A' else 2])
data.sort()
used = [False] * n
cnt = 0
max_in_one = 0
for i in range(n):
if used[i]:
continue
cnt += 1
size, color = data[i]
used[i] = True
pile_size = 1
for j in range(i + 1, n):
if not used[j] and size + 5 <= data[j][0] and 3 - color == data[j][1]:
used[j] = True
pile_size += 1
color = 3 - color
size = data[j][0]
max_in_one = max(max_in_one, pile_size)
print(max_in_one, cnt)
Приведем решение Сергея Морёнова на языке Python.
n = 10000
f = open('26.txt')
a=f.readlines()
boxes=[]
for s in a:
d,type=s.split()
boxes.append([int(d),type])
boxes.sort()
count_block=0
maxdepth=0
while len(boxes)>0:
block=[boxes[0]]
boxes.remove(boxes[0])
i=0
while i < len(boxes):
box=boxes[i]
if box[0]-block[-1][0] >= 5 and box[1] != block[-1][1]:
block.append(box)
boxes.remove(box)
else:
i += 1
maxdepth=max(len(block),maxdepth)
count_block+=1
print(maxdepth,count_block)