2011-09-16 08:40:34Morris
d751. Q10049-Selfdescribing Sequence
d751. Q10049-Selfdescribing Sequence
/* Problem: d751 "Q10049-Selfdescribing Sequence" from UVa ACM 10049 */
/* Language: C (717 Bytes) */
/* 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;
}
內容 ：
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: 
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.
). 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)次。
/**********************************************************************************/作法 : 建出一部份的表
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) */
/* 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;
}