Self-describing Sequence

문제풀이

>특수한 f(x) 함수에서 규칙을 찾아내어 f(n)을 구한다.

>함수의 규칙을 찾아내어 간단히 구현하는게 중요

 

배울점

>f(1)+..+f(n)의 값을 k라 한다면 f(k)는 n이다.

>f(n)을 계산하기 위해서는 위 f(1)+..+f(x)의 값을 넘지않는 x을 찾는다.

 

소스>성공

 

#include <stdio.h>

int map[200][200];
int color[200];
int queue[40000];
int top, bot;

int main()
{
    int n, l, i, j, x, y, root;

    while (scanf("%d", &n), n != 0)
    {

        for (i = 0; i < n; i++)
        { // -1 not input, 1 on, 0 off//init
            color[i] = -1;
            for (j = 0; j < n; j++)
                map[i][j] = 0;
        }

        scanf("%d", &l);
        for (i = 0; i < l; i++)
        {
            scanf("%d %d", &x, &y);
            map[x][y] = 1;
            map[y][x] = 1;
        }

        color[0] = 1;   // first point is on
        top = 0;        // queue's top
        bot = 0;        // queue's tail
        root = 1;       // roop on
        queue[top] = 0; // first point is 0

        while (bot <= top && root)
        { // width search
            x = queue[bot++];
            for (i = 0; i < n; i++)
                if (map[x][i] == 1)
                    if (color[i] == -1)
                    {
                        queue[++top] = i;
                        color[i] = !color[x];
                    }
                    else if (color[x] == color[i])
                    {
                        root = 0;
                        break; // find NOT BICOLORABLE
                    }
        }

        if (root)
            printf("BICOLORABLE.\n");
        else
            printf("NOT BICOLORABLE.\n");
    }
    return 0;
}

#include <stdio.h>
#define MAX 1000000
int main()
{

    int n;
    static long arr[MAX];
    int i, count, f, sum;

    arr[1] = 1;
    arr[2] = 2;
    f = 2;
    sum = 3;
    count = 3; // bound
    while (1)
    {
        scanf("%d", &n);

        arr[1] = 1;
        arr[2] = 2;
        f = 2;
        sum = 3;
        count = 3; // bound

        if (n == 0)
            break; // exit

        for (i = 3; i < MAX; i++)
        {
            arr[i] = f;

            sum += arr[i];
            if (sum >= n)
                break;
            if (i == count)
            {
                f++;
                count += arr[f];
            }
        }
        if (n == 1)
            i = 1;
        else if (n <= 3)
            i = 2;
        printf("%d\n", i);
    }
    return 0;
}