Kryształy
Limit pamięci: 32 MB
Bajtocy opracował proces tworzenia kryształów złożonych z
określonej liczby atomów różnych pierwiastków.
Po latach eksperymentów udało mu się znaleźć formułę, która
opisuje, dla jakiej liczby atomów poszczególnych pierwiastków można
wytworzyć kryształ składający się z tych atomów.
Ciekawi go jak wiele różnych kryształów może otrzymać.
Niech i oznaczają nieujemne liczby całkowite.
Przez oznaczmy wynik wykonania operacji
xor na odpowiadających sobie bitach liczb i .
Wyniki działania operacji xor na bitach to: ,
.
Na przykład, .
Bajtocy zna różnych pierwiastków, ponumerowanych od 1 do .
Dla każdego pierwiastka istnieje górne ograniczenie
na liczbę atomów tego pierwiastka, jaka może być użyta do stworzenia
kryształu.
Utworzenie kryształu, który składa się z atomów -tego
pierwiastka (dla ) jest możliwe tylko, gdy:
Ostatni z powyższych warunków oznacza, że kryształ musi składać
się z przynajmniej jednego atomu.
Zadanie
Napisz program, który:
-
Wczyta ze standardowego wejścia liczbę pierwiastków oraz
ograniczenia na liczbę atomów danego pierwiastka w
krysztale.
-
Wyliczy liczbę różnych kryształów jakie można otrzymać.
-
Wypisze wynik na standardowe wyjście.
Wejście
Pierwszy wiersz standardowego wejścia zawiera liczbę
pierwiastków , . W drugim i ostatnim wierszu
znajduje się liczb pooddzielanych
pojedynczymi odstępami, .
Wyjście
Twój program powinien wypisać na standardowe wyjście jedną
liczbę - liczbę kryształów, które można otrzymać. Możesz
założyć, że liczba ta jest mniejsza od .
Przykład
Dla danych wejściowych:
3
2 1 3
poprawną odpowiedzią jest:
5
Możliwe ilości atomów poszczególnych pierwiastków to:
.
Autor zadania: Jakub Pawlewicz.