D4. фанатам стратегий 3 (7 )
данный шаг отличается от предыдущего формулировкой ограничений на входные данные. перед проверкой решения с формулировкой ограничений из этого шага, убедитесь, что это решение проходит и на предыдущем шаге.
к добавлено примечание!
вскоре стало понятно, что всё совсем не просто. нельзя взять и построить здание. их в этой игре ещё и открыть нужно.
новое здание типа
a
можно построить, только если на нашей базе функционирует хотя бы по одному новому зданию из списка необходимых зданий здания типа
a
.
сколько на самом деле нам придётся построить зданий (не считая электростанций)? какие они? в каком порядке их строить? ваша – найти ответы на эти вопросы.
примечание
гарантируется, что существует такая последовательность постройки зданий, что здания всех типов можно построить.
формат входных данных
в первой строке записаны три целых числа
n, m и t
(1≤m≤n≤5⋅10^4; 1≤t≤2)
– количество различных типов новых зданий в игре, количество новых зданий, которые нужно построить, и номер формата выходных данных.
в следующей строке записаны
m
названий типов зданий, разделённых пробелами – требуемые для обеспечения устойчивой обороны здания. гарантируется, что строка не содержит одинаковых типов зданий.
далее идёт
n
блоков по
2
строки следующего вида:
в первой строке – название типа здания.
во второй – длина списка необходимых зданий для здания данного типа и сам список необходимых зданий. гарантируется, что список не содержит одинаковых типов зданий.
сумма длин списков необходимых зданий не превышает
5⋅10^4.
название каждого типа здания состоит только из латинских букв и имеет длину не более десяти символов.
формат выходных данных
если
t=1
, то выведите одно число – минимальное количество зданий, которые нужно построить.
если
t=2
, то в первой строке выведите одно число – минимальное количество зданий, которое необходимо построить, а во второй –
k
названий зданий, которые нужно построить, в том порядке, в котором их нужно строить. если существует несколько подходящих последовательностей – выведите любую из них.
sample input 1:
13 5 2
refinery vehicle repair palace turret
constryard
0
windtrap
1 constryard
refinery
1 windtrap
outpost
1 windtrap
silo
2 refinery constryard
vehicle
3 refinery windtrap outpost
barracks
2 constryard outpost
wall
1 outpost
turret
1 outpost
starport
2 silo refinery
repair
1 vehicle
hitech
3 vehicle wall outpost
palace
1 starport
sample output 1:
10
constryard windtrap refinery outpost silo vehicle turret starport repair palace
# Python 3.X
'''
Программа просит ввести основание
и прилегающую высоту треугольника,
присваивает введённые значения
переменным a и h, вычисляет площадь
треугольника и печатает значения
a, h и площади треугольника.
Вычисление площади треугольника
оформлено в виде вс
функции.
'''
def trig_area(a, h):
a = 0.5 * a * h
if a.is_integer():
return int(a)
else:
return a
a = int(input('Введите основание: '))
h = int(input('Введите прилегающую высоту: '))
print('\nОснование: {}\nВысота: {}\nПлощадь: {}'.format(a, h, trig_area(a, h)))
uses GraphABC;
begin
var xc:=300;
var yc:=250;
var r:=150;
var dx:=Trunc(r*cos(Pi/3));
var dy:=Trunc(r*sin(Pi/3));
Polygon((xc+r,yc),(xc+dx,yc-dy),(xc-dx,yc-dy),(xc-r,yc),
(xc-dx,yc+dy),(xc+dx,yc+dy));
r:=r-10;
dx:=Trunc(r*cos(Pi/3));
dy:=Trunc(r*sin(Pi/3));
Pen.Color:=clRed;
Brush.Color:=Pen.Color;
Polygon((xc+r,yc),(xc+dx,yc-dy),(xc-dx,yc-dy),(xc-r,yc),
(xc-dx,yc+dy),(xc+dx,yc+dy));
Font.Color:=clWhite;
Font.Size:=50;
Font.Style:=fsBold;
SetCoordinateOrigin(xc-90,yc-40);
Write('STOP');
end.