###### tags: `xivlo`

# Zajęcia 21.04.2021

## Zadanie "Domino Jasia"
Liczby na kostce traktujemy jak wierzchołki w grafie, a samą kostkę jako połączenie między nimi.

Po wczytaniu krawędzi i tym samym stworzeniu grafu, możemy uruchomić dowolny algorytm przeszukiwania DFS/BFS od wierzchołka `p` i sprawdzić czy dotarł on do wierzchołka `k`.

Odpowiedź na pytanie czy istnieje droga między pechową liczbą `p`, a szczęśliwą `k`, możemy uzyskać także rozwiązując nasze zadanie za pomocą algorytmu wyznaczania MST. Jeśli użyjemy Union(x,y) na wszystkich kostkach domina [x|y], to dostaniemy spójne zbiory wierzchołków. Jest droga od `p` do `k`, jeśli oba te wierzchołki znajdują się w jednym zbiorze.

#### *ROZWIĄZANIE ZADANIA*
:::spoiler

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

vector<int> G[10004];
bool vis[10004];
int k;

void dfs(int v){
    if(v==k){
        cout<<"TAK\n";
        exit(0);
    }
    vis[v]=true;
    for(int s: G[v]){
        if(!vis[s]){
            dfs(s);
        }
    }
}

int main()
{
    int p,m,a,b;
    cin>>p>>k>>m;
    for(int i=0; i<m; i++){
        cin>>a>>b;
        G[a].push_back(b);
        G[b].push_back(a);
    }
    dfs(p);
    cout<<"NIE\n";

    return 0;
}

:::

## Zadanie "Długie wakacje"
Tak jak powiedzieliśmy sobie w trakcie omówienia na lekcji, to zadanie może być w prosty sposób rozwiązane zachłannie.

Będziemy wybierać(zliczać) po kolei wycieczki na które może pojechać Jasiu, w kolejności terminu ich zakończenia. Gdyż jeśli wycieczka zakończyła się w dniu x to ma maksymalnie x dni długości. Możliwie krótkie i wcześnie kończące się wycieczki, będziemy zatem rozpatrywać najpierw i to jest własność, która jest dla nas porządana.

#### *ROZWIĄZANIE ZADANIA*
:::spoiler

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

pair<int, int> p[100003];

int main()
{
    int n;
    cin>>n;
    
    for(int i=0; i<n; i++){
        cin>>p[i].second>>p[i].first;
    }
    
    sort(p, p+n);
    
    int ile=1;
    int ost=0;
    for(int i=1; i<n; i++){
        if(p[i].second > p[ost].first){
            ile++;
            ost=i;
        }
    }
    
    cout<<ile<<"\n";

    return 0;
}

:::

## Zadanie "Jednowymiarowe rzutki"
Zadanie to proste wyszukiwanie binarne.

Przypomnę koncept wyszukiwania binarnego na dwóch prostych przykładach.
### 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ę. 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 <algorithm>
#include <iostream>
#include <string>
#include <vector>
using namespace std;

int n;
vector < pair<int, string> > kroliki;

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


int main(){
    int p,w,q,x;
    cin>>n;
    
    kroliki.push_back({0,""});
    for(int i=1; i<=n; i++){
        cin>>w>>p;
        kroliki.push_back({w,p});
    }
    
    sort(kroliki.begin(), kroliki.end());
    
    cin>>q;
    
    for(int i=0; i<q; i++){
        cin>>x;
        cout<<bs(x)<<"\n";
    }
    
    return 0;
}

#### *ROZWIĄZANIE ZADANIA*
:::spoiler

#include <iostream>
#include <algorithm>
// ↓ Definiuję sobie skrócone nazwy, by kod był czytelniejszy
#define fst first
#define snd second
using namespace std;

// tablica na nasze przedziały ((od, do), wartość)
pair< pair<int,int>, long long> przedzialy[100005];
int n;

// wyszukiwanie binarne przedziału
long long int bs(int x){
    // jako przedziały skrajne, wybieram te które oznaczają
    // wartości mniejesze od najbardziej skrajnej pary z 'lewej strony'
    // i analogicznie większe od najbardziej skrajnej pary z 'prawej strony'
    // tablicy przedziałów
    int l=0;
    int p=n+1;
    while(l+1<p){
        int s=(l+p)/2;
        if(x >= przedzialy[s].fst.fst && x <= przedzialy[s].fst.snd)
            // znalazłem przedział w którym zawiera się x
            return przedzialy[s].snd;
        if(x >= przedzialy[s].fst.snd){
            l=s;
        }else{
            p=s;
        }
    }
    // po wyjściu z pętli mam dwóch kandydatów na rozwiązanie - l i p
    
    // sprawdzam czy x zawiera się w l
    if (l != 0 && x >= przedzialy[l].fst.fst && x <= przedzialy[l].fst.snd)
        return przedzialy[l].snd;
        
    // sprawdzam czy x zawiera się w p
    if (p != n+1 && x >= przedzialy[p].fst.fst && x <= przedzialy[p].fst.snd)
        return przedzialy[p].snd;
        
    // teraz już wiem, że trafiono w miejsce spoza przedziałów z punktami 
    return 0;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int q,t;
    cin>>n;
    for(int i=1; i<=n; i++){
        cin>>przedzialy[i].fst.fst>>przedzialy[i].fst.snd>>przedzialy[i].snd;
    }
    sort(przedzialy+1, przedzialy+n+1);

    cin>>q;
    for(int i=0; i<q; i++){
        cin>>t;
        cout<<bs(t)<<"\n";
    }


    return 0;
}

:::