Путь Пети в школу пролегает через оживлённый перекресток. На этом перекрёстке есть светофоры для пешеходов и светофоры для автомобилей. Пешеходы могут переходить дорогу только по пешеходным переходам. Пронумеруем пешеходные переходы числами от 1 до 4 так, как показано на рисунке. Углы перекрёстка будем обозначать комбинациями цифр 12, 23, 34 и 41 — по номерам переходов, которыми можно воспользоваться, находясь на этом углу.

Question

Вопрос. Полная версия

Путь Пети в школу пролегает через оживлённый перекресток. На этом перекрёстке есть светофоры для пешеходов и светофоры для автомобилей. Пешеходы могут переходить дорогу только по пешеходным переходам. Пронумеруем пешеходные переходы числами от 1 до 4 так, как показано на рисунке. Углы перекрёстка будем обозначать комбинациями цифр 12, 23, 34 и 41 — по номерам переходов, которыми можно воспользоваться, находясь на этом углу. Для каждого перехода известно время RJ, в течение которого пешеходам горит красный свет, и время GJ, в течение которого пешеходам горит зелёный свет (J = 1, 2, 3, 4). Также для каждого перехода известно время ТJ, за которое его может перейти Петя.

Петя будет переходить ту или иную дорогу только в том случае, если успеет полностью перейти её на зелёный свет.

Чтобы попасть в школу, Пете нужно перейти с угла 12 на угол Y (Y ≠ 12). Известно, что в тот момент, когда Петя достиг угла 12, на всех пешеходных светофорах включился красный свет.

Ваша задача — определить, через какое минимальное время Петя сможет попасть на угол Y.

Ответ

Answer 1

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)