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

Day 1 - Problem 3 (30 points)

A sequence of positive integers a1,a2,...,an 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 ak=ai+aj. Write a program that, for a1=1 and the last element read from input, finds out an additive chain with minimal length.

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