Addition chains

All submissions for this problem are available.
An addition chain for a positive integer N is a sequence of positive integers C = (A_{0}, A_{1}, ..., A_{L}) such that
 1 = A_{0} < A_{1} < ... < A_{L – 1} < A_{L} = N,
 for each i such that 1 ≤ i ≤ L there exist integers j and k such that 0 ≤ j, k < i and A_{i} = A_{j} + A_{k}.
The integer L is called the length of the chain C.
For example, C = (1, 2, 3, 6, 12, 15) is an addition chain of length 5 for N = 15. Indeed,
A_{0} = 1,
A_{1} = 2 = 1 + 1 = A_{0} + A_{0},
A_{2} = 3 = 2 + 1 = A_{1} + A_{0},
A_{3} = 6 = 3 + 3 = A_{2} + A_{2},
A_{4} = 12 = 6 + 6 = A_{3} + A_{3},
A_{5} = 15 = 3 + 12 = A_{2} + A_{4}.
It is, in fact, the shortest addition chain for N = 15.
Your task is to find some addition chain for a given positive integer N.
The shorter chain you will find the better score you will get.
Input
The only line of the input file contains an integer N, the number for which you need to find an addition chain.
Output
The first line of the output file should contain an integer L ≤ 500, the length of your addition chain for the value of N given in the input file. L lines should follow. i^{th} line should contain two nonnegative integers j[i] and k[i] both less than i separated by exactly one space. Their meaning is that for your addition chain, A_{i} is equal to A_{j[i]} + A_{k[i]}. More specifically, your output will be considered as correct if and only if all of the following conditions hold:
 1 ≤ L ≤ 500;
 0 ≤ j[i], k[i] < i for all i such that 1 ≤ i ≤ L;
 for the sequence (A_{0}, A_{1}, ..., A_{L}) defined by the rules A_{0} = 1 and A_{i} = A_{j[i]} + A_{k[i]} for i = 1, 2, ..., L we have 1 = A_{0} < A_{1} < ... < A_{L – 1} < A_{L} = N.
Your program will get Accepted if and only if it returns correct output for each test case within a given time limit.
Scoring
Your score for a test file is the length of your addition chain, that is, an integer L. The total score for a submission is the average score across all test files. Your goal is to minimize the total score.
Constraints
1 < N < 10^{100}
Example
Input: 15 Output: 6 0 0 1 0 2 0 0 3 4 4 4 5
Explanation
Sample output represents an addition chain (1, 2, 3, 4, 5, 10, 15) for N = 15. Your score for such output will be 6. Note that according to the problem statement shorter chain is possible for this value of N but you don't need to find the shortest chain since this is a challenge problem. Also note that order in which we write numbers j[i] and k[i] for the given i doesn't matter.
Test Generation
Values of N are generated using different strategies. There are 50 official test files in all. Among them there are 8 files where N < 100000, 5 files where N is a random decimal string of the length 100 (that is, each digit of N is distributed uniformly in the range [0, 9] except the first digit which is distributed in the range [1, 9]), 8 files where binary representation of N is a random string of the random length from 300 to 332 (that is, at first an integer L is chosen randomly in the range [300, 332] and then L digits d_{1}, d_{2}, ..., d_{L} are chosen so that d_{1} = 1 and each d_{i}, 2 ≤ i ≤ L, is uniformly distributed in the range [0, 1]. After that N is set to d_{1} ∙ 2^{L1} + d_{2} ∙ 2^{L2} + ... + d_{L1} ∙ 2 + d_{L}, that is, d_{1}d_{2}...d_{L} is the binary representation of N). Other 29 files generated using some special strategies which we prefer to keep in secret.
Author:  anton_lunyov 
Tester:  laycurse 
Editorial  http://discuss.codechef.com/problems/ADDCHAIN 
Tags  anton_lunyov, challenge, july12 
Date Added:  11062012 
Time Limit:  0.19467 sec 
Source Limit:  50000 Bytes 
Languages:  C, JAVA, PYTH, PYTH 3.6, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions