©2020-2024 ioDraw All rights reserved
The following figure is the famous Yang Hui triangle ：
If we press from top to bottom , Arrange all the numbers in a row from left to right , You can get the following sequence ：
1, 1, 1, 1, 2, 1, 1, 3, 3, 1, 1, 4, 6, 4, 1, ...
Given a positive integer N, Please output the first time in the sequence N What number is it ?
Input format
Enter an integer N.
Output format
Output an integer representing the answer .
Data range
about 20% Evaluation cases for ,1≤N≤10;
For all profiling cases ,1≤N≤10^9.
sample input ：
6
sample output ：
13
Some properties of Yang Hui triangle ： Left right symmetry
, Therefore, as long as the number appearing on the right half of Yang Hui triangle will appear on the left half , And the position is symmetrical , So the answer must be on the left , In addition, for each oblique line and vertical line, it increases from top to bottom , It should be clear that all numbers will appear in Yang Hui triangle , such as x, There must be C(x,1) Corresponding to x, So don't worry about whether there is a solution , But we need to find a value of x The uppermost position of the needs to be enumerated from bottom to top , Because if x First appeared in (i,j) This position , Then the number in the upper left and upper right of this position will be higher than that in the upper right x Smaller , So we can enumerate oblique lines , Use dichotomy to enumerate the positions in each oblique line , Note that it is enumerated from bottom to top :
code ：
#include<cstdio> #include<iostream> #include<cstring> #include<vector>
#include<algorithm> #include<map> #include<cmath> #include<queue> using
namespace std; typedef long long ll; ll C(ll a,ll b)// Find combination number { ll ans=1; for(int
i=a,j=1;j<=b;i--,j++) ans*=i,ans/=j; return ans; } ll n; bool check(int
k)// Mei Judi k Oblique travel { ll l=2*k,r=max(l,n); while(l<r) { ll mid=l+r>>1; if(C(mid,k)>=n)
r=mid; else l=mid+1; } if(C(l,k)==n) {
printf("%lld",l*(l+1)/2+k+1);// Note that the number of combinations is from C(0,0) Started return true; } return false; }
int main() { cin>>n; for(int i=16;;i--)// Enumerate oblique rows if(check(i)) break; return 0; }
Technology