下面的圖形是著名的楊輝三角形：

如果我們按從上到下、從左到右的順序把所有數(shù)排成一列，可以得到如下數(shù)列：?1, 1, 1, 1, 2, 1, 1, 3, 3, 1, 1, 4, 6, 4,·······

給定一個(gè)正整數(shù)?N，請(qǐng)你輸出數(shù)列中第一次出現(xiàn)?N?是在第幾個(gè)數(shù)？

輸入描述

輸入一個(gè)整數(shù)?N。

輸出描述

輸出一個(gè)整數(shù)代表答案。

輸入輸出樣例

示例 1

輸入

6

輸出

13

---

上圖并不是我們喜歡的楊輝三角形式，讓我們?cè)龠M(jìn)行一步轉(zhuǎn)換：

第?0列第?1 列第?2 列第?3 列第?4 列第?5列

第?0 行	1
第?1 行	1	1
第?2 行	1	2	1
第?3 行	1	3	3	1
第?4行	1	4	6	4	1
第?5 行	1	5	10	10	5	1

我們知道楊輝三角的第?i行第?j列的值為?

用黃色印記標(biāo)記的數(shù)字為我們需要考慮的部分（圖一的左側(cè)部分），我們稱(chēng)其為有效部分。

那么不難發(fā)現(xiàn)，對(duì)于每一列（比如第?i列），它們的有效部分都是從?始的。

而顯然，對(duì)于同一行，列數(shù)越大則對(duì)應(yīng)的數(shù)值也越大；對(duì)于同一列來(lái)說(shuō)行數(shù)越大則數(shù)值也越大。也就是說(shuō)如果某一行的某一列的值為?X，那么在列數(shù)不變的情況下，無(wú)論行數(shù)怎么變大都不會(huì)再出現(xiàn)比?X小的數(shù)了；同理在行數(shù)不變的情況下列數(shù)怎么變大也不會(huì)再出現(xiàn)比?X小的數(shù)了。

于是我們可得，當(dāng)時(shí)，有效列數(shù)為第?0～16?列 （因?yàn)榈?17列的有效部分是開(kāi)始的，所以該列無(wú)論如何都不可能出現(xiàn)?n了，其它的列就就更不可能了）。

import sys n=int(input()) def C(a,b):res=1i=aj=1while j<=b:res=int(res*i/j)i-=1j+=1return res #計(jì)算出C(32,16)=601080390,C(34,17)=2333606220 #用二分法從后往前搜索 for k in range(16, -1, -1):l = 2 * kr = max(n, l)res = int(-1)while l <= r:mid = l + r >> 1if C(mid, k) > n:r = mid - 1if C(mid,k)<n:l = mid + 1if C(mid,k)==n:res=midprint((res + 1) * res // 2 + k + 1)sys.exit()

總結(jié)

以上是生活随笔為你收集整理的蓝桥杯省赛 2021 杨辉三角形 python的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。