matriosca

Olimpiada de Informatic, etapa pe sector

22Februarie 2015

Clasa a VII-a

Problema 2 Complot100 puncteA aprut un zvon cum c, s-a nfiinat o organizaie secret numit Matematica complicat care vrea s schimbe toate operaiile matematice cu unele mult mai complicate. Cum ani buni i-au dat bti de cap i cele pe care le tii acum, nu vrei s se ntmple aa ceva. mpreun cu colegii de clas, afli c organizaia are doi lideri Algebr i Geometrie i nu are niciun sediu, tocmai pentru a nu fi gsii, ntlnirile lor avnd loc n parcul Herstru. Ca s aflai mai multe despre ei, hotri c trebuie s fie urmrii. Cum jumtate din zi suntei la coal, angajai pe cei mai buni detectivi care s stea la cte o intrare n parc i s noteze momentele de timp la care intr i iese fiecare dintre cei doi lideri.Detectivii v predau listele cu plimbrile n parc ale lui Algebr i de asemenea, listele cu plimbrile n parc ale lui Geometrie. Ca s dejucai ct mai repede planurile celor doi, trebuie s calculai voi ct timp au stat cei doi mpreun n parc.

CerineScriei un program care s determine numrul de minute pe care le-au petrecut mpreun Algebr i Geometrie n parc.Date de intrareFiierul complot.in conine informaiile date de detectivi. n prima parte a fiierului sunt enumerate plimbrile lui Algebr dup care cele ale lui Geometrie. Pe prima linie a fiierului va fi scris un numr natural n, reprezentnd de cte ori a intrat i a ieit Algebr din parc. Pe urmtoarele n linii sunt scrise cte dou numere ntregi a i b; a reprezint momentul de timp la care Algebr intr n parc i b reprezint momentul de timp la care Algebr prsete parcul. Pe linia n+2, va fi scris un numr natural m ce reprezint numrul de plimbri n parc ale lui Geometrie. Urmtoarele m linii vor conine cte dou numere ntregi c i d cu aceeai semnificaie; c reprezint momentul de timp la care Geometrie intr n parc i d reprezint momentul de timp la care Geometrie prsete parcul.Date de ieire

Fiierul complot.out conine o singur linie ce conine un singur numr ntreg ce reprezint timpul total pe care Algebr i Geometrie l petrec mpreun n parc. Restricii

0 n 1 000 000 0 m 1 000 000 0 a1 < b1 < a2 < b2 < ... < an < bn 10 000 000 0 c1 < d1 < c2 < d2 < ... < cm < dm 10 000 000 Toate momentele de timp se exprim n minute.Exemplupatrat.inpatrat.outExplicaie

310 20

40 60

85 100

2

15 50

110 12015 Cei doi au stat mpreun n parc ntre minutele 15 i 20 i ntre minutele 40 i 50, deci n total 15 minute

Timp maxim de execuie/test: 0.1 secundeMemorie total disponibil 16 MB din care pentru stiv 4 MB.Dimensiunea maxim a sursei 5 KB.