Взвешивание гирек

[frankenstein]

Даны 2012 гирек разной массы. Они разбиты на две группы (по 1006 в каждой), внутри которых упорядочены по массе. Найти способ за 11 взвешиваний найти 1006 гирьку по массе среди всех.

[Shadow]

За $n$ взвешиваний можем найти среднюю по массе ($2^{n-1}$-ую) среди $2^n$ гирек, разбитые на две группы по $2^{n-1}$. Случай $n=1$ тривиален.
Случай $n=2$:
$a_1<a_2,b_1<b_2$ Взвешиваем первые и пусть $a_1<b_1$ Отпадают как варианты $a_1,b_2$ Остаются $a_2,b_1$ и задача сводится к предыдущей.

Или. Если в группах по $2^{k+1}$ гирек сравниваем $a_{2^k},b_{2^k}$. Ровно половина из каждой группы отпадают.

Значит за 11 взвешиваний можем найти среднюю по массе среди 2048 гирек в две группы по 1024.
В случае их меньше, но после первого взвешивания можем отбросить не половину из каждой группы, а менше.

[frankenstein]

Как я понял, хотя, давайте сначала изменим эту условную оболочку задачи.
Это ведь по сути задача нахождения 1006го элемента в массиве из 2012 элементов, который разбит
на две кучи, в которых элементы отсортированы в неубывающем порядке.

Допустим $a$ и есть этот массив
$[11]$
Тогда если:
$a[1006] < b[1]$ тогда $a[1006]$ и есть ответ.
иначе
Алгоритм:
$a_i = 1; a_j = 1006$
$b_i = 1; b_j = 1006$
Пока ($a[a_i] \ne b[b_i] $ и $a_i \ne a_j$ и $b_i \ne b_j$)
....$m_a = (a_i + a_j) / 2$
....$m_b = (a_b + a_b) / 2$
....Если $a[m_a] > b[m_b]$ то $b_j = m_b$
....Если $a[m_a] < b[m_b]$ то $a_i = m_a$

[Shadow]

frankenstein в сообщении #837894 писал(а):

....Если $a[m_a] > b[m_b]$ то $b_j = m_b$
....Если $a[m_a] < b[m_b]$ то $a_i = m_a$

Нет, при любом резултате нужно изменить (уменьшить вдвое) интервалы в обеих массивах. И хорошо, если еще с первого взвешивания поддерживаем в интервалах по $2^k$ элемента. Я буду использовать переменные Amin,Amax,Bmin,Bmax

Используется синтаксис FreeBasic

Если A[512]<B[512] То
 Amin=495
 Amax=1006
 Bmin=1
 Bmax=512
Иначе
 Amin=1
 Amax=512
 Bmin=495
 Bmax=1006
Все

Пока Amin<Amax
 Ak=(Amin+Amax)\2
 Bk=(Bmin+Bmax)\2
 Если A[Ak]<B[Bk] То
  Amin=Ak+1
  Bmax=Bk
 Иначе
  Amax=Ak
  Bmin=Bk+1
 Все
Все

Если А[Amin]<B[Bmin] То
 Вывод A[Amin]
Иначе
 Вывод B[Bmin]
Все
Конец