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
2016-05-16 20:43:22
O(nlog(n)) passes easily. I don't see anything difficult here, basic binary search stuff. One can easily think of an O(n) solution for this problem too.

Last edit: 2016-05-16 20:44:04
2016-05-16 13:16:04
No precomputation , O(NlogN) just fast I/O and got AC.
2014-05-18 10:29:10 RIVU DAS
Nice ques!!!
2013-04-26 22:00:44 Federico Lebrón
EDIT: Nothing :)

Last edit: 2013-04-26 22:33:00
2012-09-06 23:12:01 Sardar Khan
a li'l misunderstanding about precomputation led to hell lot of TLEs
BUT finally AC:))
2012-08-21 22:15:34 Secret
@uddipta thnx :)
2012-06-17 07:50:53 (Tjandra Satria Gunawan)(曾毅昆)
@sabari: yes, my algo is O(N)... I use some precomputation and I/O optimization.
without it, I got 0.75s (submission ID: 7163528)
----------------------------------------------
I wonder why there's no JAVA AC solution?
2012-06-17 07:28:07 npsabari
@Tjandra : How did you manage to do in 0.19 sec.. is your algorithm O(N) or less than that? or some I/O optimization..?
I used O(N) algo and got 0.7 sec.
2012-06-14 18:10:07 uddipta maity
Don't use cin, cout!!!!
2012-06-14 17:14:54 __KIRA__
@ALL precompute and O(N) also tle.
only got it using fast i/o .strange!!!
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.