蓝桥--杨辉三角形

简介: 蓝桥--杨辉三角形

【题目描述】


下面的图形为著名的杨辉三角形

7e4c1263680547a8a2098dd318fc2cc8.png

如果我们按从上到下,从左到右的顺序把所有数排成一列,可以得到如下数列:


1 , 1 , 1 , 1 , 2 , 1 , 1 , 3 , 3 , 1 , 1 , 4 , 6 , 4 , 6 , 1...... 1,1,1,1,2,1,1,3,3,1,1,4,6,4,6,1......1,1,1,1,2,1,1,3,3,1,1,4,6,4,6,1......


给定一个正整数N,求出N第一次出现是在第几个数?

1 < = N < = 109


【输入】


数字n


【输出】


N第一次出现的位置(从1开始计算)


【样例输入】


6


【样例输出】

13


【参考代码】

#include<algorithm>
#include<iostream>
typedef long long ll;
using namespace std;
int N;
ll combine(int n, int m) {
    ll ans = 1;
    for (int i = 0; i < m; i++) {
        ans *= (n - i);
        ans /= (i + 1);
        if (ans > N) {
            return ans;
        }
    }
    return ans;
}
bool f(int k) {
    int l = 2 * k, r = max(N, l);
    while (l < r) {
        int mid = (l + r) >> 1;
        if (combine(mid, k) >= N) {
            r = mid;
        } else {
            l = mid + 1;
        }
    }
    if (combine(r, k) == N) {
        cout << 1ll * (r + 1) * r / 2 + k + 1 << endl;
        return true;
    } else {
        return false;
    }
}
int main() {
    cin >> N;
    if (N == 1) {
        cout << "1" << endl;
    } else {
        for (int i = 17; i > 0; i--) {
            if (f(i)) {
                break;
            }
        }
    }
    return 0;
}


相关文章
|
算法
leetcode:136. 只出现一次的数字(找单身狗)
leetcode:136. 只出现一次的数字(找单身狗)
61 0
|
7月前
|
人工智能 编解码 自然语言处理
Zonos:油管博主集体转粉!开源TTS神器Zonos爆火:克隆你的声音说5国语言,还能调喜怒哀乐
Zonos 是 ZyphraAI 推出的开源多语言 TTS 模型,支持语音克隆、情感控制和多种语言,适用于有声读物、虚拟助手等场景。
421 18
Zonos:油管博主集体转粉!开源TTS神器Zonos爆火:克隆你的声音说5国语言,还能调喜怒哀乐
|
11月前
|
负载均衡 算法 网络安全
阿里云WoSign SSL证书申请指南_沃通SSL技术文档
阿里云平台WoSign品牌SSL证书是由阿里云合作伙伴沃通CA提供,上线阿里云平台以来,成为阿里云平台热销的国产品牌证书产品,用户在阿里云平台https://www.aliyun.com/product/cas 可直接下单购买WoSign SSL证书,快捷部署到阿里云产品中。
2641 8
阿里云WoSign SSL证书申请指南_沃通SSL技术文档
|
Linux Windows
ubuntu20.04离线安装rabbitvcs
ubuntu20.04离线安装rabbitvcs
346 0
|
存储 人工智能 安全
[译][AI OpenAI-doc] 弃用
随着我们推出更安全、更功能强大的模型,我们定期淘汰旧模型。依赖OpenAI模型的软件可能需要偶尔更新以保持正常工作。受影响的客户将始终通过电子邮件和我们的文档以及博客文章(针对较大的更改)收到通知。本页面列出了所有API弃用情况,以及推荐的替代方案。
|
存储 算法 Linux
嵌入式C语言(十三)
嵌入式C语言(十三)
87 0
|
SQL 分布式计算 Java
如何在 hive udf 中访问配置数据-踩坑记录,方案汇总与对比-udf中可以写sql吗?
如何在 hive udf 中访问配置数据-踩坑记录,方案汇总与对比-udf中可以写sql吗?
|
设计模式 Java
Java设计模式【十四】:责任链模式
Java设计模式【十四】:责任链模式
108 0
|
存储 API Android开发
Android 天气APP(十一)未来七天的天气预报、逐小时预报、UI优化
Android 天气APP(十一)未来七天的天气预报、逐小时预报、UI优化
457 0
Android 天气APP(十一)未来七天的天气预报、逐小时预报、UI优化
|
存储 索引 Python
Python列表与元组学习笔记
Python列表与元组学习笔记