10049 - Self-describing Sequence
Time limit: 3.000 seconds
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=34&page=show_problem&problem=990
Solomon Golomb'sselfdescribing sequenceis
the only nondecreasing sequence of positive integers with the property that it contains exactlyf(k)
occurrences ofkfor eachk. A few moments thought
reveals that the sequence must begin as follows:
In this problem you are expected to write a program that calculates the value off(n)
given the value ofn.
The input may contain multiple test cases. Each test case occupies a separate line and contains an integern().
The input terminates with a test case containing a value0fornand this case must not be processed.
For each test case in the input output the value off(n) on a separate line.
100
9999
123456
1000000000
0
21
356
1684
438744
1. 如何构造一个增长速率较快的递推式?
注意到f(n)增长缓慢,不妨利用其反函数g(n)=max{m | f(m)=n}(比如g(4)=8),然后再求一次反函数f(n)=min{k | g[k]>=n}即可得到f(n)。
随后由f(n)的定义有g(n)=g(n-1)+f(n)=g(n-1)+min{k | g[k]>=n}
(比如g(4)=g(3)+f(4)=5+3=8,g(5)=g(4)+f(5)=8+3=11)
2. 如何计算min{k | g[k]>=n}?
用二分查找。
完整代码:
/*0.075s*/
#include<cstdio>
#include<algorithm>
const int M = 700000;
using namespace std;
long long g[M];
int main()
{
g[1] = 1;
g[2] = 3;
for (int i = 3; i < M; ++i)
g[i] = g[i - 1] + (lower_bound(g + 1, g + i, i) - g);
int n;
while (scanf("%d", &n), n)
printf("%d\n", lower_bound(g + 1, g + M, n) - g);
return 0;
}
分享到:
相关推荐
XFS Self Describing Metadata.
中职课程英语Unit-1-2-Describing-People.pdf
Effective Business Modeling with UML-Describing Business Use Cases and Realizations-TheRationalEdge_Nov2002.pdf
Locus of control and self-concept in achieving and underachieving bright elementary students Teacher Ratings 395 RIEBER, M., & WOMACK, M. Intelligence of preschool children as related to ethnic ...
Contemporary software design increasingly relies on software components in the form of self-contained and self-describing packages of functionality. Key to such components is that they present a ...
You’ll discover the great styling possibilities of CSS paired with semantic structures like Microformats and RDFa, while enriching the self-describing semantics of XHTML content. Learn how to group ...
In his great speech at Washington, when describing himself as having begun his political career as an alderman, and run through all the branches of the legislature, a voice in the crowd cried, "From ...
Describing people 英语描述一个人PPT课件.pptx
TIBCO Rendezvous(或称为TIBCO RV)也是一种中间件,具有发布/订阅(Publish/Subscribe)、基于主题寻址(Subject-Based Addressing) 和自定义数据信息(Self-Describing Data Messages)等专利技术功能,使不同应用平台...
TIBCO Rendezvous(或称为TIBCO RV)产品是一种中间件,它具有发布/订阅(Publish/Subscribe)、基于主题寻址(Subject-Based Addressing) 和自定义数据信息(Self-Describing Data Messages)等专利技术功能,使不同应用...
TIBCO Rendezvous(或称为TIBCO RV)产品是一种中间件,它具有发布/订阅(Publish/Subscribe)、基于主题寻址(Subject-Based Addressing) 和自定义数据信息(Self-Describing Data Messages)等专利技术功能,使不同应用...
TIBCO Rendezvous(或称为TIBCO RV)产品是一种中间件,它具有发布/订阅(Publish/Subscribe)、基于主题寻址(Subject-Based Addressing) 和自定义数据信息(Self-Describing Data Messages)等专利技术功能,使不同应用...
Lower total cost of ownership with reusable self-describing applications, no registry, robustness and security and simplified deployment. Note: There is a .NET runtime for Windows 98 and up. The ...
The code is meant to be as self-describing as possible, so I do not plan to include much documentation. It is assumed that you know the basics; if you want to learn algorithms perhaps it is a wrong ...
这是为技术演讲“Self-describing REST-Services with RAML and BPMN”创建的示例 它由一个带有 Jersey 启动模块的 Spring Boot 应用程序和提供的RAML 到 JAX-RS和Brainslug BPMN 渲染器插件组成。 经过一连串 mvn...
一 客观描述图 二 说明意思 三 给出观点 【范文】 As is vividly depicted in the drawing, in front of computers and in narrow spaces are sitting many people, exchanging their views with each ...
The Device Class Definition for HID 1.11 is intended to supplement the USB Specification and provide HID manufacturers with the information ...> be self-describing to allow generic software applications
Popular science/hobbyist writer Stan Gibilisco covers every important aspect of basic (algebra-based) statistics, including: notation and jargon, describing, tables, graphs, randomness and uncertainty...
NetCDF文件是自描述的,网络透明的,可直接访问且可扩展的。 Self-describing是指netCDF文件包含有关其包含的数据的信息。 Network-transparent意味着netCDF文件以一种形式表示,可由计算机以不同的方式存储整数,...
Contemporary software design increasingly relies on software components in the form of self-contained and self-describing packages of functionality. Key to such components is that they present a ...