2610 问题 K: 蓝桥杯2021年第十二届省赛真题-杨辉三角形

 时间限制: 1s 内存限制: 128MB

题目描述

下面的图形是著名的杨辉三角形：

蓝桥杯2021年第十二届省赛真题-杨辉三角形

如果我们按从上到下、从左到右的顺序把所有数排成一列，可以得到如下
数列：
1, 1, 1, 1, 2, 1, 1, 3, 3, 1, 1, 4, 6, 4, 1, ...
给定一个正整数 N，请你输出数列中第一次出现 N 是在第几个数？

输入格式

输入一个整数 N。

输出格式

输出一个整数代表答案。

样例输入

6

样例输出

13

提示

【评测用例规模与约定】
对于 20% 的评测用例，1 ≤ N ≤ 10；
对于所有评测用例，1 ≤ N ≤ 1000000000。

                    
                    
                    

                        

                            
                            

                                                                    
                                    
                                                                
                                
                                
                                
                            

                        

                        

                            
                        

                    

                
 
                                
    
            
                             
        

            

        

        

            

                
比赛公告

            

            

                

                    
1........................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................
                

            

        

        

            

                
比赛状况