% !TEX program = lualatex % (can also use "xelatex") 
\documentclass[12pt]{article}
\input{ejoi_structure.tex}

\usepackage[bulgarian]{babel}

\begin{document}

\renewcommand{\round}{Ден 1}
\renewcommand{\problemName}{Задача Майнкрафт}
\renewcommand{\lang}{Български}

\renewcommand{\tl}{$0.7$ sec.}
\renewcommand{\ml}{$256$ MB}
\problem{\problemName}

Знаем, че в момента НИКОЙ не е в двуседмична фаза на Майнкрафт. Освен Боби, който не знае как да бие Майнкрафт. Вие трябва да му помогнете. Нека малко да улесним работата Ви -- светът, в който се намира Боби, е едномерен -- има само една координата. 

Първата му задача е да намери $K$-те портала, които могат да го откарат в другия свят -- Ада. Вие трябва да имплементирате следната функция:
\begin{lstlisting}
 std::vector<int> portals(int N, int K);
\end{lstlisting}
Тази функция ще бъде извикана веднъж от Боби и има параметър $N$ -- максималната координата на едномерния свят и $K$ -- брой портали. Вие трябва да върнете координатите на всички портали. За комуникация с играта може да използвате следната функция:
\begin{lstlisting}
 int find_portals(int l, int r);
\end{lstlisting}
Като параметър функцията получава два координата и връща броя на портали с координати между $l$ и $r$, където $1 \leq l \leq r \leq N$.

Така Вие ще успеете да помогнете на Боби да влезне в другия свят на Майнкрафт -- Ада.

Следващата му цел ще бъде да намери Адска крепост. Но това не се оказва толкова лесна работа -- както знаете, Адът е място, където може да се умре много лесно, затова Боби търси Адската крепост, която ще има най-малка трудност за достигане. Освен това, по пътя Боби си прави почивки -- колкото по-дълго пътува, толкова е по-голям шансът да умре, затова той предпочита да спира на определени места -- нека ги наречем станции. По този начин можем да представим пътя на Боби до някоя крепост като свързан участък от станции, като той предварително знае трудността за достигането от една станция до друга. Има още една особеност -- всеки портал от намерените го откарва на същата координата, в която е бил и в нормалния свят. Нека отбележим, че порталите и крепостите се броят като станции. Освен това е гарантирано, че има как да се стигне през пътищата от всяка станция до всяка друга.

\newpage

Вие трябва да помогнете на Боби да намери координатите на Адската крепост и портала, между които се постига най-малка опасност, която Боби може да изпита. Под опасност разбираме сумата от всички трудности по пътя от някой портал до някоя крепост. За целта трябва да имплементирате следната функция:

\begin{lstlisting}
 std::pair<int, int> minimal_danger(int N, std::vector<std::pair<int, std::pair<int, int>>> paths, std::vector<int> portals, std::vector<int> fortresses);
\end{lstlisting}

Първият параметър на функцията е максималният номер на станция и е равна на стойността на $N$ при намирането на порталите за Ада. Вторият параметър на фунцията представлява възможните двойки станции, между които Боби може да пътува, и трудността на това ($w_i$). Той може да пътува в двете посоки по този път. За всеки елемент в \texttt{paths}, първата стойност е дължината на пътя, а другите са номерата на станциите, между които има път. Предпоследният параметър съдържа \textbf{правилните} координати на портали от преди Боби да влезе в Ада. Последният параметър съдържа координатите на Адските крепости. Функцията трябва да върне съответно координатата на портала, от който Боби започва пътя си, и координатата на Адската крепост, където Боби завършва пътя си.

Дотук всичко е наред. Единственото останало на Боби е да намери портала към Края. Какво обаче се обърква? След като Боби си набави нужните пламенни пръчки, за да си направи Очи на Края, той решава, че трябва да докосне малко трева и да спре с Майнкрафт за деня. 

На следващия ден влиза в сървъра и какво да види -- светът му е станал двумерен! Той се зарадвал много, но това усложнява Вашата задача. Вие трябва да намерите портала към Края, като имплементирате следната функция:

\begin{lstlisting}
 std::pair<int, int> find_end_portal(int L);
\end{lstlisting}
Параметърът $L$ е максималната координата в новия двумерен свят. Функцията трябва да върне координатите на портала към Края. За комуникация с играта можете да използвате следната функция:
\begin{lstlisting}
 std::string throw_eye(std::pair<int, int> coordinates);
\end{lstlisting}

\newpage

Тази функция може да върне един от тези отговори:

\begin{itemize}
	\item \texttt{NE}: порталът към Края се намира на североизток от координатите, на които е Боби.
	\item \texttt{N}: порталът към Края се намира на север от координатите, на които е Боби.
	\item \texttt{NW}: порталът към Края се намира на северозапад от координатите, на които е Боби.
	\item \texttt{E}: порталът към Края се намира на изток от координатите, на които е Боби.
	\item \texttt{NONE}: порталът към Края се намира на координатите, на които е Боби.
	\item \texttt{W}: порталът към Края се намира на запад от координатите, на които е Боби.
	\item \texttt{SE}: порталът към Края се намира на югоизток от координатите, на които е Боби.
	\item \texttt{S}: порталът към Края се намира на юг от координатите, на които е Боби.
	\item \texttt{SW}: порталът към Края се намира на югозапад от координатите, на които е Боби.
\end{itemize}

Имайте в предвид, че на юг координатите намалят, а на север се увеличават, както в координатна система. Всичко, наречено "координата" в задачата, започва от 1.

\subsection{Задача}
Трябва да имплементирате функциите \texttt{portals}, \texttt{minimal\_danger} и \texttt{find\_end\_portal}, които да използват възможно най-малко заявки (т.е. извиквания на помощни функции).

\subsection{Ограничения}
\begin{itemize}
\item $1 \leq N, F \leq 10^5$
\item $1 \leq M \leq 2.10^5$
\item $1 \leq L \leq 10^3$
\item $1 \leq K \leq 1000$
\item $1 \leq w_i \leq 10^9$
\item В част от тестовете има само една Адска крепост.
\item В друга част от тестовете $K \leq 5$.

\end{itemize}

\newpage

\subsection{Оценяване}
Да приемем, че разделяме задачата на три ''подзадачи'', като всяка от тях отговаря на една от трите от имплементираните от Вас функции. 
\begin{table}[H]
\begin{tblr}{|Q[c,m]|Q[c,m]|}
\hline
\textbf{Подзадача} & \textbf{Процент от точките на даден тест}\\
\hline
$1$ & $25$\\ 
\hline
$2$ & $50$\\
\hline
$3$ & $25$\\
\hline
\end{tblr}
\end{table}
\FloatBarrier

За всеки тест се оценява всяка от трите подзадачи, след което точките на даден тест (между 0 и 1) се намират по следния начин: $P=0.25P_1+0.5P_2+0.25P_3$, където $P_1, P_2, P_3$ са точките на всяка подзадача, а те са между 0 и 1 и са описани по-долу.

\textbf{Подзадача 1. Функция \texttt{portals}}

Нека $Q_1$ е броят извиквания на \texttt{find\_portals} от решението, а $Q_{1,author}$ е броят извиквания на автора. Тогава:

\[
P_1=0.1+0.9\frac{\log N - \log Q_1}{\log N - \log (Q_{1,author})}.
\]

\textbf{Подзадача 2. Функция \texttt{minimal\_danger}}

Ако върнете правилен отговор, $P_2=1$, а в противен случай $P_2=0$. 

\textbf{Подзадача 3. Функция \texttt{find\_end\_portal}}

Нека $Q_3$ е броят извиквания на \texttt{throw\_eye} от решението, а $Q_{3,author}$ е броят извиквания на автора. Тогава:

\[
P_3=0.1+0.9(1-(\frac{Q_3-Q_{3,author}}{L^2-Q_{3,author}})^{0.1}).
\]

\subsection{Примерна комуникация}

\begin{table}[H]
\begin{tblr}{
  colspec = {|X[c,m]|X[c,m]|},
  hlines,
  vlines,
}
\textbf{Жури} & \textbf{Състезател} \\
\texttt{portals(100, 2)} & \\ 
 & \texttt{find\_portals(1, 10)} \\ 
\texttt{0} & \\ 
 & \texttt{find\_portals(42, 80)} \\ 
\texttt{1} & \\ 
 & \texttt{find\_portals(81, 100)} \\ 
\texttt{1} & \\ 
 & \textbf{Връща} \texttt{\{55, 90\}} \\ 
\texttt{minimal\_danger(100, \{\{15, \{55, 12\}\}, \{5, \{12, 77\}\}\}, \{55\}, \{77\})} & \\ 
 & \textbf{Връща} \texttt{\{55, 77\}} \\ 
\texttt{find\_end\_portal(50)} & \\ 
 & \texttt{throw\_eye(\{10, 10\})} \\ 
\texttt{NE} & \\ 
 & \texttt{throw\_eye(\{45, 20\})} \\ 
\texttt{W} & \\ 
 & \texttt{throw\_eye(\{30, 20\})} \\ 
\texttt{NONE} & \\ 
 & \textbf{Връща} \texttt{\{30, 20\}} \\
\end{tblr}
\end{table}
\FloatBarrier

\newpage

\subsection{Примерен грейдър}
Предоставен Ви е примерен грейдър \texttt{Lgrader.cpp}.

Форматът на входа е следния: 
\begin{itemize}
\item На първия ред се въвеждат числата $N, K$ -- максимална координата в едномерния свят на Боби и броя на портали в него.
\item На втория ред се въвеждат $K$ числа -- координатата на всеки от порталите.
\item На следващия ред се въвежда $M$ -- брой двойки станции, между които Боби може да пътува.
\item На следващите $M$ реда се въвеждат по три числа -- координатите на двойката станции и опасността на пътя между тях.
\item На следващия ред се въвежда число $F$ -- брой Адски крепости.
\item На следващия ред се въвеждат $F$ числа -- координатите на Адските крепости.
\item На следващия ред се въвежда число $L$ -- максимална координата в двумерния свят на Боби.
\item На следващия ред се въвеждат две числа -- координатите на портала към Края в новия свят на Боби.
\end{itemize}
Форматът на изхода е следния: 
\begin{itemize}
\item На първия ред се извежда дали отговорът на решението Ви е правилен, след което броя използвани заявки.
\end{itemize}

\newpage

Това е цялата задача, но авторите прецениха, че условието не е достатъчно дълго. Тъй като те се притесняват, че може да Ви е прекалено скучно по време на състезанието, а освен това не успяха да измислят нещо по-добро, което да сложат в това условие, по-долу ще можете да се насладите на избрани откъси от скорошните новини.

\subsection{EK: TikTok не защитава достатъчно децата онлайн}

Европейската комисия съобщи, че днес е изпратила предварителна оценка до социалната платформа "ТикТок" (TikTok), в която се отчита неспазване на европейските правила за защитата на непълнолетните потребители онлайн.

Комисията уточнява, че платформата дава възможност на непълнолетните да създадат открит профил, видим дори за онези, които нямат акаунт в TikTok. Това може да доведе до нежелани контакти и съдържанието може да бъде използвано за кибертормоз, се допълва в съобщението. Тази функция дава на непознати поглед към живота на детето и може да доведе до по-нататъшни последици, защото съдържанието "може да остане онлайн завинаги", според ЕК.

Допълва се, че дори т. нар. частни акаунти може лесно да бъдат намерени чрез списъците за "последователи" на други потребители, а качените там снимки остават достъпни за всеки, включително онези без акаунт в платформата. Настройките са ключови за безопасността на непълнолетните онлайн, защото определят кой може да вижда тяхното съдържание и кой може да се свързва с тях. Съгласно европейското законодателство платформите, достъпни за непълнолетни, трябва да осигуряват висока защита за поверителност, безопасност и сигурност, отбелязва комисията, предаде БТА.

ЕК очаква от платформата да промени настройките за непълнолетните, така че тяхното съдържание да е по подразбиране видимо само за потребители на TikTok, одобрени от непълнолетния потребител. Според комисията съдържанието на непълнолетни потребители не трябва да бъде достъпно за аудитория извън платформата.

Предвижда се ЕК да продължи разговорите с платформата, а след това е възможно да издаде решение за несъответствие и да наложи глоба, определена от естеството, тежестта, честотата и продължителността на нарушението. Глобата няма да превишава 6 на сто от годишния оборот на дружеството в световен мащаб, се уточнява в съобщението.

\subsection{Проверяват опасно разминаване между пътнически самолет и хеликоптера на Тръмп}

Федералната авиационна администрация на САЩ прави проверка във връзка с нарушение на процедурите за безопасност при полети, при което пътнически самолет е получил разрешение за излитане, докато хеликоптерът на президента Доналд Тръмп се е приближавал към националното летище „Рейгън“ във Вашингтон, предаде Асошиейтед прес.

Инцидентът е станал във вторник. Президентският хеликоптер „Марин Уан“ e излетял от площадка в Белия дом, за да извърши полет към военновъздушната база „Андрюс“. Тръмп е бил на борда на хеликоптера, чиито полет бил първият етап от пътуването му до западното крайбрежие на САЩ. По същото време от летище „Рейгън“ е излетял и пътнически самолет.

На 29 януари 2025 г. при сблъсък между пътнически самолет и военен хеликоптер „Блек Хок“ загинаха 67 души. Катастрофата стана причина Федералната авиационна администрация да разпореди всички излитания и кацания на летище „Рейгън“ да бъдат преустановявани всеки път, когато покрай летището прелита хеликоптер, пише БТА.

Излетелият във вторник пътнически самолет е набрал височина над президентския хеликоптер, така че двата летателни апарата са се движели по траектории, по които не е имало опасност от сблъсък.

Федералната авиационна администрация публикува изявление, в което се посочва, че е имало „моментна загуба на дистанция, след което въздухоплавателните средства са продължили да се отдалечават едно от друго“.

„Диспечерът на въздушното движение е поддържал връзка както с пилота на пътническия самолет, така и с пилота на „Марин Уан“, се добавя в изявлението.

Белият дом подчерта, че президентът Тръмп през цялото време е бил в безопасност. „Марин Уан“ се управлява от едни от най-добрите пилоти в света и в нито един момент президентът не е бил изложен на риск“, заяви говорител на Белия дом.

Националната комисия за безопасност на транспорта тази сутрин съобщи, че продължава да събира информация за вчерашния инцидент и че все още не е взела решение дали да започне разследване.

\subsection{Нови руски атаки срещу Киев и Славянск: Петима загинаха, има ранени}

Нова руска атака по Украйна – взривове са чути в Киев, където беше задействана противовъздушната отбрана, а при удар по град Славянск в Донецка област са загинали най-малко петима души. Украинските власти съобщават за щети по жилищни сгради, търговски обекти и сградата на консулството на Латвия.

В Киев бяха задействани системите за противовъздушна отбрана, за да отблъснат руска атака, заяви днес кметът на украинската столица Виталий Кличко, предаде Ройтерс.

Според очевидци в града са се чули множество експлозии, докато хората са бягали към убежищата.

Военновъздушните сили на Украйна предупредиха за ракети, които са изстреляни към Киев, пише БТА.

Най-малко петима души загинаха, а девет са ранени при бомбардировка срещу град Славянск, в Донецка област, съобщи в Телеграм ръководителят на Донецката областна военна администрация Вадим Филашкин.

Две въздушни бомби нанесоха щети върху 10 къщи, един търговски обект и сградата на консулството на Латвия, уточни той.

Руска атака с дронове срещу пристанищната инфраструктура в Николаевска област нанесе щети на два търговски кораба, съобщи в Телеграм временно изпълняващият длъжността областен управител Георгий Решетилов.

Никой не е пострадал при атаката, добави той.

\newpage

\subsection{Полетите от и до летището на Лайпциг бяха спрени заради НЛО и подозрителен предмет}

Полетите от и до летището на Лайпциг, което обслужва и друг германски град - Хале, бяха спрени временно през изминалата нощ, след като в района беше забелязан неидентифициран летящ обект, а близо до една от пистите беше открит подозрителен предмет, предадоха ДПА и Ройтерс, позовавайки се на полицията.

Няколко самолета, един от които - изпълняващ редовен пътнически полет, са били пренасочени по време на този "инцидент в областта на сигурността".

Северната писта на летището отново бе отворена за полети тази сутрин.

Южната писта на летището, което служи като хъб за самолетите на логистичната компания Ди Ейч Ел (DHL), остана обаче затворена, докато специалисти проучват предмета с помощта на технологии за обезвреждане на взривни устройства.

Германските власти разследват и сигнали за неизвестен летящ обект, който е бил забелязан в района над летището, и установяват дали е възможно той да е свързан с инцидента.

Говорител на полицията заяви, че няма непосредствена опасност.

Германските летища са в състояние на повишена готовност след поредица от непозволени прелитания на безпилотни летателни апарати над обекти, включително военни съоръжения, енергийни терминали, морски пристанища и обекти, собственост на логистични компании.

Полицията в Германия предупреждава, че подобни прелитания на дронове може да са дело на руски агенти - твърдения, които Русия категорично отрича, отбелязва Ройтерс.

По-късно властите съобщиха, че на летището - ключов логистичен център за НАТО и за доставките на товари към Украйна, е открит дрон с взрвино устройство.

От полицията уточниха, че сапьорски екип е използвал робот за обезвреждане.

\newpage

\subsection{Русия съобщи, че е ударила три товарни кораба в Черно море}

Русия и Украйна засилиха взаимните си атаки срещу корабоплаването, което доведе до покачване на световните цени на пшеницата и заплашва да превърне Черно море в поредната стратегическа търговска зона.

Руските сили са ударили в сряда още три товарни кораба в Черно море, съобщи руското Министерство на отбраната, цитирано от Ройтерс.

Министерството публикува видеозаписи от ударите, но не разкри повече подробности.

Русия и Украйна засилиха взаимните си атаки срещу корабоплаването, което доведе до покачване на световните цени на пшеницата и заплашва да превърне Черно море в поредната стратегическа търговска зона , след Ормузкия проток, която ще бъде блокирана в резултат на война.

Засилващите се атаки срещу кораби, пристанища и експортни терминали в Черно море започват да оказват влияние върху световните доставки на зърно и петрол, превръщайки региона в поредната ключова търговска зона, засегната от ескалиращ конфликт.

Черно море е един от най-важните транспортни маршрути за износ на зърнени култури, суров петрол и рафинирани петролни продукти. Водите му се споделят от Русия и Украйна, както и от България, Грузия, Румъния и Турция.

Русия – най-големият износител на пшеница в света, и Украйна – един от водещите износители на селскостопанска продукция, през последните седмици засилиха взаимните атаки срещу пристанищна инфраструктура, съоръжения за износ и търговски кораби в Черно море. Киев увеличи и ударите срещу танкери, свързвани с търговията с руски петрол.

Новата ескалация създава допълнителен натиск върху световните стокови пазари, които вече са изправени пред проблеми заради нарушения в други ключови морски маршрути в Близкия изток.

„Последиците вече се виждат на световните селскостопански пазари“, заяви представителят на ООН Кайоко Готох по време на заседание на Съвета за сигурност. По думите ѝ не трябва да бъде допускано разрастването на „опасна спирала на ескалация“.

Потоците на петрол през Ормузкия проток също са засегнати от напрежението между САЩ и Иран, а действията на подкрепяните от Техеран хути в Йемен увеличават рисковете за корабоплаването в Червено море.

Износът на зърно под натиск
Украинските власти съобщават за десетки атаки срещу кораби и пристанищни съоръжения през юли. По данни на Министерството на инфраструктурата на страната са регистрирани 35 нападения срещу кораби в пристанища, 22 атаки срещу плавателни съдове в морето и 67 удара по пристанищна инфраструктура.

За сравнение, през цялата 2025 г. са били атакувани 14 кораба. Според оценки на „Ройтерс“ Украйна е нанесла удари по десетки танкери, свързвани с износа на руски петрол.

Последиците вече се усещат в търговията. Руската корабна компания FESCO съобщи, че е спряла приемането на нови заявки за превози през Черно море, след като един от корабите ѝ беше повреден при атака с украински дрон.

Междувременно Русия засили ударите си срещу граждански кораби и пристанищна инфраструктура около Одеса – основен украински транспортен център, през който преминава над 90% от селскостопанския износ на страната.

И Москва, и Киев твърдят, че атаките им са насочени единствено към военни цели.

Селскостопанската продукция остава основен източник на приходи от износ за Украйна повече от четири години след началото на войната. Страната търси алтернативни маршрути, но според украинския министър на земеделието Тарас Висоцки те няма да достигнат пълния си капацитет до края на август и ще могат да поемат едва около половината от обемите, които обичайно се транспортират през черноморските пристанища.

Дейността в Азовско море, което е свързано с Черно море, също е ограничена от 10 юли, което засяга работата на руското зърнено пристанище Таман.

Износът от руските пристанища Новоросийск и Туапсе продължава, но с по-бавни темпове.

Петролният износ също е засегнат
Ударите срещу танкери през юли доведоха до повреди по няколко кораба и временно прекъсване на товарните операции в Новоросийск и терминала на Каспийския тръбопроводен консорциум (CPC) – ключов маршрут за износ на казахстански петрол.

„Системата CPC е критично важен експортен маршрут за Казахстан, през който преминава около 80\% от износа на суров петрол на страната. Всяко продължително прекъсване може да се превърне в сериозен проблем за регионалните доставки“, заявиха от корабния брокер BRS.

Международни компании за морска сигурност предупреждават, че корабите, които продължават да посещават черноморските пристанища, трябва да извършват допълнителни оценки на риска, а екипажите да спазват специални мерки за безопасност при атаки с дронове.

„Невинните цивилни моряци не могат да бъдат разглеждани като странични щети при постигането на военни цели. Това е опасен и неприемлив прецедент“, заяви Стивън Котън, генерален секретар на Международната федерация на транспортните работници.

Застраховките в Черно море поскъпват
Повишените рискове за сигурността вече увеличават разходите за превоз. Според пазарни оценки средната дневна цена за танкери, превозващи петрол в Черно море, е нараснала до над 300 000 долара на ден спрямо малко над 200 000 долара седмица по-рано.

Военните застраховки за кораби, посещаващи черноморски терминали, са се увеличили до около 2\% от стойността на плавателните съдове спрямо приблизително 1\% преди две седмици. Дори малки промени в тези ставки означават стотици хиляди долари допълнителни разходи за едно пътуване.

Според Нилс Расмусен, главен анализатор по корабоплаване в BIMCO, ако ограниченият обем на превозите в Черно море се запази, световният пазар на танкери за суров петрол може да отчете спад от около 3\% – в момент, когато секторът вече е под сериозен натиск.

\emph{Информацията е взета от bTV Новините.}


\end{document}
