One day, little Mirko came across a funny looking machine! It consisted of a very very large screen and a single button. When he found the machine, the screen displayed only the letter A
. After he pressed the button, the letter changed to B
. The next few times he pressed the button, the word transformed from B
to BA
, then to BAB
, then to BABBA
. When he saw this, Mirko realized that the machine alters the word in a way that all the letters B
get transformed to BA
and all the letters A
get transformed to B
.
Amused by the machine, Mirko asked you a very difficult question! After times of pressing the button, how much letters
A
and how much letters B
will be displayed on the screen?
Input Specification
The first line of input contains the integer
, the number of times Mirko pressed the button.
Output Specification
The first and only line of output must contain two space-separated integers, the number of letters A
and the number of letters B
.
Scoring
In test data worth of total points,
will be less or equal to
.
Sample Input 1
1
Sample Output 1
0 1
Sample Input 2
4
Sample Output 2
2 3
Sample Input 3
10
Sample Output 3
34 55
Comments
The last three test cases i didn't pass the time limit. How can I improve my speed? thanks
the editorial helped. got it.
I have been struggling with this one for two days. I can't figure out how to track the updates to the letters correctly.
Don't track them. At every iteration parse the string to count how many of 'A', 'B', and 'AB', you have. Then, create the next string, etc etc. But, this is not the best way to do this exercise. Instead, write down how many As and Bs you get at every iteration and you'll see a pattern emerge.
Thank you for the tip. After reading this it took me little more than 5 minutes to resolve it.
The memory limit of 32M is insufficient if you try to generate the entire sequence of 'A's and 'B's in the test cases 9-11, at least in python. So instead of generating the sequence and then counting As and Bs, you might try counting the letters directly without generating the whole sequence of characters... Fibo, anyone? ;-)