Zgadywanka
Limit pamięci: 32 MB
Bajtazar gra z Bajtonim w następującą grę. Bajtoni losuje sobie ciąg składający
się z 0 i 1 o długości cyfr. Zadaniem Bajtazara jest
odgadnięcie ciągu, który wylosował Bajtoni. W tym celu może zadawać pytania
typu: "Czy suma wyrazów ciągu od -tego do -tego jest parzysta?".
Bajtoni chętnie udzielał odpowiedzi, jednak po pewnym czasie Bajtazar zaczął
podejrzewać, że jego kolega oszukuje. Chciałby sprawdzić kiedy Bajtoni udzielił
pierwszej odpowiedzi sprzecznej z poprzednimi, dlatego zwrócił się do Ciebie o
pomoc.
Zadanie
Napisz program, który:
- wczyta opis pytań zadawanych przez Bajtazara oraz odpowiedzi Bajtoniego,
- obliczy największe takie , dla którego odpowiedzi Bajtoniego na pierwszych pytań są niesprzeczne,
- wypisze wynik na standardowe wyjcie.
Wejście
W pierwszym wierszu standardowego wejścia znajduje się jedna
liczba całkowita (), oznaczajca liczbę pytań
Bajtazara. Każdy z kolejnych wierszy zawiera opis jednego pytania Bajtazara
oraz odpowiedzi Bajtoniego w postaci trzech liczb całkowitych ,
i (). Liczy i
oznaczają, że Bajtazar zapytał o sumę wyrazów ciągu od -tego do -tego
włącznie. Jeśli , to Bajtoni odpowiedział, że suma ta jest parzysta.
Jeśli , Bajtoni powiedział, że suma jest nieparzysta.
Wyjście
Twój program powinien wypisać w pierwszym i jedynym wierszu standardowego
wyjścia jedną liczbę całkowitą - największe takie , dla którego odpowiedzi
Bajtoniego na pierwszych pytań są niesprzeczne.
Przykład
Dla danych wejściowych:
5
3 3 0
2 5 1
1 4 0
2 5 0
1 5 1
poprawną odpowiedzią jest:
3
Autor zadania: Jakub Łącki (zapożyczenie).