← 返回题目列表

Codeforces · 471/C

C. MUH 和纸牌屋

中文机器翻译题面 查看原题

圣彼得堡动物园的北极熊 Menshykov 和 Uslada 以及基辅动物园的大象 Horace 决定建造一座纸牌屋。为此,他们已经找到了一大堆有 n 张扑克牌。让我们来描述一下他们想要建造的房子:

1. 房屋由一些非零层数组成。
2. 每层楼由非零数量的房间和天花板组成。房间是两张相互倾斜的卡片。房间排成一排,每两个相邻的房间共用另一张卡片制成的天花板。
3. 除最低一层外,每层的房间数应少于下面一层的房间数。

请注意,房屋的末端可能有多个房间,在这种情况下,它们也必须被天花板覆盖。另外,相邻楼层的房间数量不必相差一间,差异可能会更多。

当熊们练习放牌时,霍勒斯试图算出他们的房子应该有多少层。房子的高度是指房子的层数。你有可能用n张卡片搭建出很多不同高度的不同房子。大象似乎无法解决这个问题,他要求你用 n 张卡片来数出他们可以建造的不同高度的房子的数量。

输入

单行包含整数 n (1 ≤ n ≤ 1012) — 卡的数量。

输出

打印由 n 张卡片组成的房屋可以具有的不同高度的数量。

示例

输入 #1

13

输出 #1

1

输入 #2

6

输出 #2

0

注意

在第一个示例中,您只能建造这两座房屋(记住,您必须使用所有卡片):

因此,13张卡只够两层楼的房子使用,所以答案是1。

第二个样本中的六张卡不足以建造任何房屋。