Strona poświęcona algorytmom

Rozwiązanie zadania “Sklep” z 3 etapu I OIG

W tym artykule rozwiążemy zadanie Sklep z 3 etapu I Olimpiady Informatycznej Gimnazjalistów , które można znaleźć poniżej:
         https://szkopul.edu.pl/p/default/problemset/oig/1

 

Zadanie Sklep – Co mamy zrobić?

W zadaniu sklep musimy

  1. podsumować ilość towaru o takim samym numerze
  2. wypisać podsumowanie:
    • numer produktu
    • sumaryczną ilość produktu

Zadanie w takiej postaci jest bardzo proste. Wystarczy w tablicy pod indeksem
         numer_produktu
sumować ilość tego produktu w zestawieniu.

Na końcu zaś wypisać wszystkie wartości które nie są zerami:

  • indeks tablicy (to numer_produktu)
  • wartość tablicy (to sumaryczna ilość produktu)

 

Na czym polega trudność nr 1?

Numer produktu może być nawet 109. Niestety tablica zawierająca 109 liczb – by przechowywać w niej sumaryczną ilość produktu o danym numerze – nie zmieści się nam w pamięci.

Typ int (integer) w C/C++ zajmuje 4 bajty. Czyli byśmy potrzebowali tablicę 109 integer’ów co daje 4GB pamięci – dużo za dużu. W zadaniu jest powiedziane, że możemy wykorzystać 32MB.

Pojawia się inne pytanie:
         Jak jest w ogóle możliwe rozwiązanie zadania?

Otóż numer produktu może być maksymalnie 109, ale produktów jest raptem 106. Czyli spośród miliarda możliwości, na numer produktu wykorzystamy maksymalnie milion liczb.

 

Na czym polega trudność nr 2?

Musimy wypisać numery_produktów oraz sumaryczną ilość produktu w kolejności, w jakiej się pojawiły w raporcie. Czyli jeśli nasz raport (dane wjeściowe) wygląda jak poniżej:

Zadanie sklep z Olimpiady Informatycznej Gimnazjalistów - dane początkowe

to musimy wypisać wynik jak poniżej:

3 (mamy 3 różne produkty)

3 6 (jako pierwszy wystąpił i jako pierwszy wypisujemy produkt nr 3 o łącznej ilości 6)

1 5 (jako drugi wystąpił i jako drugi wypisujemy produkt nr 1 o łącznej ilości 5)

2 9 (jako trzeci wystąpił i jako trzeci wypisujemy produkt nr 2 o łącznej ilości 9)

 

Podsumowanie trudności

Tak więc problemy w tym zadaniu możemy podsumować jako:

  1. Jak pamiętać wartości rozproszone od 1 do 109?
  2. Jak zapamiętać w podsumowaniu pierwsze wystąpienie produktu?
  3. Jak wypisać produkty w podsumowaniu w kolejności ich wystąpienia?

 

Struktura która pomoże

W zapamiętaniu kolejności występowania produktów pomoże nam poniższa struktura języka C++:

 struct typ_produkt {

    int numer_produktu;

    int ilosc;

    int pozycja_poczatkowa;

 };

typ_produkt to nasza nazwa nowego typu w C++, który właśnie zdefiniowaliśmy a który po prostu składa się z 3 integer’ów (liczb całkowitych). Utworzymy 2 tablice tego typu:

Tablica: raport
Wczytamy tu cały raport:

  • numer produktu
  • ilość

oraz dodatkowo

  • pozycję w raporcie

Tablica raport będzie miała 106 elementów więc spokojnie pomieści wszystkie linie raportu oraz wszystkie numery produktów, nawet jak każda z 106  linii raportu będzie mieć inny numer produktu – w ten sposób rozwiązujemy problem a)

Tablica: podsumowanie_produktow

W tablicy podsumowanie_produktow będziemy trzymać tu

  • numer produktu
  • sumaryczną ilość produktu ze wszystkich linii raportu
  • najwcześniejszą linię w której produkt wystąpił w raporcie

Tablica podsumowanie_produktow będzie miała również 106 elementów gdyż każda linia raportu może mieć informacje o innym produkcie.

 

Jak wygląda nasz algorytm?

Nasz algorytm sprowadza się do następujących kroków:

  1. Wczytamy wszystkie linie raportu i zapamiętamy je w tabeli raport
  2. Posortujemy tabelę raport po wartości:
    numer_produktu

    W ten sposób gwarantujemy sobie, że produkty o tym samym numerze będą koło siebie.
    Ale jednocześnie będziemy pamiętać w zmiennej pozycja_poczatkowa, w której linii pojawił się dany wpis w raporcie
  3. Przejdziemy liniowo po całej tablicy raport i dla danego numeru produktu (te same numery produktu są koło siebie po posortowaniu):
    • Zsumujemy łączną ilość produktu o danym numerze
    • Zapamiętamy kiedy pierwszy raz się pojawił (najmniejsza wartość zmiennej pozycja_poczatkowa)
    • Gdy przejrzymy już wszystkie produkty o danym numer_produktu to wpiszemy go do tablicy podsumowanie_produktow czyli wpiszemy:
      • Numer produktu
      • Jego łączną ilość
      • Pierwsze wystąpienie w raporcie (w zmiennej pozycja_poczatkowa)
  4. Posortujemy tabelę podsumowanie_produktow po wartości:
                pozycja_poczatkowa

    W ten sposób tabela podsumowanie_produktow będzie przechowywać produkty w kolejności ich pojawienia się w raporcie – im wcześniej produkt był w raporcie tym ma mniejszy indeks w tabeli podsumowanie_produktow.
  5. Wypiszemy wartości tabeli podsumowanie_produktow:
    1. Numer produktu 
    2. Sumaryczną ilość produktu 

 

Symulacja algorytmu dla przykładowych danych

Prześledźmy działanie algorytmu dla następujących przykładowych danych:

Krok 1 –  wczytanie danych do tabeli raport
Po wczytaniu danych tabela raport będzie miała 5 pozycji:

OIG - posortowany raport

Krok 2 –  posortowanie tabeli raport po polu numer_produktu
Sortując tabelę raport po numerze produktu otrzymamy następująca tabelę:

OIG - rozwiązania zadań

Krok 3 –  podsumowanie produktów o tym samym numerze

Idziemy po kolei po tablicy raport i dla produktów o tym samym numerze:

  1. Sumujemy ich ilość
  2. Pamiętamy najwcześniejszą pozycje w raporcie na której dany produkt wystąpił
  3. Wpisujemy A. oraz B. do tabeli podsumowanie_produktow

Tabela podsumowanie produktów po korkach A. – C. będzie miała poniższe 3 pozycje:

Olimpiada Informatyczna

Krok 4 –  posortowanie tablicy podsumowanie_produktow po początkowej pozycji

W tablicy podsumowanie_produktow mamy

  1. podliczone produkty
  2. pozycje kiedy produkt wystąpił najwcześniej

Teraz wystarczy posortować tablice podsumowanie_produktow po pozycji w raporcie kiedy najwcześniej produkt wystąpił. Otrzymamy wówczas tabelę:

OIG

Krok 5 –  wypisanie wyniku

Teraz wypisujemy zgodnie z poleceniem zadania:

3 (tyle jest produktów w tabeli podsumowanie_produktow)

A następnie idziemy po tablicy podsumowanie_produktow i wypisujemy wartość numer produktu i jego sumaryczną ilość. Wartości te wpiszemy poczynając od produktów które najwcześniej wystąpiłyu w oryginalnym raporcie bo tak posrtowaliśmy naszą tabelę podsumowanie_produktu:

3 6 (jako pierwszy wystąpił i jako pierwszy wypisujemy produkt nr 3 o łącznej ilości 6)

1 5 (jako drugi wystąpił i jako drugi wypisujemy produkt nr 1 o łącznej ilości 5)

2 0 (jako trzeci wystąpił i jako trzeci wypisujemy produkt nr 2 o łącznej ilości 9)

 

Złożoność naszego algorytmu

Niech N to będziemy ilość linii raportu

W naszym algorytmie musimy:

  1. Wczytać N linii do tabeli raport – złożoność:

 O ( N )

  1. Posortować N elementów (trójek liczb) tabeli raport – złożoność sortowania w C++:

O ( N*logN )

  1. Przejść tablicę raport posiadającą max N elementów, policzyć sumę, wpisać dane do tablicy podsumowanie_produktow – zrobimy to liniowo – złożoność:

O ( N )

  1. Posortować max N elementów (trójek liczb) tabeli podsumowanie_produktow – złożoność sortowania w C++:

O ( N*logN )

  1. Wypisać tablicę podsumowanie_produktow zawierającą max N elementów – zrobimy o liniowo – złożoność:

O ( N )

Sumaryczna złożoność to

O ( N + N*logN + N + N*logN + N ) = O (N*logN)

Czyli złożoność algorytmu ze wzrostem danych N wzrasta jak O (N*logN).

 

Zmienne

Zwróćmy uwagę, że wszystkie zmienne mogą być typu int (integer).

Suma ilości produktów nie przekroczy 108.

Nawet gdybyśmy mieli max liczbę linii raportu (równą 106) z jednym tylko produktem, a w każdej linii raportu byłaby maksymalna ilość tego jednego produktu (100), to po zsumowywaniu, tego jednego produktu otrzymujemy:
106 * 100 = 106 * 102 = 108

Wniosek
      Możemy wszędzie używać typu integer w C/C++:
Obejmuje liczby do 2*109

Kod C/C++

Poniżej wzrocowy kod C++ który

  • realizuje powyższy algorytm
  • ma złożonośc O ( N*logN )
  • otrzymuje 100%

———

#include <bits/stdc++.h>

using namespace std;

struct typ_produkt {
   int numer_produktu;
   int ilosc;
   int pozycja_poczatkowa;
};

const int MAX_PRODUKTOW = 1000010;
typ_produkt raport[MAX_PRODUKTOW];
typ_produkt podsumowanie_produktow[MAX_PRODUKTOW];


bool CzyDrugiProduktMaWiekszyNumer (typ_produkt produkt1, typ_produkt produkt2) {
   if (produkt2.numer_produktu > produkt1.numer_produktu)
      return true;
   return false;
}

bool CzyDrugiProduktMaWiekszaPozycjePoczatkowa (typ_produkt produkt1, typ_produkt produkt2) {
   if (produkt2.pozycja_poczatkowa > produkt1.pozycja_poczatkowa)
      return true;
   return false;
}

int main(){
   int liczba_wierszy, liczba_produktow;
   int numer_produktu, suma_produktu, pozycja_poczatkowa;
   int i;

   scanf (" %d", &liczba_wierszy);

   for (i=0; i<liczba_wierszy; ++i) {
      scanf (" %d%d", &(raport[i].numer_produktu), &(raport[i].ilosc) );
      raport[i].pozycja_poczatkowa = i;
   }

   sort (raport, raport+liczba_wierszy, CzyDrugiProduktMaWiekszyNumer);

   liczba_produktow = 0;
   numer_produktu = raport[0].numer_produktu;
   suma_produktu = raport[0].ilosc;
   pozycja_poczatkowa = raport[0].pozycja_poczatkowa;
   for (i=1; i<liczba_wierszy; ++i) {
      if (raport[i].numer_produktu == numer_produktu) {
         suma_produktu += raport[i].ilosc;
         if (pozycja_poczatkowa > raport[i].pozycja_poczatkowa)
            pozycja_poczatkowa = raport[i].pozycja_poczatkowa;
            continue;
         }
      podsumowanie_produktow[liczba_produktow].numer_produktu = numer_produktu;
      podsumowanie_produktow[liczba_produktow].ilosc = suma_produktu;
      podsumowanie_produktow[liczba_produktow].pozycja_poczatkowa = pozycja_poczatkowa;
      ++liczba_produktow;
      numer_produktu = raport[i].numer_produktu;
      suma_produktu = raport[i].ilosc;
      pozycja_poczatkowa = raport[i].pozycja_poczatkowa;
   }
   podsumowanie_produktow[liczba_produktow].numer_produktu = numer_produktu;
   podsumowanie_produktow[liczba_produktow].ilosc = suma_produktu;
   podsumowanie_produktow[liczba_produktow].pozycja_poczatkowa = pozycja_poczatkowa;
   ++liczba_produktow;

   sort (podsumowanie_produktow, podsumowanie_produktow+liczba_produktow, CzyDrugiProduktMaWiekszaPozycjePoczatkowa);

   printf ("%d\n", liczba_produktow );
   for (i=0; i<liczba_produktow; ++i)
      printf ("%d %d\n", podsumowanie_produktow[i].numer_produktu, podsumowanie_produktow[i].ilosc );

   return 0;
}

—–
Wielu rozwiązanych zadań!
Daniel Olkowski

 

 

 



Dodaj komentarz

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