PEG Test - December 2014

Problem C: Assembly Elves

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 N stations (numbered from 1 to N) in the North Pole assembly line. Each station is meant to continuously produce an unlimited amount of a particular type of unit. Specifically, station i produces type-T_i units.

Station one produces elementary units (type-1 units), so T₁ = 1. From thereon, a station i can only produce a unit of type-T_i if T_i 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 1, 2, 3, and 5. The elf at station two can make type-2 units because it can take two of station one's units and put them together (1 + 1). The elf at station three can make type-3 units because it can take one of station one's units and one of station two's units (1 + 2). The elf at station four can make type-5 units because it can put together one of station two's units and one of station three's units (2 + 3).

Santa wants to make type-X 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 Format

A single integer X (1 ≤ X ≤ 100), the type of toy that Santa wants to produce.

Output Format

Line 1 should contain a single integer N specifying the length of the shortest possible production line that produces the specified toy.
Line 2 should contain N space-separated integers, the values of T₁, T₂, …, T_N, representing the types of units being produced in each assembly line station.

Sample Input

5

Sample Output

4
1 2 3 5

All Submissions
Best Solutions

Point Value: 10 (partial)
Time Limit: 2.00s
Memory Limit: 16M
Added: Dec 13, 2014
Author: Alex

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)

Is there any reason 1 2 4 5 is invalid? Or is it valid and was simply not chosen?
In the case that it is valid, how do I decide which to output?

Any correct answer will be accepted.