---
title: 'Opis poprawności rozwiązań i testy'
---

Opis poprawności rozwiązań i testy
===

## Spis treści

[TOC]

## Budowa płotu
Aby możliwie najmniejszym kosztem wybudować płot należy wyznaczyć otoczkę wypukłą.

### Dowód poprawności
Do wyznaczenia otoczki wypukłej został użyty algorytm Jarvisa.
Algorytm Jarvisa działa w czasie O(kn);
* n - liczba punktów,
* k - liczba punktów należących do otoczki.

Algorytm Jarvisa działa na zasadzie „zawijania” punktów, zaczynając od punktu skrajnego i iteracyjnie wybierając kolejny punkt, który jest najbardziej na zewnątrz względem aktualnego punktu i wszystkich pozostałych punktów. Bazując na aktualnym punkcie szuka pośród pozostałych punktów takiego, który jest najbardziej “na prawo” od niego, tj. ma największy kąt dodatni. Robimy to, aż nie dojdziemy tym sposobem do punktu z którego zaczynaliśmy.

Więcej informacji na temat algorytmu Jarvisa znajduje się [tutaj](https://edu.pjwstk.edu.pl/wyklady/asd/scb/asd13/main13_p5.html).

### Przykład 1

#### Wejście
Wierzchołki grafu:

0: 0 5
1: 5 0
2: 5 5
3: 0 0
4: 2 2
5: 3 4

#### Wyjście
> Otoczka wypukła: **[0, 2, 1, 3]**
Obwód: **20**

### Przykład 2

#### Wejście
Wierzchołki grafu:

0: -9.432 2.24
1: 2.594 0.076
2: -7.73 6.264
3: -8.39 9.41
4: -5.073 -4.979
5: 2.709 -9.274
6: 2.693 -1.154
7:-2.046 -0.713
8: 0.553 -2.059
9: -3.397 -4.613

#### Wyjście
> Otoczka wypukła: **[4, 0, 3, 1, 5]**
Obwód: **48.3318**

## Wyszukiwanie najlepszej drogi
Aby znaleźć najlepszą drogę z fabryki do miejsca budowy płotu należy wyznaczyć maksymalny przepływ.

### Dowód poprawności
Do wyznaczania maksymalnego przepływu używamy algorytmu Edmondsa-Karpa. Jego złożoność czasowa wynosi O(VE²);
* V - liczba wierzchołków,
* E - liczba krawędzi.

Poprawność algorytmu wynika wprost z twierdzenia Forda-Fulkersona, które dowodzi, że wartość dowolnego przepływu maksymalnego jest równa przepustowości dowolnego przekroju minimalnego.

Więcej informacji na temat algorytmu Edmondsa-Karpa znajduje się [tutaj](http://algorytmy.ency.pl/artykul/algorytm_edmondsa_karpa)

### Przykład 1

#### Wejście
Krawędzie w grafie:

    0 -> 5 [przepływ = "48.4"];
    0 -> 7 [przepływ = "24.64"];
    1 -> 0 [przepływ = "95.8"];
    1 -> 8 [przepływ="47.91"];
    2 -> 6 [przepływ="94.03"];
    2 -> 9 [przepływ="56.43"];
    2 -> 1 [przepływ="66.5"];
    2 -> 5 [przepływ="47.51"];
    3 -> 1 [przepływ="89.64"];
    3 -> 4 [przepływ="8.89"];
    4 -> 2 [przepływ="47.86"];
    4 -> 9 [przepływ="2.06"];
    5 -> 4 [przepływ="16.59"];
    5 -> 0 [przepływ="16.07"];
    5 -> 3 [przepływ="22.64"];
    5 -> 1 [przepływ="18.64"];
    6 -> 5 [przepływ="33.88"];
    8 -> 0 [przepływ="49.69"];
    8 -> 6 [przepływ="16.86"];
    9 -> 7 [przepływ="34.5"];

Otoczka wypukła:

4, 0, 3, 1, 5

#### Wyjście
> id wierzcholka: 4, maksymalny przeplyw z fabryki: **25.48**
id wierzcholka: 0, maksymalny przeplyw z fabryki: **143.71**
id wierzcholka: 3, maksymalny przeplyw z fabryki: **22.64**
id wierzcholka: 1, ten wierzcholek jest fabryka
id wierzcholka: 5, maksymalny przeplyw z fabryki: **65.26**

### Przykład 2

#### Wejście
Krawędzie w grafie:

    0 -> 4 [przepływ="65.85"];
    2 -> 3 [przepływ="3.49"];
    3 -> 4 [przepływ="71.29"];
    3 -> 2 [przepływ="21.16"];
    3 -> 1 [przepływ="2.78"];
    4 -> 3 [przepływ="91.05"];
    4 -> 0 [przepływ="28.08"];

Otoczka wypukła:

2, 3, 1, 4

#### Wyjście
> id wierzcholka: 2, maksymalny przeplyw z fabryki: **21.16**
id wierzcholka: 3, maksymalny przeplyw z fabryki: **65.85**
id wierzcholka: 1, maksymalny przeplyw z fabryki: **2.78**
id wierzcholka: 4, maksymalny przeplyw z fabryki: **65.85**

### Przykład 3
##### Wejście
Krawędzie w grafie:

    0 -> 1 [przepływ="3"];
    0 -> 2 [przepływ="1"];
    1 -> 3 [przepływ="1"];
    2 -> 0 [przepływ="4"];
    2 -> 3 [przepływ="1"];
    3 -> 4 [przepływ="5"];

Otoczka wypukła:

 5, 4, 1, 0, 2

#### Wyjście
>id wierzcholka: 5, maksymalny przeplyw z fabryki: **0**
id wierzcholka: 4, maksymalny przeplyw z fabryki: **2**
id wierzcholka: 1, maksymalny przeplyw z fabryki: **3**
id wierzcholka: 0, ten wierzcholek jest fabryka
id wierzcholka: 2, maksymalny przeplyw z fabryki: **1**

## Dobieranie tragarzy w pary
Posiadając dwa zbiory tragarzy oraz inforamcje o tragarzach, którzy się lubią tworzymy graf skierowany dodając wierzchołek początkowy i końcowy a tragarzy traktując jak zwykłe wierzchołki. Przepustowość na każdej krawędzi ustawiamy zawsze na wartość 1. Następnie używając algorytmu Edmondsa-Karpa wyszukujemy maksymalny przepływ, który jest jednocześnie maksymalną liczbą par, które możemy utworzyć.

### Dowód poprawności
[Dowód jak wyżej.](#Wyszukiwanie-najlepszej-drogi)

### Przykład 1

#### Wejście
Ilość tragarzy mających ręce w prawo: **5**
Ilość tragarzy mających ręce w lewo: **5**

Id leworęcznych tragarzy, których lubi tragarz praworeczny o id 0: **7**
Id leworęcznych tragarzy, których lubi tragarz praworeczny o id 1: **9 8 7**
Id leworęcznych tragarzy, których lubi tragarz praworeczny o id 2: **7 8**
Id leworęcznych tragarzy, których lubi tragarz praworeczny o id 3: **żadnego**
Id leworęcznych tragarzy, których lubi tragarz praworeczny o id 4: **7 5 6**

#### Wyjście
>Maksymalna liczba par jakie można utworzyć: **4**

>Przykładowe pary tragarzy:
**0 <--> 7**
**1 <--> 9**
**2 <--> 8**
**4 <--> 5**

### Przykład 2

#### Wejście
Ilość tragarzy mających ręce w prawo: **11**
Ilość tragarzy mających ręce w lewo: **5**

Id leworęcznych tragarzy, których lubi tragarz praworeczny o id 0: **11 13 15**
Id leworęcznych tragarzy, których lubi tragarz praworeczny o id 1: **14**
Id leworęcznych tragarzy, których lubi tragarz praworeczny o id 2: **15 11**
Id leworęcznych tragarzy, których lubi tragarz praworeczny o id 3: **12 11 15 13**
Id leworęcznych tragarzy, których lubi tragarz praworeczny o id 4: **12 13 15 11**
Id leworęcznych tragarzy, których lubi tragarz praworeczny o id 5: **11 12 15 14**
Id leworęcznych tragarzy, których lubi tragarz praworeczny o id 6: **12**
Id leworęcznych tragarzy, których lubi tragarz praworeczny o id 7: **12**
Id leworęcznych tragarzy, których lubi tragarz praworeczny o id 8: **żadnego**
Id leworęcznych tragarzy, których lubi tragarz praworeczny o id 9: **12 11 13 14**
Id leworęcznych tragarzy, których lubi tragarz praworeczny o id 10: **13 11 14**

#### Wyjście
>Maksymalna liczba par jakie można utworzyć: **5**

>Przykladowe pary tragarzy:
**0 <--> 11**
**1 <--> 14**
**2 <--> 15**
**3 <--> 12**
**4 <--> 13**

## Kodowanie melodii na maszynie informatyka
Do zakodownia melodii w ten sposób by zabierała mniej miejsca użyliśmy algorytmu Huffmana.

### Dowód poprawności
Znaki występujące najczęściej posiadają kody najkrótsze, ponieważ znajdują się najbliżej korzenia w drzewie. Dzięki temu sumaryczna liczba bitów jest mniejsza niż przy stosowaniu kodów o stałej długości. Pozwala to zaoszczędzić wykorzystywane miejsce na maszynie statystycznie o około 20%.
### Przykład 1

#### Wejście

melodia:`jmrtddpazlibbqcbagdynmlmeozcni`

#### Wyjście
>zakodowana melodia: 01110001111010111111111111100110110000110001101010010111001011010011010101111100001100001100000110100100100001101111001101

### Przykład 2

#### Wejście

melodia: `zzzzzzz`

#### Wyjście
>zakodowana melodia:
>0000000

### Przykład 3

#### Wejście

melodia: `awawawaw`

#### Wyjście
>zakodowana melodia:
>01010101

## Zamiana fragmentów opowieści-melodii
Do wyszukiwania fragmentów melodii, które mają być zmienione użyto algorytmu Boyera-Moore'a.

### Dowód poprawności
Algorytm wykorzystuje dwie heurystyki: `bad character heuristic`oraz `good suffix heuristic`. Przesunięcie wyznacza się jako maksimum przesunięć wyznaczonych w tych dwóch heurystykach.
* `bad character heuristic` - jeśli podczas dopasowywania wzorca do tekstu napotkamy znak w tekście, który nie zgadza się ze znakiem we wzorcu, przesuwamy wzorzec w prawo tak, aby ten niezgodny znak w tekście wyrównał się z jego ostatnim wystąpieniem we wzorcu (lub jeśli znak nie występuje we wzorcu, przesuwamy wzorzec poza ten znak).
* `good suffix heuristic` - jeśli część wzorca została dopasowana, ale napotkano niezgodność, przesuwamy wzorzec w prawo, aby dopasowany sufiks wyrównał się z jego następnym wystąpieniem we wzorcu (lub najbliższym prefiksem wzorca, jeśli taki występuje).

Przesunięcie wzorca zgodnie z tymi regułami gwarantuje, że żadne możliwe dopasowanie nie zostanie pominięte. Dodatkowo przesuwamy wzorzec o maksimum z tych przesunięć, przez co przeszukujemy możliwie najmniej fragmentów tekstu nie zawierających wzorca.

W oparciu o prezentację z wykładu:
* O(nm) - wyszukiwanie(wersja pesymistyczna)
* O(n + m) - wyszukiwanie (wersja pesymistyczna, gdy wzorzec nie występuje w tekście)
>n - długość tekstu
>m - długość wzorca

### Przykład 1

#### Wejście

szukany wzorzec: `poli`
zamieniamy na: `boli`
melodia:`sdlkjfnsdjkfsdfpolikjfnskjfnsfjkpolishfsdhjs`

#### Wyjście
>zmieniona melodia: sdlkjfnsdjkfsdf**boli**kjfnskjfnsfjk**boli**shfsdhjs

### Przykład 2

#### Wejście
szukany wzorzec: `morskich`
zamieniamy na: `jeziorne`
melodia:`kiedyrumzaszumiwglowiealyswiatnabieratresciwtedychetniesluchaczlowiekmorskichopowiescihejhakolejkenalejhejhakielichywzniesmytozrobidoskonalemorskimopowiesciom`

#### Wyjście
>zmieniona melodia:
kiedyrumzaszumiwglowiealyswiatnabieratresciwtedychetniesluchaczlowiek**jeziorne**opowiescihejhakolejkenalejhejhakielichywzniesmytozrobidoskonalemorskimopowiesciom

### Przykład 3

#### Wejście
szukany wzorzec: `iamgonnahurtyou`
zamieniamy na: ---
melodia: `nevergonnagiveyouupnevergonnaletyoudownnevergonnarunaroundanddesertyounevergonnamakeyoucrynevergonnasaygoodbyenevergonnatellalieandhurtyou`

#### Wyjście
> nie znaleziono podanego wzorca

## Grafik pracy strażników
Do przypisania strażników do poszczególnych dni tygodnia używamy utworzonego przez nas algorytmu operującego na kolejkach priorytetowych.

### Opis algorytmu
Zaczynamy przejście od najjaśniejszego punktu płotu, gdyż dla każdego innego dowolnego punktu płotu, będzie on od niego jaśniejszy, a więc nie będziemy musieli w nim odpocząć. Następnie sprawdzając punkty - na dojście do których dany strażnik ma wystarczająco energii - szukamy najjaśniejszego z nich, który jest jednocześnie ciemniejszy od obecnego. Dzięki temu zmniejszamy prawdopodobieństwo tego, że kolejny punkt do którego przejdziemy będzie jaśniejszy - tym samym zmniejszając liczbę potencjalnych odpoczynków danego strażnika.

W wypadku jeśli wśród punktów do których strażnik może dojść nie ma takiego w którym mógłby zatrzymać się bez odpoczynku, przechodzi do najdalszego do którego ma energię.

### Dowód poprawności
Z każdym obiegiem pętli używanej do wyszukiwania kolejnych potencjalnych punktów odpoczynku dla strażnika, poruszamy się o co najmniej o jeden wierzchołek do przodu, więc ich wyszukiwanie na pewno się zakończy.

Nie jesteśmy w stanie stwierdzić, że jest to najbardziej optymalne rozwiązanie, gdyż nasz algorytm jest zachłanny - podjemuje najlepszą w danym momencie decyzję.

### Przykład 1

#### Wejście
Jasność punktów na otoczce:

0: 3
1: 1
2: 3
3: 1

Dostępni strażnicy

id: 4 energia: 3
id: 5 energia: 3
id: 13 energia: 3
id: 8 energia: 3
id: 10 energia: 3
id: 15 energia: 3
id: 16 energia: 3
id: 11 energia: 2
id: 12 energia: 2
id: 18 energia: 2
id: 3 energia: 2
id: 19 energia: 2
id: 17 energia: 2
id: 2 energia: 2
id: 14 energia: 1
id: 0 energia: 1
id: 6 energia: 1
id: 7 energia: 1
id: 9 energia: 1
id: 1 energia: 1

#### Wyjście

>Strażnicy będą zaczynać od puktu o id: 0
Dla dnia tygodnia nr: 1 przydzielono straznika o id: 4. Musi on odpoczac 1 raz(y).
Dla dnia tygodnia nr: 2 przydzielono straznika o id: 5. Musi on odpoczac 1 raz(y).
Dla dnia tygodnia nr: 3 przydzielono straznika o id: 13. Musi on odpoczac 1 raz(y).
Dla dnia tygodnia nr: 4 przydzielono straznika o id: 8. Musi on odpoczac 1 raz(y).
Dla dnia tygodnia nr: 5 przydzielono straznika o id: 10. Musi on odpoczac 1 raz(y).
Dla dnia tygodnia nr: 6 przydzielono straznika o id: 15. Musi on odpoczac 1 raz(y).
Dla dnia tygodnia nr: 7 przydzielono straznika o id: 16. Musi on odpoczac 1 raz(y).

### Przykład 2

#### Wejście
Jasność punktów na otoczce:

0: 9
1: 0
2: 6
3: 4
4: 10
5: 4
6: 7
7: 3
8: 2
9: 5
10: 1

Dostepni straznicy:

id: 2 energia: 3
id: 4 energia: 3
id: 9 energia: 3
id: 15 energia: 3
id: 17 energia: 3
id: 1 energia: 2
id: 6 energia: 2
id: 13 energia: 2
id: 11 energia: 2
id: 12 energia: 2
id: 18 energia: 2
id: 7 energia: 1
id: 14 energia: 1
id: 19 energia: 1
id: 16 energia: 1
id: 5 energia: 1
id: 3 energia: 1
id: 0 energia: 1
id: 10 energia: 1
id: 8 energia: 1

#### Wyjście
>Straznicy beda zaczynac od puktu o id: 4
Dla dnia tygodnia nr: 1 przydzielono straznika o id: 2. Musi on odpoczac 1 raz(y).
Dla dnia tygodnia nr: 2 przydzielono straznika o id: 4. Musi on odpoczac 1 raz(y).
Dla dnia tygodnia nr: 3 przydzielono straznika o id: 9. Musi on odpoczac 1 raz(y).
Dla dnia tygodnia nr: 4 przydzielono straznika o id: 15. Musi on odpoczac 1 raz(y).
Dla dnia tygodnia nr: 5 przydzielono straznika o id: 17. Musi on odpoczac 1 raz(y).
Dla dnia tygodnia nr: 6 przydzielono straznika o id: 1. Musi on odpoczac 2 raz(y).
Dla dnia tygodnia nr: 7 przydzielono straznika o id: 6. Musi on odpoczac 2 raz(y).