【二分】Shell Pyramid

【来源】：2008年哈尔滨区域赛

【题目链接】：

http://acm.hdu.edu.cn/showproblem.php?pid=2446

【题意】

题目是真的长呀，其实就问一个问题。

按照图里面的方法，请问第i个在第几堆，第几行，第几列。

例如，第19个在哪里呢？

在第4堆，第4行，第3列。

【题解】

利用二分快速找到第几堆，同样道理，找到第几行也一样。

这个题目关键在于公式推导。

前i堆有多少个 S（n）= Σ （ n+1）* n / 2 ）

没有公式插入真的很麻烦呀。。。

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<algorithm>
 4 
 5 typedef unsigned long long ll ;
 6 using namespace std;
 7 
 8 ll F( ll n ){
 9     ll x = n , y = n+1 , z = n+2 ;
10     if( x % 2 == 0 ){
11         x /= 2 ;
12     }else if( y % 2 == 0){
13         y /= 2 ;
14     }else{
15         z /= 2 ;
16     }
17 
18     if( x % 3 == 0 ){
19         x /= 3 ;
20     }else if( y % 3 == 0){
21         y /= 3 ;
22     }else{
23         z /= 3 ;
24     }
25 
26     return x * y * z ;
27 }
28 int main()
29 {
30     int T ;
31     for ( cin >> T ; T ; T -- ){
32         ll S, No , x , y ;
33         cin >> S;
34 
35         ll L = 0 , R = 3810776;
36         ll Mid , tmp ;
37         while ( L < R ){
38             Mid = (L + R ) >> 1 ;
39             tmp = F(Mid);
40             if( S <= tmp ){
41                 R = Mid ;
42             }else {
43                 L = Mid + 1  ;
44             }
45         }
46         //L;
47         tmp = F( L-1 ) ;
48         //cout << " L : " << L << " F(X) " << F(L) << endl;
49         S -= tmp ;
50         No = L;
51 
52         //cout << S << endl ;
53 
54         L = 1 , R = 3810776;
55         while( L < R ){
56             Mid = (L + R ) >> 1 ;
57             tmp = ( Mid * (Mid+1) ) / 2 ;
58             if( S <= tmp  ){
59                 R = Mid ;
60             }else {
61                 L = Mid + 1 ;
62             }
63         }
64         x = L ;
65         L -- ;
66         tmp = ( L * (L+1) ) / 2 ;
67         y =( S - tmp ) ? S-tmp : L ;
68         cout << No << " " << x << " " << y << endl ;
69     }
70     return 0;
71 }

View Code