E.pdf

(158 KB) Pobierz

Problem E

Trójkąt Pascala

I OTWARTE MISTRZOSTWA OPOLA W PROGRAMOWANIU ZESPOŁOWYM

Trójkąt Pascala tworzą wiersze zawierające liczby całkowite. NajwyŜszy wiersz zawiera jed-

ną liczbę 1. KaŜdy następny wiersz zawiera o jedną liczbę więcej niŜ poprzedni i jest tworzo-

ny według następujących reguł:

•

pierwsza i ostatnia wartość jest równa 1;

•

na pozostałych pozycjach są sumy dwóch wartości leŜących powyŜej nich.

Oto pierwsze 7 wierszy trójkąta Pascala:

Trójkąt Pascala jest nieskończony i zawiera nieograniczoną liczbę jedynek. Inne wartości

występują w trójkącie skończoną liczbę razy.

Zadanie

Napisz program, który dla danej liczby całkowitej

≥

2 wyznacza liczbę wartości w trójkącie

Pascala większych od 1 i nie przekraczających

Wejście

Twój program będzie sprawdzany przy pomocy zestawu wielu testów. Pierwszy wiersz wej-

ścia

zawiera jedną liczbę całkowitą

reprezentującą liczbę testów (1

≤

2000). KaŜdy z

kolejnych

wierszy zawiera jedną liczbę całkowitą

≤

). Dane mają być odczy-

tywane ze standardowego wejścia.

Wyjście

Dla kaŜdego przypadku testowego program ma wyprowadzić na standardowe wyjście poje-

dynczy wiersz zawierający liczbę całkowitą określającą ile w trójkącie Pascala jest liczb róŜ-

nych od 1 i nieprzekraczających

Przykład

Dla danych wejściowych:

prawidłowy wynik to: