P3424 [POI2005]SUM-Fibonacci Sums

    • 48通过
    • 203提交
  • 题目提供者 codesonic
  • 评测方式 云端评测
  • 标签 斐波那契,Fibonacci 贪心 POI 2005 高性能
  • 难度 提高+/省选-
  • 时空限制 2000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    题意翻译

    斐波那契数是一个这样定义的整数:$F(0)=1$ ,$F(1)=1$ ,$F(i)=F(i-1)+F(i-2)$ $(i>=2)$ ,前几个数是这样的$(1,1,2,3,5,8...)$

    伟大的计算机学家Byteazar在制作一个不寻常的计算机,其中数由斐波那契系统表示,如一个数列($b_1$ ,$b_2$ ,...,$b_n$ )表示数字$F(1)*b_1+b_2*F(2)+...+b_n*F(n)$ (我们不使用F(0))。不幸的是,这样的表示是不明确的,即相同的数字可以具有不同的表示。比如42可以表示为$(0,0,0,0,1,0,0,1)$ ,$(0,0,0,0,1,1,1,0)$ 或$(1,1,0,1,0,1,1)$ ,由于这个原因,Byteazar只使用满足以下条件的表示方式:

    如果$n>1$ ,那么$b_n=1$ ,即数字的表示不包含前导零。

    如果$b_i=1$ ,那么$b_{i+1}=0$ ,即数字的表示不包含两个(或多个)连续的数字。

    计算机的建设很明显比Byteazar所认想的要难。帮助他一下!

    写一个程序:

    从标准输入读取两个正整数的表示,计算并向标准输出写入其和的表示。

    输入格式:

    输入的第一行先是一个正整数,为$x$ 的斐波那契表示的长度,接下来的序列是x的斐波那契表示

    第二行的第一个数字也是一个正整数,为$y$ 的斐波那契表示的长度,接下来的序列是y的斐波那契表示

    输出格式:输出只有一行程序,应写入$x+y$ 的和的斐波纳契表示(满足上述条件),同样是先输出一个正整数$n$ ,表示$x+y$ 的和的斐波纳契表示的长度,然后再输出$x+y$ 的和的斐波那契表示。 $1\leqn\leq1000000$

    感谢@codesonic 提供的翻译

    题目描述

    Fibonacci numbers are an integer sequence defined in the following way: $Fib_0=1$, $Fib_1=1$, $Fib_i=Fib_{i-1}+Fib_{i-2}$ (for $i\ge 2$). The first few numbers in this sequence are: ($1,1,2,3,5,8,\cdots$).

    The great computer scientist Byteazar is constructing an unusual computer, in which numbers are represented in Fibonacci system i.e. a bit string $(b_1,b_2,\cdots,b_n)$ denotes the number $b_1\cdot Fib_1+b_2\cdot Fib_2+\cdots+b_n\cdot Fib_n$. (Note that we do not use $Fib_0$.) Unfortunately, such a representation is ambiguous i.e. the same number can have different representations. The number $42$, for instance, can be written as: $(0,0,0,0,1,0,0,1)$, $(0,0,0,0,1,1,1,0)$ or $(1,1,0,1,0,1,1)$. For this very reason, Byteazar has limited himself to only using representations satisfying the following conditions:

    if $n>1$, then $b_n=1$, i.e. the representation of a number does not contain leading zeros.

    if $b_i=1$, then $b_{i+1}=0$ (for $i=1,\cdots,n-1$), i.e. the representation of a number does not contain two (or more) consecutive ones.

    The construction of the computer has proved more demanding than Byteazar supposed. He has difficulties implementing addition. Help him!

    TaskWrite a programme which:

    reads from the standard input the representations of two positive integers,calculates and writes to the standard output the representation of their sum.

    斐波那契数列和

    (译者注:不太会使用markdown且是在记事本编辑,具体变量请参照英文原文,同时也请管理员不要删除英文原文)

    斐波那契数是一个这样定义的整数:F(0)=1,F(1)=1,F(i)=F(i-1)+F(i-2)(i>=2),前几个数是这样的(1,1,2,3,5,8...)

    伟大的计算机学家Byteazar在制作一个不寻常的计算机,其中数由斐波那契系统表示,如一个数列(b1,b2,...,bn)表示数字F(1)*b_1+F(2)*b_2+...+b_n*F(n)(我们不使用F(0))。不幸的是,这样的表示是不明确的,即相同的数字可以具有不同的表示。比如42可以表示为(0,0,0,0,1,0,0,1),(0,0,0,0,1,1,1,0)或(1,1,0,1,0,1,1),由于这个原因,Byteazar只使用满足以下条件的表示方式:

    如果n>1,那么b_n=1,即数字的表示不包含前导零。

    如果b_i=1,那么b_(i+1)=0,即数字的表示不包含两个(或多个)连续的数字。

    计算机的建设很明显比Byteazar所认想的要难。帮助他一下!

    写一个程序:

    从标准输入读取两个正整数的表示,计算并向标准输出写入其和的表示。

    输入输出格式

    输入格式:

    The input contains the Fibonacci representations (satisfying the aforementioned conditions) of two positive integers $x$ and $y$ - one in the first, the other in the second line. Each of these representations is in the form of a sequence of non-negative integers, separated by single spaces. The first number in the line denotes the length of the representation $n$, $1\le n\le 1\ 000\ 000$. It is followed by $n$ zeros and/or ones.

    输入的第一行先是一个正整数,为x的斐波那契表示的长度,接下来的序列是x的斐波那契表示

    第二行的第一个数字也是一个正整数,为y的斐波那契表示的长度,接下来的序列是y的斐波那契表示

    输出格式:

    In the first and only line of the output your programme should write the Fibonacci representation (satisfying the aforementioned conditions) of the sum $x+y$. The representation should be in the form of a sequence of non-negative integers, separated by single spaces, as it has been described in the Input section. The first number in the line denotes the length of the representation $n$, $1\le n\le 1\ 000\ 000$. It is followed by $n$ zeros and/or ones.

    输出只有一行程序,应写入x+y的和的斐波纳契表示(满足上述条件),同样是先输出一个正整数n,表示x+y的和的斐波纳契表示的长度,然后再输出x+y的和的斐波那契表示。

    保证输入输出的数据长度都不大于1000000也不小于1

    输入输出样例

    输入样例#1: 复制
    4 0 1 0 1
    5 0 1 0 0 1
    输出样例#1: 复制
    6 1 0 1 0 0 1
    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。