1st Balkan Olympiad on Informatics
Constantza, Romania, 24-29 May 1993

Day 1 - Problem 3 (30 points)

A sequence of positive integers a₁,a₂,...,a_n is called "additive chain" of length n if for every k, 1 < k <= n, there exists indices i and j (1 <=i <=j <= n), so that a_k=a_i+a_j. Write a program that, for a₁=1 and the last element read from input, finds out an additive chain with minimal length.

Example The sequence 1,2,4 is an additive chain of length 3.