Danciu: Pagină nouă: 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 pasti...

2024-06-04T08:44:27Z

Pagină nouă: 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 pasti...

New page

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>

1236 - Pastile - Revision history