Olimpiada de Informatica, 2016Faza locala, clasa a 9-a

Problema 1 cai 100 puncte

Pe un cmp sunt N cai i M crue. Calul i are puterea egal cu pi, iar crua are greutatea egal cu gi. Un cal poate strag cel mult o cru, dar aceasta trebuie s aib greutatea mai mic sau egal cu puterea calului.

Cerin

Determinai numrul maxim de perechi de cai i crue n care caii sunt n stare s trag cruele.

Date de intrare

Pe prima linie a fiierului de intrare cai.in se afl N + 1 numere naturale: N p1 p2 ... pN, separate prin cte un spaiu, cu semnificaia din enun. Pe a doua linie se gsesc, n mod asemntor, M + 1 numere naturale M g1 g2 ... gM, separate prin cte un spaiu.

Date de ieire

n fiierul de ieire cai.out se va afla un singur numr natural, reprezentnd numrul maxim cerut.

Restricii i precizri

1 N, M 10 000

1 pi < 215, i = 1,2,...,N

1 gi < 215, i = 1,2,...,M

Pentru 50% din teste M, N 1000.

Exemplu

cai.in cai.out Explicaie6 3 3 4 4 5 16 3 4 5 2 1 6

5 Perechile (indice cal, indice cru) cuplate sunt:

(1, 1), (2, 4), (3, 2), (5, 3), (6, 5).

Timp maxim de execuie/test: 1 secund/test

Problema 2 var BAC 100 puncte

Cerina:Se consider algoritmul alaturat, descris n pseudocod. S-a notat cu x%y restul mpririinumrului natural x la numrul natural nenul y i cu [z] partea ntreag a numrului real z.

Scriei programul C++ corespunztor algoritmului dat. Programul citeste din fisierul"intrare.in" dou valori (una pentru variabila a i una pentru variabila b, valorile suntseparate printr-un spatiu).

Construiti "intrare.in" cu doua valori care vor fi citite astfel nct, n urma executriialgoritmului, s se afieze valoarea 0 in fisierul "iesire.out".

Timp maxim de executare: 1 secund.

Olimpiada de Informatica, 2016