Editing 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 <code>N</code> 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 <code>N</code> 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 <code>pastile.in</code> conține pe prima linie numărul natural <code>N</code>.

= Date de ieșire =
Fișierul de ieșire <code>pastile.out</code> va conține pe prima linie numărul determinat.

= Restricții și precizări =

* <code>1 ≤ N ≤ 50.000</code>

= Exemplu: =
<code>pastile.in</code>
 3
<code>pastile.out</code>
 5

=== Explicație ===
Dacă notăm cu <code>P</code> o pastilă întreagă și cu <code>J</code> o jumătate de pastilă atunci Manole avea <code>5</code> posibilități:

<code>P J P J P J</code>

<code>P P J J P J</code>

<code>P J P P J J</code>

<code>P P P J J J</code>

<code>P P J P J J</code>

== Rezolvare ==
<syntaxhighlight lang="python3">
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()

</syntaxhighlight>