Срочно!!! помогите, пж, задание по олимпиаде сириус
Ограничение по времени: 1
секунда
Ограничение по памяти: 256
мегабайт
Путь Пети в школу пролегает через оживлённый перекресток. На этом перекрёстке есть светофоры для пешеходов и светофоры для автомобилей.
Пешеходы могут переходить дорогу только по пешеходным переходам.
Пронумеруем пешеходные переходы числами от 1
до 4
так, как показано на рисунке.
Углы перекрёстка будем обозначать комбинациями цифр 12
, 23
, 34
и 41
—
по номерам переходов, которыми можно воспользоваться, находясь на этом углу.
Для каждого перехода известно время RJ
, в течение которого пешеходам горит красный свет, и время GJ
, в течение которого пешеходам горит зелёный свет (J=1
, 2
, 3
, 4
). Также для каждого перехода известно время TJ
, за которое его может перейти Петя.
Петя будет переходить ту или иную дорогу только в том случае, если успеет полностью перейти её на зелёный свет.
Чтобы попасть в школу, Пете нужно перейти с угла 12
на угол Y
(Y≢12
). Известно, что в тот момент, когда Петя достиг угла 12
, на всех пешеходных светофорах включился красный свет.
Ваша задача —
определить, через какое минимальное время Петя сможет попасть на угол Y
.
Формат входных данных
В первой строке содержится число Y
(Y
∈
{23
, 34
, 41
}) —
обозначение угла, на который нужно попасть Пете.
Во второй строке содержатся три целых числа R1
, G1
, T1
, записанных через пробел.
В третьей строке содержатся три целых числа R2
, G2
, T2
, записанных через пробел.
В четвёртой строке содержатся три целых числа R3
, G3
, T3
, записанных через пробел.
В пятой строке содержатся три целых числа R4
, G4
, T4
, записанных через пробел.
Здесь RJ
—
время, в течение которого на переходе J
горит красный свет, GJ
—
время, в течение которого на переходе J
горит зелёный свет, TJ
—
время, в течение которого Петя может пересечь переход J
(J=1
, 2
, 3
, 4
). Все числа положительные и не превосходят 106
.
Формат выходных данных
Выведите целое число —
минимальное время, которое потребуется Пете, чтобы попасть с угла 12
на угол Y
.
Гарантируется, что Петя всегда может перейти на угол Y
C++
#include <bits/stdc++.h>
using namespace std;
#define ll long long
int inf = 10000000;
int times[4][3];
vector<vector<vector<int>>> route = {
{},
{{1}, {0, 3, 2}},
{{1, 2}, {0, 3}},
{{0}, {1, 2, 3}}
};
int calc_route(vector<int> v) {
int tm = 0;
for (auto ind : v) {
int r = times[ind][0], g = times[ind][1], w = times[ind][2];
if (w > g) return inf;
int tmp = tm % (r + g);
if (tmp < r) {
tm += r - tmp;
tmp = r;
}
if (w > r + g - tmp) tm += -tmp + r + g + r + w;
else tm += w;
}
return tm;
}
int main()
{
int ang; cin >> ang;
if (ang == 12) {
cout << "0\n";
return 0;
}
if (ang == 23) ang = 1;
if (ang == 34) ang = 2;
if (ang == 41) ang = 3;
for (int i = 0; i < 4; ++i) {
for (int j = 0; j < 3; ++j) {
cin >> times[i][j];
}
}
int ans = inf;
for (auto v : route[ang]) {
ans = min(ans, calc_route(v));
}
cout << ans << "\n";
}
inf = 10_000000
times = [[0] * 3 for _ in range(4)]
route = [
[],
[[1], [0, 3, 2]],
[[1, 2], [0, 3]],
[[0], [1, 2, 3]]
]
def calc_route(v):
tm = 0
for ind in v:
r, g, w = times[ind][0], times[ind][1], times[ind][2]
if w > g:
return inf
tmp = tm % (r + g)
if tmp < r:
tm += r - tmp
tmp = r
if w > r + g - tmp:
tm += -tmp + r + g + r + w
else:
tm += w
return tm
ang = int(input())
if ang == 12:
print('0')
exit()
if ang == 23:
ang = 1
if ang == 34:
ang = 2
if ang == 41:
ang = 3
for i in range(4):
times[i] = list(map(int, input().split()))
ans = inf
for v in route[ang]:
ans = min(ans, calc_route(v))
print(ans)
Ответы на Сириус курсы ищи в тг канале "Сириус курсы ответы"