###### tags: `ilo`
*MAP 2021*
# Notatki - grupa podstawowa

## 12.06.2021
### Sortowanie za pomocą funkcji sort()
Funkcja `sort()` znajduje się w bibliotece `algorithm`. Sortuje ona elementy z podanego zakresu. Jako pierwszy argument funkcja `sort` przyjmuje wskaźnik (strzałeczkę) na pierwszy element - nazwijmy ten argument *first*, a drugi element to wskaźnik na ostatni element - nazwijmy go *end*.
Sort sortuje zakres \[*first*,*end*\). Trzeci argument jest opcjonalny i jest oznaczaniem funkcji, która kontroluje porządek utrzymywany w trakcie sortowania.

Sortowanie całej tablicy 5-elementowej o nazwie tablica:
sort(tablica, tablica+5);

Sortowanie tylko 3 środkowych elementów powyższej tablicy:
sort(tablica+1, tablica+4);

Sortowanie vectora G:
sort(G.begin(), G.end());

#### Przykład użycia

#include <iostream>
#include <algorithm>
using namespace std;

int tab[5]={8,2,7,1,4};

void wypisz(){
    for(int i=0; i<5; i++){
        cout<<tab[i]<<" ";
    }
    cout<<"\n";
}

bool cmp(int a, int b){
    return a > b;
}

int main(){
    wypisz(); // 8 2 7 1 4
    sort(tab, tab+5);
    wypisz(); // 1 2 4 7 8
    sort(tab, tab+5, cmp);
    wypisz(); // 8 7 4 2 1

    return 0;
}

### Para
Para to mała struktura pozwalająca utrzymywać wygodnie dwa elementy dowolnych typów.

deklaracja:
pair<typ pierwszego elementu, typ drugiego elementu> nazwa;

Do elementów pary dostajemy się za pomocą słów *first* i *second*, które umieszczamy po nazwie pary i kropce.

#### Przykład deklaracji pary

...
    // ↓ tablica, w której trzymamy imiona i wagi naszych królików
    pair<string, int> kroliki[2];
    
    kroliki[0].first  = "Leszek";
    kroliki[0].second = 21;
    kroliki[1].first  = "Pies";
    kroliki[1].second = 37;
    
    // Nadpisywanie pary nową parą:
    kroliki[0] = make_pair("Staszek", 19);
    // można też tak:
    kroliki[1] = {"Patrycja", 11};

## 29.05.2021
### Sumy prefiksowe
Gdy potrzebujemy szybko odpowiadać na zapytania o sumę pewnych wyników na przedziałach (na przykład z tablicy `tab`), możemy użyć do tego tablicy sum prefiksowych.

Wynik w miejscu `x` w tablicy sum prefiksowych oznacza wynik dla tablicy `tab` z przedziału od początku tablicy do `x`.

By uzyskać wynik na przedziale $[a, b]$, wystarczy wziąć wynik z przedziału $[0, b]$ i odjąć od niego wynik z przedziału $[0, a-1]$.

#### Przykład
Powiedz jaka jest suma liczb na zadanym przedziale.

int tab[] = {0,1,2,3,4,5}; //przykładowa tablica
//indeksy:   0,1,2,3,4,5

int sumy[5]; //tablica sum prefiksowych

//uzupełnijmy tablicę sum prefiksowych
for(int i=1; i<5; i++){
    sumy[i] = sumy[i+1] + tab[i];
}

//odpowiadamy na pytania
// [2, 5]
tab[5]-tab[2-1];
// [1, 2]
tab[2];
tab[2]-tab[1-1];

//lub ogólniej
//[a, b]
tab[b]-tab[a-1];

### Tablica
https://miro.com/app/board/o9J_lBslUk0=/
<iframe width="768" height="432" src="https://miro.com/app/live-embed/o9J_lBslUk0=/?moveToViewport=-696,-346,2133,1045" frameBorder="0" scrolling="no" allowFullScreen></iframe>

## 15.05.2021
Przykłady z wyszukiwaniem binarnym:
### Przykład 1
Grasz z drugą osobą w *Zgadnij liczbę*. Osoba ta myśli liczbę od 1 do $n$, a Ty musisz zgadnąć co to za liczba. Możesz zadawać osobie pytania, na które może odpowiadać tylko TAK/NIE. Dodatkowo chcesz być pewn_, że nie zadasz więcej niż $\lceil log_2(n)\rceil$ pytań.

def binary_search(start, koniec):
    lewy = start - 1
    prawy = koniec + 1
    
    while lewy + 1 < prawy:
        srodek = (lewy+prawy)/2
        if <czy środek jest >= od pomyślanej liczby?>:
            prawy = srodek
        else:
            lewy = srodek
            
    return <Ta liczba to prawy>
    

def main():
    p = 1
    n = <osoba mówi jaka jest maksymalna liczba>
    
    print("Twoja liczba to:", binary_search(p, n))

### Przykład 2
Franek ma swoim domu hodowlę królików - ma ich bardzo dużo! Weterynarz kazał mu co jakiś czas przyjeżdzać na kontrolę z pierwszym królikiem o wadze mniejszej niż $x$. Pomóż Frankowi szybko dowiadywać się z którym królikiem powinien jechać na kontrolę zdrowia.

*Wejście*
Dostajesz $n$ - liczbę królików, a następnie w $n$ liniach pary $w, p$, gdzie $w$ ($0<w\leq10^9$) to waga królika, a $p$ to jego imię. Króliki podawane są w kolejności rosnącej wag. Następnie na wejściu pojawia się liczba $q$, a po niej $q$ zapytań z jedną liczbą $x$.

*Wyjście*
Twoim zadaniem jest wypisanie $q$ wierszy, w każdym należy wypisać imię pierwszego lżejszego niż $x$ królika. Jeśli nie ma takiego królika, należy wypisać pusty napis.

*Przykładowe wejście*

5
13 Jan
9 Jola
12 Joachim
3 Jurek
7 Joanna
3
10
2
15

*Przykładowe wyjście*

Jola

Jan

#### Rozwiązanie przykładu 2

#include <iostream>
#include <string>
using namespace std;

int n;
int wagi[1000002];
string imiona[1000002];

string bs(int x){
    int lewy = 0;
    int prawy = n+1;
    
    while(lewy+1<prawy){
        int srodek = (lewy+prawy)/2;
        
        if( wagi[srodek] >= x ){
            prawy = srodek;
        }else{
            lewy = srodek;
        }
    }
    
    return imiona[lewy];
}


int main(){
    int q,x;
    cin>>n;
    

    for(int i=1; i<=n; i++){
        cin>>wagi[i]>>imiona[i];
    }
    
    cin>>q;
    
    for(int i=0; i<q; i++){
        cin>>x;
        cout<<bs(x)<<"\n";
    }
    
    return 0;
}

### Tablica
https://miro.com/app/board/o9J_lEMdokI=/
<iframe width="768" height="432" src="https://miro.com/app/live-embed/o9J_lEMdokI=/?moveToViewport=-1248,-452,4210,2054" frameBorder="0" scrolling="no" allowFullScreen></iframe>

## 07.05.21

### Własności wykorzystywane przy algorytmie Euklidesa
$$
nwd(a,0) = a\\
nwd(a,b) = nwd(b, a-b) \text{ dla } a>b\\
nwd(a,b) = nwd(b, a\ mod\ b)\\
$$

[Więcej o NWD (wiki)](https://pl.wikipedia.org/wiki/Najwi%C4%99kszy_wsp%C3%B3lny_dzielnik#Za_pomoc%C4%85_algorytmu_Euklidesa)
[Więcej o NWW (wiki)](https://pl.wikipedia.org/wiki/Najmniejsza_wsp%C3%B3lna_wielokrotno%C5%9B%C4%87#Algorytmy_wyznaczania_NWW)

### Przydatne informacje
1. Typ `int` ma 4 bajty = 32 bity.
2. W zmiennej typu `int` możemy trzymać liczby od $-2^{31}$ (~ -2mld.) do $2^{31}-1$ (~ 2 mld.)
[→ Więcej informacji o typach ←](http://cpp0x.pl/kursy/Kurs-C++/Poziom-1/Pojecie-zmiennej-i-podstawowe-typy-danych/11)
3. Komputerowi wykonanie $10^8$ operacji zajmuje ok. 1 sekundy.
4. Trzeba pamiętać, że gdy nie przypisujemy wartości danej komórce pamięci, to znajduje się tam losowa wartość (tak jak znak zapytania w maszynie RAM).
5. Zadania na Themisie i na konkursach często mają limit pamięci. Jednym z przeliczników, które warto znać jest ten, że tablica miliona intów ma rozmiar 4MB.
6. Deklarując tablicę musimy pamiętać o jej odpowiedniej wielkości. Nie możemy jako programiści dopuścić do zaglądania w "nie naszą pamięć". Np. próba odczytu lub zapisu do komórki spoza tablicy, w zadaniu na Themisie, np. tab\[-1\], lub tab\[10\] (dla tablicy 10 elementowej), zakończy się odpowiednim błędem.
7. Próba zapisu liczby o typie innym niż zmienna do której zapisujemy, nie zakończy się błędem. Program wykona swoje zadanie, odpowiednio ucinając liczbę, lub modyfikując ją w inny sposób.
Np. `cout<<(int)(3.5);` wypisze liczbę 3.

### Tablica
https://miro.com/app/board/o9J_lF6SJLk=/
<iframe width="768" height="432" src="https://miro.com/app/live-embed/o9J_lF6SJLk=/?moveToViewport=-1058,734,2996,1462" frameBorder="0" scrolling="no" allowFullScreen></iframe>