d751. Q10049-Selfdescribing Sequence＠Morris' Blog｜PChome Online 人新台

Morris' Blog 我在摸索我存在的意、生命的意、涵及值。有真正神手般的害，套用模式是大部分的情。那害的我存在的意何，托出神的存在？有候不能怪人不我，我已始省思，什我有人的原因，而是全要靠人。有候我我不同，那是因我做不到很多人能到的事情。我不到、玩不起、得不明、理解得不多，我缺少的文能力，就是一切一切能的判定。此，我不得能做些人有助的事情。我知道我自己是不服的性格，但在我不得不。我有能力，因此我必。我到底世界作什？充不定性，而我是法出拔萃，想一般人似乎也回不了了。越大的挑需要越力的支持，而我的支持是什？最近人，但都是失的局，人能接受，不需要言，不需要通，一切所想都表不出。
49的鼓 6站台

2011-09-16 08:40:34| 人1,333| 回0 | 上一篇 | 下一篇

d751. Q10049-Selfdescribing Sequence

推 0 收藏 0 0 站台

容：

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.

入明：

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 value 0 for n and this case must not be processed.

出明：

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

例入：

100 9999 123456 1000000000 0

例出：

21 356 1684 438744

提示：

出：

UVa ACM 10049 (管理：david942j)

作法 : 建出一部份的表
Solomon Golomb的自我描述序列（selfdescribing sequence）＜f(1), f(2), f(3), ......＞是一唯一的不下降序列。在此序列的正整的特k在序列中出f(k)次。

/**********************************************************************************/
/* Problem: d751 "Q10049-Selfdescribing Sequence" from UVa ACM 10049           */
/* Language: C (717 Bytes)                                                   nbsp;   */
/* Result: AC(52ms, 280KB) judge by this@ZeroJudge                               */
/* Author: morris1028 at 2011-09-16 08:36:37                                     */
/**********************************************************************************/

#include<stdio.h>
struct {
   int n, fn;
}A[4811];
int BinarySearch(int l, int r, int v) {
   int m;
   do {
       m = (l+r)/2;
       if(A[m].n < v)   l = m+1;
       else {
           if(A[m].n >= v && A[m-1].n < v)
               return m;
           r = m-1;
       }
   } while(l <= r);
}
int fn(int n, int limit) {
   int i, fn;
   if(n == 1)   return 1;
   i = BinarySearch(1, limit, n);
   i--;
   fn = (n - A[i].n)/i + A[i].fn;
   return fn;
}
main() {
   A[1].n = 1, A[1].fn = 1;
   A[2].n = 2, A[2].fn = 2;
   A[3].n = 6, A[3].fn = 4;
   int i;
   for(i = 4; i < 4811; i++) {
       A[i].n = A[i-1].n + fn(i-1, i-1)*(i-1);
       A[i].fn = A[i-1].fn + (A[i].n - A[i-1].n)/(i-1);
   }
   while(scanf("%d", &i) == 1 && i)
       printf("%d\n", fn(i, 4810));
   return 0;
}