Let's consider the following infinite sequence:

0, 1, 1, 2, 3, 5, 8, 13, 12, 7, 10, 8, 9, ...

The 0th element is 0 and the 1st element is 1. The successive elements are defined recursively: each of them is the sum of the separate digits of the two previous elements.

Write int solution(int N) returning the N-th element.

Example: N = 2 → 1.

解法

从 2 迭代到 N，每步把前两项各自的数位和相加。复杂度 O(N · log V)。

def solution(N: int) -> int:
    if N == 0:
        return 0
    if N == 1:
        return 1
    a, b = 0, 1
    for _ in range(2, N + 1):
        s = sum(int(c) for c in str(a)) + sum(int(c) for c in str(b))
        a, b = b, s
    return b

class Solution {
    public int solution(int N) {
        if (N == 0) return 0;
        if (N == 1) return 1;
        int a = 0, b = 1;
        for (int i = 2; i <= N; i++) {
            int s = digitSum(a) + digitSum(b);
            a = b; b = s;
        }
        return b;
    }
    private int digitSum(int x) {
        int s = 0;
        while (x > 0) { s += x % 10; x /= 10; }
        return s;
    }
}

int digitSum(int x) {
 int s = 0;
 while (x > 0) { s += x % 10; x /= 10; }
 return s;
}

int solution(int N) {
 if (N == 0) return 0;
 if (N == 1) return 1;
 int a = 0, b = 1;
 for (int i = 2; i <= N; i++) {
 int s = digitSum(a) + digitSum(b);
 a = b; b = s;
 }
 return b;
}

There is a board with N cells (numbered from 0 to N−1) arranged in a row. The board is described by an array points and a string tokens, both of length N. The K-th letter of tokens is either 'T' or 'E', indicating whether the K-th cell contains a token or is empty.

If the K-th cell contains a token, we score the number of points in points[K]. Additionally, we score another point for every pair of adjacent cells with tokens. What is the total number of points scored?

Examples:

• points = [3,2,1,2,2], tokens = "ETTTE" → 7
• points = [2,2,2,2], tokens = "TTTT" → 11

Constraints

1 ≤ N ≤ 100, 1 ≤ points[i] ≤ 1000, tokens[i] ∈ {E, T}.