In what concerns the continuous evaluation solving exercises grade during the semester, you should submit until 23:59 of December 7th
(this exercise will still be available for submission after that deadline, but without counting towards your grade)
[to understand the context of this problem, you should read the class #08 exercise sheet]


In this problem you should submit a function as described. Inside the function do not print anything that was not asked!

[IP084] Dracarys!

Daenerys Targaryen, the Mother of Dragons, has tasked you with a perilous challenge. She wants to know how many occurrences of the letter 'A' appear between two given positions of the White Rabbit game. She will only spare you from the wrath of her dragons if you can solve this puzzle efficiently. Failure to do so will result in her commanding Drogon to unleash Dracarys upon you.

Recall the rules of the game. You start with an 'A' and then:

The first lines of the game are:

A
AB
ABA
ABAAB
ABAABABA
ABAABABAABAAB
ABAABABAABAABABAABABA

The Problem

Write a function count_range(a,b) that given two integers a and b, returns the number of 'A's that appear between positions [a,b] (inclusive) on the word game.

For instance, count_range(3,10) should return 5:

ABAABABAABAABABAABABA

And count_range(2,19) should return 11:

ABAABABAABAABABAABABA

Constraints

The following limits are guaranteed in all the test cases that will be given to your program:

1 ≤ a ≤ b ≤ 1030       positions of the range

NOTE: the limits are really high and you must have an efficient solution that can compute this very quickly.
Your program will need to be able to answer around five hundred queries in less than one second.


Example Function Calls Example Output
print(count_range(3,10))
print(count_range(2,19))
print(count_range(42,297))
5
11
159

Introduction to Programming (CC1024)
DCC/FCUP - University of Porto