#2: Sequence Of Powers

Let's take a look at this infinite sequence of powers of ten, starting with the number 1.

110100100010000....

Your task is to write a program that would print the digit in a given position and the digit in the position right next to it. The program should be written to find the digits within a second even with an input integer of 1 000 000 (which means that you would need to look at the millionth digit to print it out).

Example:

Input: 7

Output: 1 0

Explanation: On position 7 and 8 in the sequence (110100100010000...) there are 1 and 0 as digits.

#1: Bowling (largest path sum in a pyramid of numbers)

You have a pyramid or a triangle of numbers like this one. Starting from the top, walking down, going one step to the adjacent number either to right or to the left until you’ve reached the bottom row. Your task is to write a program to find the largest possible sum considering the conditions above. 

3
7 4
2 4 6
8 5 9 3

In this case, the largest sum is 3 + 7 + 4 + 9 = 23.

NOTICE: The program should be written so it can calculate the largest possible sum maximum within 1 second even with a triangle that consists of 100 rows.

-- Example I:

input:

4 // is the number of rows in the triangle

3
7 4
2 4 6
8 5 9 3

output: 

23

-- Example II:

Input:

5

7

3 8

8 1 0

2 7 4 4

4 5 2 6 5

Output: 30