PEG Test - December 2014
As we all know, toys are mass-produced at the North Pole every year. Mass-production everywhere in the world (yes, even at the North Pole!) depends heavily on the assembly line. The North Pole production line for toys is much more extraordinary than normal ones found in a typical factory. For one, they are run by Santa's elves instead of humans. But more importantly, the way that toys are built is much different. In a typical assembly line, workers are at their own stations and a bunch of steps are done to intermediate semi-finished parts until a final product is reached.
At the North Pole, toys are made just a tad more magically than your
average automobile. Since toys are made up of a bunch of parts,
technically, one toy can also be considered a "part" if it is used later
in the making of another toy. It's not important to distinguish between
toys and parts for the purposes of this problem – Santa just wants to
get things done! To eliminate confusion, we shall refer to toys and
parts simply as "units". There are stations (numbered from
to
)
in the North Pole assembly line. Each station is meant to continuously
produce an unlimited amount of a particular type of unit. Specifically,
station
produces type-
units.
Station one produces elementary units (type- units), so
.
From thereon, a station
can only produce a unit of type-
if
is a sum of the unit types of exactly two (not necessarily
unique) stations that come before it. Therefore, just like a typical
assembly line, the type of unit produced at a station depends on the
stations before it.
For example, a valid sequence of production types is ,
,
, and
. The
elf at station two can make type-
units because it can take two of
station one's units and put them together
. The elf at station
three can make type-
units because it can take one of station one's
units and one of station two's units
. The elf at station four
can make type-
units because it can put together one of station two's
units and one of station three's units
.
Santa wants to make type- toys. Moreover, he wants the assembly line
for creating the toy to be as compact as possible, so toy production
rates can be maximized. You must help him determine the shortest
possible production line for producing this type of toy.
Input Specification
A single integer
, the type of toy that Santa
wants to produce.
Output Specification
Line should contain a single integer
specifying the length of the
shortest possible production line that produces the specified toy.
Line should contain
space-separated integers, the values of
, representing the types of units being
produced in each assembly line station.
Sample Input
5
Sample Output
4
1 2 3 5
Comments
Would an answer of:
4
1 2 4 5
also be correct?