%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 Задача D2. ДВОЙКИ}

\bigskip


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

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

\bigskip

{\bf Бавно решение с изчерпващо търсене} -- файл {\tt pair\_31p.cpp}

\bigskip

Програмата прочита числата от дадената редица в масива {\tt a[]}.
След това се извършва изчерпващо търсене, където резултатът се
пресмята в променливата {\tt c}:
\begin{verbatim}
     long long int c=0;
     for(int i=0;i<n;i++)
     for(int j=i+1;j<n;j++)
       if(a[i]+a[j]==s) c++;
\end{verbatim} 

\bigskip

{\bf По-добро решение с изчерпващо търсене} -- файл {\tt pair\_38p.cpp}

\bigskip

Използваме, че в дадената редица няма повтарящите се числа.
Затова, след намиране във вътрешния цикъл на двойка елементи,
чиято сума е равна на {\tt s}, излизаме от този цикъл,
понеже не е възможно за друга стойност на индекса {\tt j}
да има двойка елементи със същата сума:
\begin{verbatim}
     long long int c=0;
     for(int i=0;i<n;i++)
     for(int j=i+1;j<n;j++)
       if(a[i]+a[j]==s) {c++; break;}
\end{verbatim} 

\bigskip

{\bf По-бързо решение с двоен цикъл} -- файл {\tt pair\_69p.cpp}

\bigskip

Сортираме масива в растящ ред. Тогава при намиране 
във вътрешния цикъл на двойка елементи,
чиято сума е по-голяма от {\tt s}, излизаме от този цикъл,
понеже за всички следващи стойности на {\tt j}
тази сума ще става още по-голяма и не е възможно да стане
равна на {\tt s}:
\begin{verbatim}
    sort(a,a+n);
    long long int c=0;
    for(int i=0;i<n;i++)
    for(int j=i+1;j<n;j++)
    {
      if(a[i]+a[j]==s) c++;
      else if(a[i]+a[j]>s) break;
    }
\end{verbatim} 

\bigskip

{\bf Бързо решение с единичен цикъл} -- файл {\tt pair\_alt.cpp} за 100 т.

\bigskip

Използва се методът на двете показалки. След сортиране на елементите
от дадената редица, полагане {\tt int L=0} за лява показалка, която
в началото сочи към индекс 0 на масива {\tt a[]} и {\tt int R=n-1} за дясна показалка,
която в началото сочи към последния елемент на масива {\tt a[]}, който има
индекс {\tt n-1}. При работата на цикъла {\tt while(L<R)} показалката {\tt L}
се движи надясно, а показалката {\tt R} -- наляво и това продължава
докато {\tt L<R}:
\begin{verbatim}
     while (L < R)
      {
        if (a[L] + a[R] < s) L++;
        else if (a[L] + a[R] > s) R--;
        else {res++; L++; R--;}
      }
\end{verbatim}
Показалката {\tt L} сочи към по-малките числа от масива, а показалката {\tt R} --
към по-големите. Постепенно {\tt L} започва да сочи към все по-големи числа,
а {\tt R} -- към все по-малки. При стъките на цикъла, когато сумата {\tt a[L]+a[R]}
е по-малка от {\tt s}, увеличаваме {\tt L}, а когато тази сума е по-голяма от {\tt s} --
намаляваме {\tt R}. Когато се получи, че сумата е равна на {\tt s}, увеличава
брояча {\tt res} и след излизане от цикъла, програмата отпечатва стойността 
на този брояч.


\bigskip

{\bf Най-бързо решение с единичен цикъл} -- файл {\tt pair.cpp} за 100 т.

\bigskip

Използваме спомагателен масив {\tt b[k]}, в който маркираме с единица
елементите му за тези негови индекси {\tt k>0} за които {\tt k=s-а[i]} за
някой индекс {\tt i}:
\begin{verbatim}
    for(int i=0;i<n;i++)
     if(s-a[i]>0) b[s-a[i]]=1;
\end{verbatim}
Така, ако за някой елемент на редицата {\tt a[j]} имаме, че
{\tt b[a[j]]==1}, това означава че за друг елемент от редицата {\tt a[i]}
е вярно, че {\tt a[j]==s-a[i]} и за този друг елемент също е вярно, че
{\tt a[i]==s-a[j]}, т.е. намерили сме два елемента от редицата
(а именно {\tt a[j]} и {\tt a[i]==s-a[j]}),
за които {\tt a[i]+a[j]==s}. Програмата преброява всички такива случаи
чрез: 
\begin{verbatim}
    long long int c=0;
    for(int j=0;j<n;j++)
     if(b[a[j]]==1)
     if(s-a[j]<a[j]) c++;
\end{verbatim} 
Броячът {\tt c} се увеличава само когато {\tt s-a[j]<a[j]}, т.е. когато
{\tt a[i]<a[j]}, за да се избегне двойното броене (да не се броят два пъти
двойките ({\tt a[i]}, {\tt a[j]}) и ({\tt a[j]}, {\tt a[i]}), и да не се брои случаят, когато {\tt a[i]==a[j]}. 

\bigskip

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