Problem A: https://codeforces.net/problemset/problem/954/A

Let's iterate over all characters of the string from left to right (excluding last character). Suppose i is a position of the current element of the string. If si ≠ si + 1, increase answer by 1 and increase i by 2, else just increase i by 1.

Problem B: https://codeforces.net/contest/1095/problem/B

It is easy to see that we always have to remove either minimum or maximum of the array. So we can sort the array and the answer will be min(an−1−a1,an−a2). We also can do it without sort because two minimal and two maximal elements of the array can be found in linear time.

Problem C: https://codeforces.net/contest/961/problem/B

Let's iterate over all i from 1 to n and if ti is equal to 1 then add ai to the some variable res and replace ai with 0. Then answer will be equal to , where can be easily calculated with prefix sums for each i.

Problem D: https://codeforces.net/problemset/problem/225/B

Firstly you should generate all k-bonacci numbers less than n. For k ≤ 32 you can do it straightforward, for bigger k you can see that all k-bonacci numbers less 109 are powers of two only (and 0). So you will have no more then 100 numbers.

Then you should use greedy algo. You should substract from n maximal possible k-bonacci numbers. You should repeat this operation while n is not decomposed. And in the end you will have answer.

Why all numbers will be different? One of possible proves:

F(k, n) = F(k, n - 1) + F(k, n - 2) + ... + F(k, n - k)

F(k, n - 1) = F(k, n - 2) + F(k, n - 3) + ... + F(k, n - k - 1)

You can substract the 2nd equation from the 1st one and you will recieve F(k, n) + F(k, n - k - 1) = 2F(k, n - 1), that equal to 2F(k, n - 1) ≥ F(k, n). This unequation also holds for n ≤ k.

Suppose than greedy also constricted 2 equal numbers F(k, x) in decomposition. But then in virtue of unequation we should take number F(k, x + 1) insead these 2 numbers. Сontradiction.

But you didn't need prove than greedy algo works, you might believe that it works:)