Sleeping Gyuri

Time limit0.5sMemory limit1024 MB

Summary

Given Gyuri's slow recursive code for a very large N, write a faster function that returns the same value within the time limit.

Level: Medium4 of 10
Topics: Matrix, Math, Divide and conquer
Solved: No attempts yet

Problem

In 2019, students of the Computer Science department at Yonsei University were once again gathering in a seminar room in Songdo to work on their assignments. Gyuri (a freshman at the time) showed up heavily drunk and started the assignment. Too sleepy to continue, Gyuri wrote the code below and fell asleep.

Gyuri's code returns the correct answer. The only problem is that the given $N$ is too large, so it does not finish within the time limit. Watching Gyuri's screen, you decide to fix the code to help poor Gyuri. You must write a function that runs within the time limit and returns the same value as Gyuri's code.

Examples1

Example 1
Input
```
0
```
Expected output
```
0
```