Reorganize & alg-1

1 files changed, 0 insertions, 42 deletions

diff --git a/dm-19.tex b/dm-19.tex
deleted file mode 100644
index 12aa975..0000000
--- a/dm-19.tex
+++ /dev/null
@@ -1,42 +0,0 @@
-\documentclass[11pt]{article}
-\usepackage[x11names, svgnames, rgb]{xcolor}
-%\usepackage{tikz}
-%\usetikzlibrary{arrows,shapes}
-
-\usepackage{scrextend}
-
-\input{intro}
-
-\lhead{\color{gray} Шарафатдинов Камиль 192}
-\rhead{\color{gray} дм-19 (\texttt{cw19\_plus})}
-\title{Дискретная математика 19}
-\author{Шарафатдинов Камиль БПМИ192}
-\date{билд: \today}
-
-% -- Here bet  dragons --
-\begin{document}
-
-\maketitle
-
-\setlength{\columnsep}{1cm}
-\twocolumn
-\dmquestion{1}
-    Заметим, что мы всегда можем выбрать два числа так, что они делят весь массив
-    на три примерно равные части, то есть такие,
-    что каждые две отличаются не более чем на 1.
-    Пусть мы умеем, запросив значение в этих числах, понимать в какой части
-    (или в каких двух подряд идущих частях) лежит максимум.
-    Тогда за 2 хода мы умеем уменьшать рассматриваемый массив в $\dfrac{3}{2}$ раза, а значит, мы сведем задачу к поиску максимума на массиве из менее чем трех элементов, а значит, решим задачу за менее чем $4\log_3 n$ ходов.
-
-\dmquestion{2}
-
-    Разобьем монеты на $\lfloor n/2 \rfloor$ пар (одна останется)
-    и сравним веса монет в каждой паре.
-    Если нашлась пара, в которой монеты имеют разный вес, то фальшивая в этой паре та, которая легче. Если монеты в каждой паре одинаковы по весу, то фальшивая - та, что осталась. Пар $\lfloor n/2 \rfloor$, поэтому сравнений столько же.
-
-\dmquestion{3}
-
-    Пусть мы справились за меньше, чем $\lfloor n/2 \rfloor$ взвешиваний. Тогда в сравнении могли поучаствовать не более, чем  $n - 3$ монеты. Значит, есть хотя бы три монеты, про которые никакой информации нет. Значит, если фальшивая была среди них, то по итогу взвешивания каждая из них может оказаться ответом, а наверняка выбрать среди них фальшивую мы не можем. Значит, нужно хотя бы $\lfloor n/2 \rfloor$ хода.
-
-
-\end{document}