Путь Пети в школу пролегает через оживлённый перекресток. На этом перекрёстке есть светофоры для пешеходов и светофоры для автомобилей. Пешеходы могут переходить дорогу только по пешеходным переходам. Пронумеруем пешеходные переходы числами от 1 до 4 так, как показано на рисунке. Углы перекрёстка будем обозначать комбинациями цифр 12, 23, 34 и 41 — по номерам переходов, которыми можно воспользоваться, находясь на этом углу. Для каждого перехода известно время RJ, в течение которого пешеходам горит красный свет, и время GJ, в течение которого пешеходам горит зелёный свет (J = 1, 2, 3, 4). Также для каждого перехода известно время ТJ, за которое его может перейти Петя.
Петя будет переходить ту или иную дорогу только в том случае, если успеет полностью перейти её на зелёный свет.
Чтобы попасть в школу, Пете нужно перейти с угла 12 на угол Y (Y ≠ 12). Известно, что в тот момент, когда Петя достиг угла 12, на всех пешеходных светофорах включился красный свет.
Ваша задача — определить, через какое минимальное время Петя сможет попасть на угол Y.
1 Ответ
Чтобы узнать, через какое минимальное время Петя сможет попасть на угол Y, надо сделать такое решение:
C++:
#include <bits/stdc++.h>
using namespace std;
#define ll long long
int inf = 10’000’000;
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»;
}
Python:
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)