VUDBOL7 - Planning Poker

Planning Poker, also called Scrum poker, is a consensus-based technique for estimating, mostly used to estimate effort or relative size of user stories in software development.
A typical Planning Poker Deck has cards showing the Fibonacci sequence including a zero: 0, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89. other decks use similar progressions.
We have some tasks estimated with other complexities from 1 to 10000000.
We need to estimate the complexity of all tasks using the Fibonacci sequence used in Planning Poker. The rule is that the old complexity will change to the valid complexity more close. But if two complexities are in equal distances take the higher.

Input

The input consists of multiple test cases.
Each test case begins with a line containing an integer “N” (1 <= N <= 100000) the number of tasks. In the following line are the complexities of "N" tasks from "0" to "N-1" (1 <= task[i] <= 10000000).
The end of input is indicated by a line with one zero. This is not a part of any test cases.

Output

For each test case print the list of new complexities sorted in ascending order. Print a space character between two complexities.

Example

Input:
5
1 2 3 4 5
5
7 8 9 11 10
0

Output:
1 2 3 5 5
8 8 8 8 13

ID RESULT TIME
code...



Added by:Edwin Guzman
Date:2012-04-25
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:ASM32-GCC MAWK BC C-CLANG C NCSHARP C++ 4.3.2 CPP CPP14 CPP14-CLANG COBOL COFFEE D-CLANG D-DMD DART ELIXIR FANTOM FORTH GOSU GRV JAVA JS-MONKEY JULIA KTLN NIM NODEJS OBJC OBJC-CLANG OCT PICO PROLOG PYPY PYPY3 PY_NBC R RACKET RUST CHICKEN SQLITE SWIFT UNLAMBDA VB.NET

hide comments
2012-06-07 11:02:23 npsabari
@Francky: The time complexity of my algo is O(N).. and the constant in that can be max log(35).. even then i am getting .74 sec.. So how is your algo that fast??
2012-05-20 17:24:31 Rishi Mukherje
Please open it for python and increase the time limit. :)
2012-05-10 20:44:57 Gaurav
@problem setter : could you pls tell me where my soln is getting wrong..THanks!!
2012-05-09 13:27:53 Francky
@ Devil D and others :
I have two distinc solutions:
0.12s -> O( N×log( task ) )
0.11s -> O( N×log(log( maxTask )) )

With harder tests cases the second one could be much faster than the first one.
---
It could be fine to open this problem to all languages, please. (with a little more time, too, for the lovely python)
2012-05-08 15:36:31 Ikhaduri
I have the same question as Devil D
2012-05-08 13:02:27 Devil D
What is the complexity required for the solution ..nlogn is getting TLE
2012-05-03 15:33:05 Vimal poonia
@ EHOR ..

read description...

Last edit: 2012-05-03 15:34:18
2012-05-03 10:28:14 Ehor Nechiporenko
Could someone explain me, why in last test case for 11 we have result 8, but for 10 result is 13?
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.