Trojice
Množinu všech přirozených čísel označíme symbolem N. Pro dvě čísla p, r ∈ N, p ≤ r definujme množinu I(p, r) předpisemI(p, r) = {s ∈ N | p ≤ s ≤ r}.
Předpokládejme, že jsou dány dvě konečné neprázdné posloupnosti přirozených čísel A = {a1, a2, ..., an}, B = {b1, b2, ..., bm}. Pro tyto dvě posloupnosti definujeme množinu TROJ(A,B) předpisem
TROJ(A,B) = {(x, y, z) ∈ N3 | 1 ≤ x ≤ n, 1 ≤ y ≤ z ≤ m, ax = ∑k∈I(y, z) bk}.
Úloha
Pro zadané dvě posloupnosti A a B máme určit mohutnost množiny TROJ(A,B).
Vstup
Na vstupu jsou dva řádky. První řádek specifikuje posloupnost A = {a1, a2, ..., an}, druhý řádek specifikuje posloupnost B = {b1, b2, ..., bm}. Oba řádky mají stejný formát. Pro posloupnost A je nejprve uvedena její délka n a poté jsou uvedeny jednotlivé její prvky a1, a2, ..., an v tomto pořadí. Druhý řádek vstupu specifikuje posloupnost B = {b1, b2, ..., bm} analogickým způsobem. Všechny sousední hodnoty v každém řádku jsou navzájem odděleny mezerou. Vstup je zadán korektně, není třeba jej kontrolovat. Pro vstupní hodnoty platí následující omezení:1 ≤ n ≤ 104, 1 ≤ m ≤ 104, všechny hodnoty obou posloupností A a B jsou přirozená čísla nepřesahující 104.
Výstup
Na výstupu je jeden textový řádek s jedním celým číslem představujícím mohutnost množiny TROJ(A,B).Příklad 1
Vstup:11 20 17 86 5 42 5 62 98 7 42 40 14 4 14 14 3 4 1 7 6 3 9 13 1 8 7Výstup:
11Pro pohodlí čtenáře uvádíme v tomto příkladu výčet množiny TROJ(A,B) a jako ilustraci také schématické naznačení jejího vztahu k posloupnostem A a B.
Obr. 1. A = (20, 17, 86, 5, 42, 5, 62, 98, 7, 42, 40), B = (4, 14, 14, 3, 4, 1, 7, 6, 3, 9, 13, 1, 8, 7). TROJ(A,B) = { (2, 3, 4), (2, 6, 9), (4, 5, 6), (6, 5, 6), (8, 4, 14), (9, 4, 5), (9, 7, 7), (9, 14, 14), (11, 1, 6), (11, 6, 12), (11, 8, 13)}. |
Příklad 2
Vstup:3 10 10 10 5 1 2 3 4 6Výstup:
6
Příklad 3
Vstup:4 7 6 5 4 8 1 1 1 1 1 1 1 1Výstup:
14
Příklad 4
Vstup:21 1 2 3 4 6 7 8 12 14 15 16 24 28 30 31 32 48 56 60 62 63 6 1 2 4 8 16 32Výstup:
21