P8749 [蓝桥杯 2021 省 B] 杨辉三角形

[蓝桥杯 2021 省 B] 杨辉三角形

题目描述

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

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

1 , 1 , 1 , 1 , 2 , 1 , 1 , 3 , 3 , 1 , 1 , 4 , 6 , 4 , 1 , … 1,1,1,1,2,1,1,3,3,1,1,4,6,4,1, \ldots 1,1,1,1,2,1,1,3,3,1,1,4,6,4,1,

给定一个正整数 N N N,请你输出数列中第一次出现 N N N 是在第几个数。

输入格式

输入一个整数 N N N

输出格式

输出一个整数代表答案。

样例 #1

样例输入 #1

6

样例输出 #1

13

提示

对于 20 % 20 \% 20% 的评测用例, 1 ≤ N ≤ 10 1 \leq N \leq 10 1N10;

对于所有评测用例, 1 ≤ N ≤ 1 0 9 1 \leq N \leq 10^9 1N109

蓝桥杯 2021 第一轮省赛 B 组 H 题。

杨辉三角性质

在这里插入图片描述

#include <iostream>
#include <algorithm>
#include <cstring>
#define int long long

using namespace std;

int n;

int C(int a, int b){
    int res = 1;
    for (int i = a, j = 1; j <= b; i --, j ++){
        res = res * i / j;
        if (res > n) return res;
    }
    return res;
}

bool check(int k){
    int l = 2 * k, r = n;
    if (l > r) return false;
    while (l < r){
        int mid = l + r >> 1;
        if (C(mid, k) >= n) r = mid;
        else l = mid + 1;
    }
    if (C(r, k) != n) return false;
    printf("%lld\n", r * (r + 1ll) / 2 + k + 1ll);
    return true;
}

signed main()
{
    scanf("%lld", &n);
    
    for (int i = 16; ; i --){
        if (check(i)) {
            break;
        }
    }
    return 0;
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/520474.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

背包问题---

一、背包模型 有一个体积为V的背包,商店有n个物品,每个物品有一个价值v和体积w,每个物品只能被拿一次,问能够装下物品的最大价值。 这里每一种物品只有两种状态即"拿"或"不拿". 设状态dp[i][j]表示到第i个物品为止,拿的物品总体积为j的情况下的最大价…

网络网络层之(3)IPv6地址

网络网络层之(3)IPv6协议 Author: Once Day Date: 2024年4月2日 一位热衷于Linux学习和开发的菜鸟&#xff0c;试图谱写一场冒险之旅&#xff0c;也许终点只是一场白日梦… 漫漫长路&#xff0c;有人对你微笑过嘛… 全系列文档可参考专栏&#xff1a;通信网络技术_Once-Day的…

简化备案域名查询的最新API接口

随着互联网的发展&#xff0c;越来越多的网站和域名被注册和备案。备案域名查询是一个非常重要的功能&#xff0c;可以帮助用户在特定时间段内查询已备案的域名信息。现在&#xff0c;我将介绍一个简化备案域名查询的最新API接口&#xff0c;该接口可以帮助用户快速查询备案域名…

SQL 注入神器:jSQL Injection 保姆级教程

一、介绍 jSQL Injection是一种用于检测和利用SQL注入漏洞的工具&#xff0c;它专门针对Java应用程序进行SQL注入攻击。以下是关于jSQL Injection的一些介绍&#xff1a; 功能特点&#xff1a; 自动化扫描&#xff1a; jSQL Injection具有自动化扫描功能&#xff0c;能够检测J…

Cesium入门路上的问题解决和知识点集合

想要进行cesium事件处理&#xff0c;必然会涉及到Cesium.ScreenSpaceEventHandler(viewer.scene.canvas)但是与js不同&#xff0c;viewer的位置要先于viewer调用代码大小写错了&#xff0c;就会找不到构造的东西​ 练习时这个方法无效主要是setInputAction方法的括号位置错误应…

精品推荐-2024护网HVV实战教程资料合集(共20章)

以下是资料目录&#xff0c;如需下载&#xff0c;请前往星球获取&#xff1a;https://t.zsxq.com/19vwYrf4t 精品推荐&#xff0c;2024护网HVV实战教程资料合集&#xff0c;压缩包内涵大量实战资料&#xff0c;共20章。星球内会持续更新教程包。 01-HW介绍.zip 02-HTTP&Bu…

揭秘微信如何设置自动回复

01 自动通过好友后自动回复设置 02 个人聊天的关键字自动回复设置 不仅如此&#xff0c;在微信私域管理系统上还可以进行批量多个号自动添加好友、批量群发、定时发朋友圈等操作&#xff0c;可以大幅度提升工作效率&#xff0c;将繁琐的任务交给系统来完成&#xff0c;从而节省…

【【萌新的Pytorch入门之Python的学习】】

学习记录 - 参考记录来自B站up主 -爆肝杰哥 ① NumPy 包为 Python 加上了关键的数组变量类型&#xff0c;弥补了 Python 的不足&#xff1b; ② Pandas 包在 NumPy 数组的基础上添加了与 Excel 类似的行列标签&#xff1b; ③ Matplotlib 库借鉴 Matlab&#xff0c;帮 Python 具…

论文《Structural Information Enhanced Graph Representation for Link Prediction》阅读

论文《Structural Information Enhanced Graph Representation for Link Prediction》阅读 论文概况Introduction问题一&#xff1a;**现有的节点标记技巧只能帮助感知路径深度&#xff0c;而缺乏对路径“宽度”的感知&#xff0c;例如节点度或路径数量**。问题二&#xff1a;G…

软考117-上午题-【计算机网络】-杂题+小结

一、杂题 真题1&#xff1a; 真题2&#xff1a; 真题3&#xff1a; 真题4&#xff1a; 真题5&#xff1a; 真题6&#xff1a; 真题7&#xff1a; 真题8&#xff1a; 真题9&#xff1a; 真题10&#xff1a; 真题11&#xff1a; 真题12&#xff1a; 真题13&#xff1a; 真题14&a…

【算法集训】基础算法:二分查找 | 概念篇

二分枚举&#xff0c;也叫二分查找&#xff0c;指的就是给定一个区间&#xff0c;每次选择区间的中点&#xff0c;并且判断区间中点是否满足某个条件&#xff0c;从而选择左区间继续求解还是右区间继续求解&#xff0c;直到区间长度不能再切分为止。 由于每次都是把区间折半&am…

AUTOSAR MCAL for SemiDrive E3 功能模块使用介绍:I2C

一、 概述 本文主要介绍如何使用芯驰提供的 AUTOSAR MCAL 软件包&#xff0c;开发 SemiDrive E3 的 I2C 模块&#xff0c;对 RTC 芯片进行读写操作。 硬件使用 E3640 GATEWAY 开发板&#xff0c;软件包为 mcal3.1。 图1 硬件环境 二、模块简介 E3 系列最多支持 8 个 I2C&am…

【51单片机入门记录】A/D D/A转换器概述

目录 一、A/D D/A转换器简介 &#xff08;1&#xff09;模数转换器-ADC &#xff08;analogue-to-digital conversion&#xff09; &#xff08;2&#xff09;数模转换器-DAC&#xff08;digital-to-analogue conversion&#xff09; &#xff08;3&#xff09;应用场景 二…

全国计算机等级考试三级Linux应用与开发技术考试-习题汇总

https://blog.csdn.net/qq_42025798/article/details/119155696 3.第1章-计算机体系结构与操作系统-练习题-简答题 https://blog.csdn.net/qq_42025798/article/details/119186151 4.第1章-计算机体系结构与操作系统-练习题-填空题 https://blog.csdn.net/qq_42025798/article/…

gulp项目配置,压缩css,压缩js,进行监听文件改动

1&#xff0c;创建项目 npm install -g gulp这个应该很熟悉&#xff0c;就是全局安装gulp 2&#xff0c;创建一个工程&#xff0c;使用node创建&#xff0c;统一命令 npm init -y3,创建后&#xff0c;目录出现一个package.json文件&#xff0c;没错&#xff0c;就是我们用vu…

【Leetcode每日一题】模拟 - 外观数列(难度⭐⭐)(51)

1. 题目解析 题目链接&#xff1a;38. 外观数列 这个问题的理解其实相当简单&#xff0c;只需看一下示例&#xff0c;基本就能明白其含义了。 2.算法原理 所谓“外观数列”&#xff0c;其实只是依次统计字符串中连续且相同的字符的个数。依照题意&#xff0c;依次模拟即 可。…

Java面向对象进阶基础知识

面向对象进阶 static 静态变量 被该类的所有的对象共享 不属于对象,属于类 随着类的加载而加载,优先于对象存在 类名调用(推荐) 对象名调用 static的注意事项 静态方法中没有this关键字 静态方法,只能访问静态 非静态方法可以访问所有 在Java中&#xff0c;static关…

元宇宙虚拟空间的碰撞体检测(四)

前言 该文章主要讲元宇宙虚拟空间的碰撞体检测&#xff0c;基本技术点&#xff0c;不多说&#xff0c;直接引入正题。 碰撞体检测 这里可以看到检测代码的逻辑是经过一系列判断&#xff0c;最后判断模型类型属性如果是trimesh&#xff0c;那么通过解析出来的顶点来生成我们的…

Linux:IO多路转接之select

文章目录 selecttimeval结构体fd_set 优缺点分析完整代码 本节要介绍的主题是多路转接式IO select 先说结论&#xff0c;这个select是做什么的呢&#xff1f; select是负责在Linux系统中&#xff0c;让一个人可以有多个鱼竿&#xff0c;可以不停的进行轮询&#xff0c;只要有…