%LuaLaTeX
\documentclass[12pt]{article}
\usepackage{geometry}
\geometry{
	paper=a4paper,
	top=4cm, % Top margin
	bottom=2cm, % Bottom margin
	left=2cm, % Left margin
	right=2cm, % Right margin
	%headheight=3cm, % Header height
	%footskip=1.5cm, % Space from the bottom margin to the baseline of the footer
	%headsep=0.5cm, % Space from the top margin to the baseline of the header
	%showframe, % Uncomment to show how the type block is set on the page
}
\usepackage[T2A]{fontenc}
\usepackage[bulgarian]{babel}
\usepackage{fontspec}
\setmainfont{Times New Roman}
\setsansfont{Times New Roman}
\setmonofont{Courier New}
\usepackage[math-style=TeX]{unicode-math}
\setmathfont{Latin Modern Math}



\begin{document}

%\newcommand{\tl}{$0.1$ сек.}
%\newcommand{\ml}{$256$ MB}
{\bf Задача ТРОЙКИ}

\bigskip


%\begin{wrapfigure}{r}{0.25\textwidth}
%	\begin{adjustbox}{width=0.25\textwidth}
%		\includegraphics{image}
%	\end{adjustbox}
%\end{wrapfigure}

{\bf Пояснение към решенията}

\bigskip

{\bf Бавно решение} -- файл {\tt triplet\_18p.cpp}

\medskip

Програмата прочита във вектора {\tt s[]} елементите на дадената редица.
Вместо вектор би могло да се използва и масив.
След това елементите на редицата се сортират в растящ ред.
Намирането на питагорова тройка става чрез троен цикъл с индекси {\tt i}, {\tt j} и {\tt k}.
В тялото на тройния цикъл се проверява дали квадратите на числата 
{\tt a=s[i], b=s[j], c=s[k]} образуват питагорова тройка, т.е. дали
{\tt a*a+b*b==c*c}.
Първата така намерена тройка удовлетворява условието на задачата.


\bigskip

{\bf По-бързо решение} -- файл {\tt triplet\_68p.cpp}

\medskip

След прочитане на дадената редица в {\tt s[]}, заменяме всяка
стойност с нейния квадрат.
Сортираме елементите на {\tt s[]} и използваме цикъл
с индекс {\tt i}, с който обхождаме елементите, започвайки от {\tt i=2}.
При всяка стойност на {\tt i} обработваме отреза от {\tt s[]} с индекси от
{\tt L} до {\tt R}. 
В началото {\tt L=0} и {\tt R=i-1}. 

Когато {\tt s[L] + s[R] == s[i]},
това означава, че е намерена питагорова тройка и тогава в променливите
{\tt ar}, {\tt br} и {\tt cr} записваме квадратите на числата от питагоровата 
тройка, като се поддържа {\tt ar} да е най-малката намерена до момента стойност,
а когато има повече от една питагорова тройка с такава най-малка стойност,
в променливата {\tt br} се поддържа най-малката намерена стойност на {\tt b}. 

Когато {\tt s[L] + s[R]} не е равно на {\tt s[i]}, тогава при
{\tt s[L] + s[R] < s[i]} увеличаваме {\tt L} с единица, а в противен случай --
намаляваме {\tt R} с единица. Така се подържа, че {\tt  L<R} и {\tt R<i},
докато е възможно.

Накрая се отпечатва
\begin{verbatim}
    cout << sqrt(ar) << " " << sqrt(br) << " " << sqrt(cr) << endl;
\end{verbatim}
или, когато не е намерена питагорова тройка, {\tt cout << -1 << endl;}


{\bf Забележка.} С малка модификация може да не използваме математическата функция {\tt sqrt}.
След прочитане на дадената редица в {\tt u[]}, записваме за всяка нейна
стойност нейния квадрат в {\tt s[]}. Така вместо да отпечатваме 
\begin{verbatim}
    cout << sqrt(ar) << " " << sqrt(br) << " " << sqrt(cr) << endl;
\end{verbatim}
отпечатваме 
\begin{verbatim}
    cout << u[ai] << " " << u[bi] << " " << u[ci] << endl;
\end{verbatim}
което в направено във файла {\tt triplet\_68p\_alt.cpp}

\bigskip

\ 


\bigskip


{\bf Бързо решение} -- файл {\tt triplet\_100p.cpp}

\medskip

Означаваме с {\tt m} най-голямата стойност на елемент от дадената редица. 
Не използваме сортиране,
а масив (или вектор) {\tt vis[]}, в който отбелязваме {\tt vis[a]=true}, когато 
стойността {\tt a} се среща в дадената редица и  {\tt vis[a]=false}, когато не се среща.
В тялото на цикъла
\begin{verbatim}
   for(LL a = 1; a < m + 1; a++)
\end{verbatim}
ще изследваме, дали
всяко от числата {\tt a} в интервала от 1 до {\tt m} може да бъде първи елемент на 
питагорова тройка (съгласно ограниченията на задачата, може вместо {\tt m} да използваме
стойността 7~000). За целта във вътрешния цикъл {\tt for(LL b = a+1; b < m+1; b++)}
проверяваме дали {\tt a*a + b*b} е точен квадрат. Това става чрез математическата
функция {\tt sqrt}: {\tt c = sqrt(a*a + b*b)}. Проверяваме дали {\tt c*c==a*a+b*b}  и 
дали {\tt c} е елемент на дадената редица. Ако е така, стойностите {\tt a,b,c} 
са търсената питагорова тройка. 




\bigskip

\hfill{\it Емил Келеведжиев}






	
\end{document}