TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  问题讨论与解答  统计信息与排名
  • 首页
  • 题库
  • P4258
  • 题目
  • P4258土拨鼠猎人
    限制 : 时间限制 : - MS   空间限制 : 165536 KB
    评测说明 : 1s
    问题描述

    Sparrow是一只土拨鼠。

    作为一只可爱又机智的土拨鼠,Sparrow常常被土拨鼠猎人们盯上。众所周知,土拨鼠很擅长打洞,他把每个洞按照1,2,3,4,……的顺序从小到大编号。为了迷惑土拨鼠猎人,Sparrow只选择了一些编号特殊的洞作为居住地。这些特殊的洞的编号满足以下几个条件:

     

    1.不含前导零。

    2.如果位数大于等于三位,则不存在连续三位数字构成“233”。如“15233”,“23345”就不是特殊编号的洞。

    3.如果位数大于等于三位,则不能同时满足存在“连续两位数字相等”和“某一个数字恰好等于它右边的数字加一”。如“13396”和“25481”满足条件,而“65377”则不行。

    4.特别地,1~99不足三位,它们也是特殊的编号。

     

    现在,天才土拨鼠猎人MLX得到可靠情报,Sparrow藏在编号第N小的特殊的洞里。你能告诉MLX这个洞的编号吗?

    输入格式

    仅一行,包含一个数字N。

    输出格式

    仅一行,为一个整数,表示标号第N小的特殊的洞的编号。

    样例输入

    110

    样例输出

    112

    提示

    【样例解释】

     

    100和110不是特殊编号的洞。

     

    【数据范围】

     

    对于10%的数据,N≤104

    对于30%的数据,N≤108

    对于100%的数据,1≤N≤3×1017,保证答案不会超过long long


    来源  OBlack rgnoH