1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
|
\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 хода мы умеем уменьшать рассматриваемый массив в $\frac{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}
|
