Взвешивание
(Время: 1 сек. Память: 16 Мб Сложность: 28%)
Заметим, что за одно взвешивание возможно исключить примерно 2/3 рассматриваемых монет. Для этого следует разделить все монеты на 3 примерно равные части (так, чтобы разница между любыми двумя кучками не превышала 1). В результате такого деления всегда возможно выбрать 2 кучки с равным количеством монет, их и нужно разместить на весах. Если весы окажутся в равновесии, то это будет означать, что среди взвешиваемых монет нет фальшивой и она находится в 3й кучке. Если же какая то из взвешиваемых частей оказалась тяжелей, то в силу равного числа монет она и будет содержать фальшивую. Таким образом, если у нас n монет, то в худшем случае за одно взвешивание мы получим (n+2) div 3 монет.
Алгоритм имеет логарифмическую сложность, поэтому реализовать его можно простым математическим моделированием процесса взвешивания. Так же эту задачу возможно решить прямым вычислением значения логарифма от n по основанию 3 с округлением в большую сторону.
Алгоритмическая запись первого из рассмотренных решений будет выглядеть следующим образом:
read(n)
k=1
while(n>3){
k = k+1
n = (n+2) div 3
}
write(k)
| 
