시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 44 26 23 56.098%

문제

*이 문제는 실제 인물과는 관련이 없습니다.*

옛날 먼 옛날, 사냐라는 사람이 살았습니다. 사냐라는 사람은 뢰벗이라는 친구가 있었는데, 둘은 매우 닮았지만, 뢰벗이 좀 더 똑똑하고, 사냐가 좀 더 잘생겼다고 합니다. 뢰벗은 오보워치(Ovorwatch) 라는 게임에서 500점으로 상위 100.00%였습니다. 사냐는 이러한 뢰벗을 놀리기를 좋아했습니다. 이에 열을 받은 뢰벗은, 사냐에게 자신이 오보워치 500점을 탈출한다면, 자신이 내는 문제를 평생 풀도록 하겠다는 내기를 했고, 사냐는 뢰벗이 설마 탈출하겠냐는 생각으로 수락했습니다.

그런데 그 일이 벌어졌습니다.

뢰벗은 오보워치 점수를 무려 600점대 까지 올렸고, 사냐는 내기 때문에 뢰벗이 내는 문제를 평생 풀어야 하게 되었습니다. 뢰벗은 사냐에게 자신이 주는 자연수를 연속하지 않은 피보나치 수들의 합으로 나타내게 시켰습니다. (피보나치 수열이란 F(1) = 1, F(2) = 2, F(n+2) = F(n+1) + F(n)으로 정의되는 수열입니다.) 멍청한 사냐는 피보나치 수열을 손으로 계산하는데, 시간이 너무 오래걸려 미칠것만 같아졌습니다. 이에 똑똑한 뢰벗은 그것도 계산 못하냐며 놀렸고, 사냐는 시무룩해졌습니다. 시무룩해진 사냐의 노동을 도와줄 프로그램을 짜봅시다.

입력

자연수 N을 입력받는다. (N < 1018)

출력

자연수 N이 연속되지 않은 i1 < i2 < ... < ik에 대하여 F(i1) + F(i2) + ... + F(ik)로 나타내어 진다면, 첫째줄에 k를 출력하고, 둘째줄에 F(i1), F(i2), ... , F(ik)를 사이에 공백을 두고 출력하여라. 아니라면, 첫째줄에 -1을 출력하여라. 만일 여러가지 방법으로 연속하지 않은 피보나치 수들의 합으로 나타낼 수 있다면, 그 가운데 항의 수가 가장 많은 것을 출력하여라.

예제 입력 1

10

예제 출력 1

2
2 8

출처

  • 문제를 만든 사람: leejseo
  • 문제의 오타를 찾은 사람: po10003