Теорія струн

Одна з найпопулярніших і (на думку багатьох фізиків) багатообіцяючих теорій — це теорія струн. Вона стверджує, що мультивсесвіт складається з різних вимірів, причому найбільшим є $11$-й вимір. За межами $11$ вимірів Всесвіт стає нестабільним, а виміри, що перевищують $11$, схлопнуться в $11$-вимірний Всесвіт. Тепер перед вами стоїть завдання моделювання теоретичної проблеми струн.

У нашій системі є $n$ струн, пронумерованих від $1$ до $n$, які розташовані в рядках S = i для i = 1, \ldots, n на декартовій площині OTP, де OT представляє часові рамки, а OS представляє поточну струну частинки. Частинки рухаються тільки вперед у часі і можуть стрибати між струнами, витрачаючи енергію. Спочатку частинки можуть залишатися в стані спокою без втрати енергії, тобто перехід зі стану $(t,p)$ в (t + 1, p) коштує $0$ енергії, і жодних інших переходів у нашій системі (поки) не передбачено. Зверніть увагу, що наша система не підтримує подорожі назад у часі (або припускає, що вартість переходу назад у часі нескінченна). Ваше основне завдання — обчислити мінімальну кількість енергії, необхідну частинці для переміщення від струни s_1 у часовому інтервалі t_1 до струни s_2 у часовому інтервалі t_2, або визначити, що це неможливо.

Тепер ми опишемо певні зовнішні сили, які можуть з'явитися: телепорти і масивні об'єкти. Коли телепорт з'являється у часовому інтервалі $t$ з витратами енергії (a_1, \ldots, a_{n-1}), він дозволяє будь-якій частинці в стані $(t,i)$ негайно перейти в стан (t, i + 1) з втратою енергії a_i або в стан (t, i - 1) з втратою енергії a_{i-1} (якщо струна i + 1 або i - 1 існує). Якщо ми додамо масивний об'єкт у часовому інтервалі $t$ з енергіями (b_1, \ldots, b_n), це вплине на перехід між часом $t$ і t + 1, так що частинка в струні $i$ вимагає витрат енергії b_i, щоб залишатися в тій самій струні (інакше частинка просто зникне в просторі-часі). Отже, є $3$ типи запитів, які ви повинні виконати:

• 1 t a_1, \ldots, a_{n-1} - додати телепорт у момент часу $t$ з енергіями a_i;

• 2 t b_1, \ldots, b_n - додати масивний об'єкт у момент часу $t$ з енергіями b_i;

• 3 t_1 s_1 t_2 s_2 - ми маємо частинку, що подорожує між станами (t_1, s_1) \to (t_2, s_2), яку мінімальну кількість енергії слід витратити цій частинці?

Зверніть увагу, що якщо вам пропонується додати $2$ телепорти або масивні об'єкти в один і той самий період часу, то пізніший замінює раніший.