Студентка Мария успешно завершила обучение в престижном вузе и теперь гуляет на выпускном. Студенты много мечтают о красивой жизни, поэтому одногруппники Маши решили соорудить небольшую пирамидку из одинаковых бокалов для шампанского. Получилась пирамида высоты n, такая что на самом верху стоял 1 бокал, на уровне ниже — 2 бокала, ещё ниже — 3 бокала и так далее. В последнем, самом нижнем уровне было ровно n бокалов.
Машин одногруппник Влад вызвался наполнять пирамиду шампанским. Он тысячу раз видел в кино, как эффектно распространяется по бокалам шампанское, перетекая с более высоких этажей на более низкие. Он взял бутылку и начал лить её содержимое в бокал, расположенный на верхнем уровне.
За одну секунду Влад выливает в верхний бокал количество шампанского, равное по объёму в точности одному бокалу. Если бокал полностью наполнен, а в него льётся шампанское, то все излишки поровну распределяются между двумя бокалами, на которых расположен данный. Если переполненный бокал стоит на нижнем уровне, то шампанское просто выливается на стол. В рамках данной задачи будем считать, что шампанское растекается по пирамиде мгновенно. Влада интересует, сколько бокалов будут наполнены до краёв через t секунд, когда бутылка подойдёт к концу.
На рисунках изображены пирамиды, состоящие из трёх уровней.
Примечание
В первом примере через 5 секунд будет наполнен верхний бокал, два бокала на втором сверху уровне, и средний бокал в нижнем уровне. Два крайних бокала в нижнем уровне будут заполнены наполовину.