Strona poświęcona algorytmom

FSO

Samochody

Fabryka Samochodów Osobowych (FSO) produkuje wiele rodzajów samochodów. Każdy samochód posiada następujące atrybuty:

  • cena
  • kolor
  • ciężar

 

Nowe raporty

Z uwagi na duży popyt na nowe samochody zarząd poprosił dział informatyki o nowe raporty. Pilnie potrzebne są następujące raporty:

  1. sumaryczny koszt wszystkich samochodów o tym samym ciężarze
  2. sumaryczny ciężar samochodów o tym samym kolorze

 

Szybkość, liczy się tylko szybkość

Fabryka produkuje kilkaset samochodów na godzinę. Dlatego raporty muszą być generowane bardzo szybko – maksymalnie w czasie N*logN gdzie N to ilość samochodów w zestawieniu.

 

Wejście

W pierwszej linii znajdują się 1 liczba oznaczająca ilość wyprodukowanych aut – ilość aut w zestawieniu

            1 <= liczba_aut <= 500 000 (liczba wyprodukowanych aut)

W kolejnych liczba_aut liniach znajdują się 3 liczby oznaczające następujące informacje o każdym wyprodukowanym samochodzie:

            cena kolor ciezar

gdzie:

            1 <= cena <= 106

            1 <= kolor <= 1015

            10 <= ciezar <= 1014

 

Wyjście

Twój program powinien wypisać następujący raport:

Koszt aut o tym samym ciezarze (tekst)

C – Liczbę oznaczającą ilość różnych ciężarów aut w zestawieniu

C linii uporządkowanych rosnąco względem ciężaru a w każdej linii 2 liczby

            ciezar sumaryczny_koszt_aut_o_tym_ciezarze

Ciezar aut o tym samym kolorze (tekst)

K – Liczbę oznaczającą ilość różnych kolorów aut w zestawieniu

K linii uporządkowanych rosnąco względem koloru a w każdej linii 2 liczby

            kolor sumaryczny_ciezar_aut_o_tym_kolorze

 

Przykład 1

Wejście

5                      (Jest 5 aut w zestawieniu)

2 3 10             (auto nr 1: cena 2, kolor 3, ciężar 10)

5 1 20             (auto nr 2: cena 6, kolor 1, ciężar 20)

6 4 10             (auto nr 3: cena 7, kolor 4, ciężar 10)

1 1 10             (auto nr 4: cena 1, kolor 1, ciężar 10)

9 4 20             (auto nr 5: cena 9, kolor 4, ciężar 20)

Wyjście

Koszt aut o tym samym ciężarze

10 9                (najmniejszy ciężar 10, koszt wszystkich auto o tym ciężarze: 8)

20 14              (ciężar nr 2 to 20, koszt wszystkich auto o tym ciężarze: 5)

Ciezar aut o tym samym kolorze

1 30                (najmniejszy kolor 1, suma ciężarów aut o tym kolorze to 30)

3 10                (kolejny kolor to 3, suma ciężarów aut o tym kolorze to 10)

4 30                (kolejny kolor to 4, suma ciężarów aut o tym kolorze to 30)

 



Dodaj komentarz

Twój adres email nie zostanie opublikowany. Pola, których wypełnienie jest wymagane, są oznaczone symbolem *