uva1599_cumulative iteration number

uva1599_cumulative iteration numberProblemC:Self­describingSequence SolomonGolomb’s self­describingsequence  istheonlynon­decreasingsequenceofpositiveintegerswiththepropertythatitcontainsexactly f(k)

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE稳定放心使用

  Problem C: Self­describing Sequence 

Solomon Golomb’s 
self­describing sequence
 

$\langle f(1), f(2), f(3), \dots \rangle$
 is the only non­decreasing sequence of positive integers with the property that it contains exactly 
f
(
k
) occurrences of 
k
 for each 
k
. A few moments thought reveals that the sequence must begin as follows:

\begin{displaymath}\begin{array}{c\vert cccccccccccc}\mbox{\boldmath $n$} & 1 &......)$} & 1 & 2 & 2 & 3 & 3 & 4 & 4 & 4 & 5 & 5 & 5 & 6\end{array}\end{displaymath}


In this problem you are expected to write a program that calculates the value of 
f
(
n
) given the value of 
n
.

Input 

The input may contain multiple test cases. Each test case occupies a separate line and contains an integer n ( $1 \le n \le 2,000,000,000$). The input terminates with a test case containing a value0 for n and this case must not be processed.

Output 

For each test case in the input output the value of f(n) on a separate line.

Sample Input 

100
9999
123456
1000000000
0

Sample Output 

21
356
1684
438744


Miguel Revilla 
2000-12-26

#include <cstdio>
#include <cstdlib>
#include <cassert>
#include <cstring>

/*
 * n    1  2  3  4  5  6  7  8  9 10 11 12 ...
 * f(n) 1  2  2  3  3  4  4  4  5  5  5  6 ...
 */

const int NMAX = 1000000;

void solve()
{
    int n;
    if (scanf ("%d", &n) == EOF || 0 == n) {
        exit (0);
    }

    static int g[NMAX];
    g[0] = 0;
    g[1] = 1;

    int i = 1;
    int fi = 1;
    int k = 1;

    while (g[i - 1] < n) {
        g[i] = g[i - 1] + fi;
#ifndef ONLINE_JUDGE
        printf ("g[%d] = %d\n", i, g[i]);
#endif
        if (++i > g[k]) {
            ++fi;
            ++k;
        }
        assert (i < NMAX);
    }

    printf ("%d\n", i - 1);
}

int main (int argc, char **argv)
{
    while (true) {
        solve();
    }
    return 0;
}

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/188752.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • HDU 2160 母猪的故事

    HDU 2160 母猪的故事

  • 警告:Your CPU supports instructions that this TensorFlow binary was not compiled to use: AVX2 FMA

    警告:Your CPU supports instructions that this TensorFlow binary was not compiled to use: AVX2 FMA问题:安装TensorFlow(CPU版本),使用pipinstalltensorflow安装,安装一切顺利,但是在跑一个简单的程序时,遇到如下情况:大概意思是:你的CPU支持AVX扩展,但是你安装的TensorFlow版本无法编译使用。原因:除了通常的算术和逻辑,现代CPU提供了许多低级指令,称为扩展,例如,SSE2,SSE4,AVX等来自维基百科:高级矢量扩…

  • trylock 用法_Java lock

    trylock 用法_Java lock在并发编程中,为了避免多线程同时读写共享资源,我们需要互斥。Go标准库提供了互斥锁sync.Mutex,通过加锁Lock()方法和解锁Unlock()方法达到对共享资源的并发控制。在之前的设计中,当锁被占有,其他goroutine尝试获取锁时会被阻塞。这种方式当然是合理的,但是在某些情况下,或许我们希望在获取锁失败时,并不想停止执行,而是可以进入其他的逻…

    2022年10月10日
  • CALayer之anchorPoint分析

    CALayer之anchorPoint分析anchorPoint:CALayer中心点,动画特效的中心点,取值区间[0.0,1.0],默认为(0.5,0.5);position:CALayer中心点坐标;frame.origin:由anchorPoint、position共同计算得出:frame.origin.x=position.x-anchorPoint*bounds.size.wi

  • 怎样解决栈溢出

    怎样解决栈溢出

    2021年11月14日
  • SpringCloud之服务网关Gateway[通俗易懂]

    SpringCloud之服务网关Gateway[通俗易懂]前言SpringCloud是微服务中的翘楚,最佳的落地方案。SpringCloudGateway是SpringCloud新推出的网关框架,之前是NetflixZuul。网关通常在项目中为了简化前端的调用逻辑,同时也简化内部服务之间互相调用的复杂度;具体作用就是转发服务,接收并转发所有内外部的客户端调用;其他常见的功能还有权限认证,限流控制等等。…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号