English
Zobacz więcej:
- dla uczniów szkół podstawowych: oij.edu.pl/start/
- dla uczniów szkół średnich: oi.edu.pl/l/jak_zaczac/
Zadanie Przyspieszenie algorytmu (prz)
Przyspieszenie algorytmu
Limit pamięci: 64 MB
Bajtazar musi za karę obliczyć pewną paskudną i tajemniczą funkcję logiczną
, która dla dwóch ciągów liczb naturalnych
,\ 
jest zdefiniowana w następujący sposób:
boolean 
then return 
else if
then return 
else return
.
W powyższym zapisie:
-
oznacza zbiór złożony ze wszystkich liczb ciągu 
(ignorujemy powtórzenia i kolejność liczb),
-
jest najdłuższym prefiksem (początkowym fragmentem) ciągu 
,
dla którego 
,
-
jest najdłuższym sufiksem (końcowym fragmentem) ciągu 
,
dla którego 
,
-
oznacza koniunkcję logiczną, 
- prawdę, 
- fałsz,
a 
- liczność zbioru 
.
mamy:
Dla bardzo dużych danych program obliczający funkcję bezpośrednio z definicji jest
zdecydowanie zbyt wolny.
Twoim zadaniem jest jak największe przyspieszenie obliczania tej funkcji.
Napisz program, który
wczyta ze standardowego wejścia kilka par ciągów 
i
wypisze na standardowe wyjście wartości 
dla każdej pary
wczytanych ciągów.
Wejście
Pierwszy wiersz wejścia zawiera jedną
liczbę całkowitą 
(
), oznaczającą liczbę par ciągów do przeanalizowania.
Kolejne 
wierszy zawiera opisy przypadków testowych.
Pierwszy wiersz każdego opisu zawiera dwie liczby całkowite 
oraz 
(
), oddzielone pojedynczym odstępem i oznaczające
długości pierwszego i drugiego ciągu.
Drugi wiersz zawiera 
liczb całkowitych 
(
),
pooddzielanych pojedynczymi odstępami i opisujących ciąg 
.
Trzeci wiersz zawiera 
liczb całkowitych 
(
),
pooddzielanych pojedynczymi odstępami i opisujących ciąg 
.
Wyjście
Wyjście powinno się składać z 
wierszy; 
-ty wiersz (dla 
)
powinien zawierać jedną liczbę całkowitą - 0 lub 1 -
oznaczającą wartość wyrażenia 
dla 
-tego przypadku testowego.
Przykład
Dla danych wejściowych:
2 4 5 3 1 2 1 1 3 1 2 1 7 7 1 1 2 1 2 1 3 1 1 2 1 3 1 3
poprawną odpowiedzią jest:
0 1
Autorzy zadania: Jakub Radoszewski, Wojciech Rytter.