### PROBLEM LINKS

### DIFFICULTY

EASY

### EXPLANATION

This problem may look scary at first to someone who haven’t seen electrical resistors before, but the basic things needed to solve are explained in the problem statement. Seeing the figures for N = 1, 2 and the low constraint on N, hints a recursive ( or iterative ) approach. Suppose we have found the resistance at the left ends of a circuit with (N-1) blocks, say P. Adding one more block at its left ends means, the horizontal Resistor (R=1) and P are in series and so Q = 1 + P, and the vertical resistor (R=1) and Q are in parallel, so the equivalent resistance is (1xQ)/(1+Q). We need to find the numerator and denominator, so we maintain them separately and update. What about reducing to lowest terms, modulo ?

Lets check the answers for N = 1, 2, 3, 4, … its 1/1 , 2/3 , 5/8, 13/21, … whoa! its fibonacci numbers If for circuit with (N-1) blocks the answer is A/B, then for N blocks its (1+A/B) / (1+1+A/B) = (A+B) / (B + (A+B)) and so the fibonacci series. Considering F(n) as the nth fibonacci number and F(0) = 0, F(1) = 1 the answer we need is simply F(2n-1) / F(2n). Also, we need not worry about reducing to lowest terms, as the gcd of two adjacent fibonacci numbers = 1 ( try euclidean method !) This can be solved now using a simple iteration in time O(n). There is a O(log n) method using matrix exponentiation, but its not needed here, as the constraints are small.

### SETTER’S SOLUTION

Can be found here.

### TESTER’S SOLUTION

Can be found here.