1236 - Pastile

Manole este extrem de răcit. Din această cauză a mers la medicul de familie care l-a sfătuit urmeze un tratament cu N pastile, din care trebuie să ia în fiecare zi câte o jumătate. A cumpărat de la farmacie o cutie în care se aflau exact N pastile, fiecare dintre ele având pe suprafață o dungă care marchează jumătatea ei.

Manole începe să își ia tratamentul și constată că poate proceda doar astfel:

• scoate din cutie o pastilă întreagă din care folosește, în ziua respectivă, doar jumătate din ea, iar jumătatea rămasă o pune înapoi în cutie;
• scoate din cutie o jumătate de pastilă, rămasă din una din zilele anterioare, pe care o folosește în ziua respectivă.

Cerința

Scrieți un program care determină numărul de posibilități în care poate lua toate cele N pastile, procedând după procedeul descris mai sus.

Date de intrare

Fișierul de intrare pastile.in conține pe prima linie numărul natural N.

Date de ieșire

Fișierul de ieșire pastile.out va conține pe prima linie numărul determinat.

Restricții și precizări

• 1 ≤ N ≤ 50.000

Exemplu:

pastile.in

3

pastile.out

5

Explicație

Dacă notăm cu P o pastilă întreagă și cu J o jumătate de pastilă atunci Manole avea 5 posibilități:

P J P J P J

P P J J P J

P J P P J J

P P P J J J

P P J P J J

Rezolvare

def calculate_possibilities(n):
    dp = [0] * (n + 1)  
    dp[1] = 1  

    for i in range(2, n + 1):

        dp[i] = 2 * dp[i - 1]

    return dp[n]

def main():
    with open("pastile.in", "r") as input_file:
        n = int(input_file.readline())

    possibilities = calculate_possibilities(n)

    with open("pastile.out", "w") as output_file:
        output_file.write(str(possibilities))

if __name__ == "__main__":
    main()