大家好，又见面了，我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。
Jetbrains全系列IDE稳定放心使用
Problem C: Selfdescribing Sequence
| Problem C: Selfdescribing Sequence |
Solomon Golomb’s
selfdescribing sequence
is the only nondecreasing 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:
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 ( 
). 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;
}
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/188752.html原文链接：https://javaforall.net
