COCI '13 Contest 3 #1 Riječi

View as PDF
Submit solution
Points: 5 (partial)
Time limit: 1.0s
Memory limit: 32M
Problem type

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 K 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 K (1 \le K \le 45), 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 20\% of total points, K will be less or equal to 10.

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


  • 0
    tiantian2012  commented on March 26, 2025, 7:30 p.m.

    Think about the way a's and b's tranform that changes the number of each letter.


  • -1
    nathanxrichards  commented on Oct. 30, 2024, 7:59 a.m.

    Thanks for the hint!

    This is the first time where making the code efficient was needed to solve the problem


  • 1
    yastrebdev  commented on Sept. 3, 2024, 8:43 a.m.

    Hint: there is a connection with the Fibonacci sequence


  • -2
    master114  commented on Aug. 21, 2024, 6:46 a.m. ← edited

    Use only counters, without strings and lists

    Python3 Resources: 0,414s, 10.72 MB Maximum single-case runtime: 0,032s Final score: 10/10 (5.0/5 points)


  • 0
    OkeeMacaroni  commented on Aug. 14, 2024, 7:26 p.m. ← edited

    Had the right solution, but a few test cases timed out. Any idea on how to help the website process things faster?


    • -1
      alexander_john  commented on Sept. 27, 2024, 4:42 a.m.

      Study the correlation between the fibonacci sequence and the problem