Дистанционный практикум по программированию

Петя и Вася играют с набором из N камней. Вначале они взвесили все камни и записали вес каждого на листке бумаги. При этом оказалось, что все веса различны.

Через некоторое время Петя разложил все камни в ряд слева направо и сказал, что теперь камни лежат в порядке возрастания веса. Однако, Вася ему не поверил и попросил это доказать. По внешнему виду камней невозможно определить, какие из них тяжелее других.

У ребят имеются стрелочные весы с двумя чашами, которые показывают разницу веса груза на правой и на левой чаше. За какое наименьшее число взвешиваний Петя может доказать свою правоту?

Например, при N = 3 достаточно лишь одного взвешивания. Пусть, например, на листке записано, что камни имеют веса a, b и c, где a < b < c. Если камни действительно упорядочены по возрастанию, то самый левый должен иметь вес a, а самый правый — вес c. Чтобы доказать это, Петя кладёт первый камень на левую чашу, а третий камень — на правую. Весы покажут c - a. Поскольку никакой другой комбинацией такой вес получить невозможно, то первый камень действительно имеет вес a, а третий — вес c. Тогда оставшийся камень имеет вес b.

При N = 4 одного взвешивания уже не хватит, но можно показать, что вполне достаточно двух.

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