Sum Of Ones

Cho một mảng số nguyên ban đầu chỉ có 1 phần tử n. Với mỗi phần tử x trong mảng, nếu x>1, thay thế x bằng 3 phần tử liên tiếp x/2, x%2, x/2 vào vị trí của x trong mảng (x/2 là phép chia lấy phần nguyên, x%2 là phép chia lấy phần dư). Mảng cuối cùng chỉ chứa các phần tử 0 hoặc 1.

Hãy đếm số số 1 trong khoảng [l, r] của mảng ở trạng thái cuối cùng. (đếm từ 1)

Ví dụ:

• Cho n = 7, l = 2, r = 5, trạng thái của mảng lần lượt là [7] -> [3,1,3] -> [1,1,1,1,3] -> [1,1,1,1,1,1,1]. Từ vị trí thứ 2 đến vị trí thứ 5 có 4 số 1. Vậy nên, sumOfOnes(7,2,5) = 4
• Cho n = 10, l = 3, r = 10, trạng thái cuối cùng của mảng là [1,0,1,1,1,0,1,0,1,0,1,1,1,0,1]. sumOfOnes(10,3,10) = 5

Đầu vào/Đầu ra:

• [Giới hạn thời gian chạy] 0.5s với C++, 3s với Java và C#, 4s với Python, JS và Go
• [Đầu vào] Integer n.
  0 <= n < 250
• [Đầu vào] Integer l, Integer r
  1 <= l <= r <= số phần tử dãy cuối cùng
• [Đầu ra] Integer res 
  • Số số 1 trong khoảng [l, r] của dãy cuối cùng