CDOJ 1264 人民币的构造 区间问题+数论
2024-09-07 10:03:28
人民币的构造
Time Limit: 3000/1000MS (Java/Others) Memory Limit: 65535/65535KB (Java/Others)
Submit Status
我们都知道人民币的面值是1、2、5、10,为什么是这个数值呢,我们分析了下发现,从1−10的每个数字都可以由每种面值选出至多一张通过加法和减法(找钱)来构成,(比如:1+2=3,5−1=4,5+1=6,5+2=7,1+2+5=8,10−1=9)
但是实际上,我们只需要1、2、7三种面值就可以组成1−10的每一个数字了
(1+2=3,7−1−2=4,7−2=5,7−1=6,7+1=8,7+2=9,7+1+2=10)
那么现在问题来了,给一个数n,请问最少需要多少种不同的面值就可以构成从1−n的所有数字,注意在构成每一个数字时同种面值不能超过1张。
Input
一个数字n(1<=n<=100000)
Output
一个数字,代表最少需要多少种不同的面值可以构成从1−n的所有数字。
Sample input and output
Sample Input Sample Output
10
3
Source
第七届ACM趣味程序设计竞赛第三场(正式赛)
;
假设当前能取到1-K区间,,加入一个数A后(A>K),,能取到的数的区间为[A-K,A+K],因为A的量是不定的,为了尽量右移,所以A-K=K+1,所以A=2*K+1,则最右端点A+K=3*K+1,,即能取到【1,3*K+1】;
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int a[10005];
int main()
{
a[1]=1;
for(int i=2;i<=12;i++)
a[i]=3*a[i-1]+1;
int n;
while(~scanf("%d",&n))
{
for(int i=1;i<=12;i++)
if(n<=a[i])
{
cout<<i<<endl;
break;
}
}
return 0;
}
最新文章
- mysql+mycat搭建稳定高可用集群,负载均衡,主备复制,读写分离
- iOS 字典或者数组和JSON串的转换
- 优化Select 语句的原则
- java web项目获取各种路径
- Unknow Unknow
- R语言画图布局摆放(layout)
- Transact-SQL
- audio 设置 currentTime 失效 的解决办法
- mysql数据库备份及恢复命令mysqldump,source的用法
- SKShapeNode类
- C++类静态成员的初始化和用法探讨
- URAL 1963 Kite 四边形求对称轴数
- bullet_01
- Spring+SpringMVC+MyBatis深入学习及搭建(十二)——SpringMVC入门程序(一)
- 升级项目到.NET Core 2.0,在Linux上安装Docker,并成功部署
- PHP7开启Opcode开启强悍性能
- SpringBoot1
- 对比学IT---路由器和linux流量统计的差别
- 写一个Windows服务
- 一个线上程序bug,由通用补数程序引起