Как выполнить Задание Геометрическая игра на планшете информатика 25.10.24?
Задание 5. Геометрическая игра на планшете
Маленький Андрей изучает геометрические фигуры при помощи игры на планшете. У него есть равнобедренные прямоугольные треугольники четырёх цветов и ориентаций: жёлтые, зелёные, красные и синие. Для каждой разновидности треугольников есть заданное количество экземпляров этих треугольников. Более точно, у Андрея есть a жёлтых, b зелёных, c красных и d синих треугольников. Известно, что a≥b≥c≥d. Все треугольники одинаковые по размеру, но у каждого есть своя ориентация, которую нельзя менять. Треугольники одного цвета имеют одну и ту же ориентацию.
Помимо этого, у мальчика есть n пустых ячеек, стороны которых совпадают с катетами треугольников. Игра происходит пошагово, на каждом шаге Андрей может взять очередной треугольник и переместить его параллельным сдвигом в одну из ячеек. При этом в одну ячейку можно поместить либо вместе жёлтый и красный треугольники, либо вместе зелёный и синий, либо один любой треугольник из имеющихся.
На каждом шаге можно переместить треугольник строго одного текущего цвета. Сначала это жёлтый, на следующем ходе зелёный, далее красный и затем синий. Далее снова жёлтый, зелёный, красный, синий и т.д по циклу. Если места для текущего цвета нет либо треугольники текущего цвета закончились, то этот цвет пропускается и ходит следующий по порядку цвет.
Допустим, в данном шаге есть треугольник текущего цвета. Если ещё есть пустая ячейка, данный треугольник обязательно помещается в эту ячейку. Если пустые ячейки закончились, но есть полупустая ячейка с парным текущему цветом, то треугольник помещается в неё. Игра длится до тех пор, пока есть цвет, который можно поместить в какую‑то ячейку.
Определите, сколько каких треугольников Андрей распределит в конечном итоге по ячейкам.
Формат входных данных
На вход подаются четыре числа a, b, c, d, каждое в своей строке. Гарантируется, что a≥b≥c≥da≥b≥c≥d. В пятой строке содержится число n количество пустых ячеек. 1≤a, b, c, d≤1018, 1≤n≤1018.
Обратите внимание, что значения переменных в этой задаче могут превышать возможные значения 32-битной целочисленной переменной, поэтому необходимо использовать 6464-битные целочисленные типы данных (тип int64 в языке Pascal, тип long long в C++, long в Java и C#).
Формат выходных данных
Выведите ответ в четыре строки: для каждого соответствующего цвета укажите, сколько треугольников этого цвета получится поместить в ячейки. В первую строку выведите число жёлтых треугольников, во вторую зелёных, в третью красных и в четвёртую синих.
Система оценки
Решения, верно работающие при 1≤a, b, c, d, n≤1000, будут оцениваться в 30 баллов.
Решения, верно работающие при 4≤a+b+c+d≤106 и 1≤n≤106, будут оцениваться в 60 баллов.
Ввод
20
5
3
2
14
Вывод
8
5
3
2
Ввод
7
7
7
7
9
Вывод
5
4
5
4
Ответы (2)
Исходные и размещённые количества треугольников каждого цвета помещаем в списки bg и fn
pair список пар для цветов.
цветам соответствуют индексы
- 0 жёлтый
- 1 зелёный
- 2 красный
- 3 синий
Код программы на языке Python.
def next_color(c):
c+=1
if c>3:
c=0
return c
bg,fn=[0]*4,[0]*4
done=[1]*4
pair=[2,3,0,1]
bg=[int(input()) for _ in range(4)]
n=int(input())
cells=[[]]*n
col=0
while sum(done)>0:
t=0
while bg[col] ==0 and t<3:
done[col]=0
col=next_color(col)
t+=1
op=False
for i_cell in range(len(cells)):
if len(cells[i_cell])==2 or col in cells[i_cell]:
continue
if pair[col] in cells[i_cell] or len(cells[i_cell])==0:
fn[col]+=1
bg[col]-=1
a=cells[i_cell].copy()
a.append(col)
cells[i_cell]=a
op=True
break
if not op:
done[col]=0
col=next_color(col)
print(*fn,sep="\n")
Программа размещает треугольники лучше чем в тестовом примере 1
Результат
9
5
3
2
Распределение цветов по ячейкам:
- [0, 2]
- [1, 3]
- [0, 2]
- [1, 3]
- [0, 2]
- [1]
- [0]
- [1]
- [0]
- [1]
- [0]
- [0]
- [0]
- [0]
Результат примера 2 совпадает с тестовым
Попробовать работу кода в онлайн Python
У мальчика Андрея на планшете есть разноцветные треугольники. Жёлтых треугольников у него а штук, зелёных - b штук, красных - c штук и синих d штук. Больше всего у Андрея жёлтых треугольников, меньше всего синих. Нужно определить сколько треугольников и какого цвета Андрей распределит по ячейкам. Помочь в этом должен следующий программный код, написанный на С++:
ВКонтакте