Chinaunix首页 | 论坛 | 博客
  • 博客访问: 328297
  • 博文数量: 93
  • 博客积分: 2515
  • 博客等级: 少校
  • 技术积分: 1025
  • 用 户 组: 普通用户
  • 注册时间: 2007-09-18 22:51
文章分类

全部博文(93)

文章存档

2010年(2)

2009年(26)

2008年(65)

我的朋友

分类: C/C++

2009-09-18 16:59:54

1081. Binary Lexicographic Sequence

Time Limit: 0.5 second
Memory Limit: 16 MB

Consider all the sequences with length (0 < N < 44), containing only the elements 0 and 1, and no two ones are adjacent (110 is not a valid sequence of length 3, 0101 is a valid sequence of length 4). Write a program which finds the sequence, which is on K-th place (0 < K < 109) in the lexicographically sorted in ascending order collection of the described sequences.

Input

The first line of input contains two positive integers N and K.

Output

Write the found sequence or −1 if the number K is larger then the number of valid sequences.

Sample

input output
3 1
000
Problem Author: Emil Kelevedzhiev
Problem Source: Winter Mathematical Festival Varna '2001 Informatics Tournament
 
--------------
此题是在做UVA上的一个关于FIBINARY NUMBERS的题时GOOGLE到的,这题比较简单,直接DFS就可以了,在这记录主要是基于这题的FIBONACCI 进位有趣..
 
附个UGLY CODE..
谁叫TIMUS不保存代码..
 
 

#include "stdio.h"
#include "string.h"
#include "math.h"
#include "stdlib.h"

#define maxn 50
#define K 50

char s1[K], s2[K];
int fib[maxn];

void solve(int st, int f, char *s)
{
    if(0==f)
        return;
    int i, j;
    for(i=st; i>=1; i--)
    {
        if(f>=fib[i])
        {
            f -= fib[i];
            s[i] = '1';
            solve(i-2, f, s);
        }
    }
}

int main()
{
    freopen("c:\\in.txt", "r", stdin);
    //freopen("c:\\out.txt", "w", stdout);


    int i;

    char ans[K];

    fib[0] = fib[1] = 1;
    for(i=2; i<45; i++)
        fib[i] = fib[i-1]+fib[i-2];
    
    int n, k;
    int st;
    while(scanf("%d %d", &n, &k) != EOF)
    {
        st = 44;
        k--;

        if(k>=fib[n+1])
        {
            printf("-1\n");
            continue;
        }

        memset(ans, '\0', (n+1) * sizeof(ans[0]));
        solve(st, k, ans);

        i = st;
        
        for(i=n; i>0; i--)
        {
            if(ans[i]=='1')
                printf("%c", ans[i]);
            else
                printf("%c", '0');
        }
        printf("\n");
    }

    return 0;
}

阅读(832) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~