RO Questions
a fost răspuns

Călin este supărat și stă pe o bancă. Prin fața lui trec Q perechi de mașini care o iau pe scurtătură (o pereche este formată din două maşini). Mașinile sunt numerotate de la 1 la N. Valoarea unei mașini este reprezentata de numărul ei. Aceeași mașina poate să treacă de maxim două ori prin fața lui Călin.

Cerința
Ajutați-l pe Călin să aleagă din fiecare pereche câte o maşină, astfel încât suma mașinilor sa fie maximă. De asemenea, Călin vrea să știe câte dubluri a ales.

Date de intrare
Fișierul de intrare masinute.in conține pe prima linie numerele Q , iar pe următoarele Q linii, numerele X și Y reprezentând numerele mașinilor.

Date de ieșire
Fișierul de ieșire masinute.out va conține pe prima linie numărul S, reprezentând suma maxima MOD 666013 și D reprezentând numărul dublurilor.

Restricții și precizări
0 ≤ Q ≤ 1.000.000
numerele din cele Q perechi vor fi mai mici decât 2.000.000.000
O pereche este compusă din două masini.
O dublura înseamnă că alege de două ori aceeași mașină.

Exemplu
masinute.in

2
1 2
3 4
masinute.out

6 0
masinute.in

4
1 1
2 2
3 3
4 4
masinute.out

10 0
masinute.in

2
1 2
1 3
masinute.out

5 0
#1838

Răspuns :

EXPRESSRO
Iti trimit solutia oficiala la aceasta problema. Succes!
#include <fstream>
#include <tr1/unordered_set> /// Includ libraria pentru SET-uri

using namespace std;
using namespace tr1; /// Includ namespace-ul pentru SET-uri

ifstream in("masinute.in");
ofstream out("masinute.out");

unordered_set <int> h; /// Declar setul

int main( )
{
    int Q,dubluri=0,sol=0;
    in >> Q;
    for(int i=1; i<=Q; i++)
    {
        int x,y,maxim;
        in>>x>>y; /// Citesc perechea de numere

        maxim=max(x,y);  /// Aflu cel mai mare numar dintre cele 2 (GREEDY)
        sol=(sol+maxim)%666013; /// Adaug maximul la solutie

        if(h.find(maxim)!=h.end()) /// Caut maximul in SET
            {
                dubluri++; /// Daca il gasesc, maresc numarul de dubluri
            }
        else
            h.insert(maxim); /// Daca nu, il adaug in set

    }
    out<<sol<<" "<<dubluri; /// Afisez solutia
}

Vă mulțumim că ați ales să vizitați platforma noastră dedicată Informatică. Ne bucurăm dacă informațiile oferite v-au fost de ajutor. Pentru orice întrebare sau clarificare suplimentară, echipa noastră vă stă la dispoziție. Revenirea dumneavoastră ne onorează – nu uitați să ne salvați în lista de favorite!


RO Questions: Alte intrebari