Задача №113531. Flat Squares
Мальчику Мише подарили на день рождения прямоугольник, разбитый на N строк и M столбцов. Миша еще только начинающий программист, поэтому он не стал рисовать лабиринты в прямоугольнике и искать в них кратчайшие пути. Миша решил нарисовать несколько квадратов в подаренном прямоугольнике, при этом Миша соблюдал следующие правила:
• квадраты должны состоять из клеток, то есть их границы должны проходить по линиям сетки исходного прямоугольника;
• квадраты не должны иметь общих точек, то есть они не могут пересекаться, касаться и иметь общую часть стороны (однако квадраты могут содержать границу исходного прямоугольника);
• каждый столбец может содержать клетки максимум одного квадрата (нельзя рисовать квад- раты один над другим);
• все квадраты должны иметь разные размеры.
Миша очень обрадовался, когда нарисовал много квадратов. Счастье его было столь велико, что он потерял подаренный ему прямоугольник. Более того, он даже забыл размеры прямоугольника N и M . Единственное, что помнит Миша о своем прямоугольнике — это количество клеток, из которых он состоял. По заданному количеству клеток прямоугольника определите, какое наибольшее количество квадратов мог нарисовать Миша.
В первой строке содержится одно число S — количество клеток прямоугольника Миши ( 1 ≤ S ≤ 10 9 ).
Выведите одно число — максимальное количество квадратов, которое мог нарисовать Миша в прямоугольнике заданного размера.
В первом примере прямоугольники площадью 7 могли быть только 1×7 и 7×1. В любом случае Миша мог вырезать максимум 1 квадрат (см. рисунок 1).
Во втором примере можно вырезать два квадрата, не нарушая правил. Для этого можно использовать прямоугольники 4 × 3, 3 × 4, 2 × 6 (рисунок 2 — a, b, c соответственно). Заметьте, что из других прямоугольников, состоящих из 12 клеток, вырезать 2 квадрата, не нарушая правил, не получится.
7
1
12
2