您当前位置：首页 > php开源 > C. MUH and House of Cards（Codeforces Round #269）

C. MUH and House of Cards（Codeforces Round #269）

来源：程序员人生发布时间：2014-10-06 08:00:01 阅读次数：2623次

Polar bears Menshykov and Uslada from the zoo of St. Petersburg and elephant Horace from the zoo of Kiev decided to build a house of cards. For that they've already found a hefty deck of n playing cards. Let's describe the house they want to make:

The house consists of some non-zero number of floors.
Each floor consists of a non-zero number of rooms and the ceiling. A room is two cards that are leaned towards each other. The rooms are made in a row, each two adjoining rooms share a ceiling made by another card.
Each floor besides for the lowest one should contain less rooms than the floor below.

Please note that the house may end by the floor with more than one room, and in this case they also must be covered by the ceiling. Also, the number of rooms on the adjoining floors doesn't have to differ by one, the difference may be more.

While bears are practicing to put cards, Horace tries to figure out how many floors their house should consist of. The height of the house is the number of floors in it. It is possible that you can make a lot of different houses of different heights out of n cards. It seems that the elephant cannot solve this problem and he asks you to count the number of the distinct heights of the houses that they can make usingexactly n cards.

Input

The single line contains integer n (1?≤?n?≤?1012) ― the number of cards.

Output

Print the number of distinct heights that the houses made of exactly n cards can have.

Sample test(s)

input
13

output
1

input
6

output
0

Note

In the first sample you can build only these two houses (remember, you must use all the cards):

$\text{[math]}$

Thus, 13 cards are enough only for two floor houses, so the answer is 1.

The six cards in the second sample are not enough to build any house.

很容易发现，每层的牌数为3t+2，先对x=n%3，当x=1时，最少有两个2，即最少有两层，当x=2时，最少有一层，x=3时最少有两层，刚好是x=3-x，现在假设有k层，最少为（3*0+2）+（3*1+2）+（3*2+2）+.......+（3*（k-1）+2<=n，整理得（k*（k+1)/2*3<=(n+k),然后再对层数加3，直到不满足上面的条件。

代码：

#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; int main() { long long n; scanf("%I64d",&n); long long x=n%3; x=3-x; long long cou=0; for(long long i=x;i*(i+1)/2*3<=(n+i);i=i+3) { cou++; } printf("%I64d ",cou); return 0; }

生活不易，码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠
程序员人生

------分隔线----------------------------

上一篇 关于Linux静态库和动态库的分析

下一篇 C++ Singleton

分享到:

------分隔线----------------------------

为码而活

积分：4237

15粉丝

7关注

栏目热点