From c5fcf7179a83ef65c86c6a4a390029149e518649 Mon Sep 17 00:00:00 2001 From: Franciszek Malinka Date: Tue, 5 Oct 2021 21:49:54 +0200 Subject: Duzy commit ze smieciami --- semestr-4/aisd/lista0/L0Z8.md | 51 + semestr-4/aisd/lista0/Rozw L0.pdf | Bin 0 -> 1983735 bytes semestr-4/aisd/lista0/lista0.pdf | Bin 0 -> 83161 bytes semestr-4/aisd/lista1/Lista 1.pdf | Bin 0 -> 810791 bytes semestr-4/aisd/lista1/lista1.pdf | Bin 0 -> 103432 bytes semestr-4/aisd/lista2/Lista 2.pdf | Bin 0 -> 2301798 bytes semestr-4/aisd/lista2/lista2.pdf | Bin 0 -> 128638 bytes semestr-4/aisd/lista3/huff.pdf | Bin 0 -> 62844 bytes semestr-4/aisd/lista3/huffman.pdf | Bin 0 -> 73477 bytes semestr-4/aisd/lista3/lista3.pdf | Bin 0 -> 179499 bytes semestr-4/aisd/pracownia1/pracownia1.pdf | Bin 0 -> 55846 bytes semestr-4/aisd/pracownia1/rozw.cpp | 59 ++ semestr-4/aisd/pracownia1/rozw2.cpp | 33 + semestr-4/aisd/pracownia2/gen.py | 24 + semestr-4/aisd/pracownia2/gen_test.sh | 24 + semestr-4/aisd/pracownia2/rozw.cpp | 59 ++ semestr-4/aisd/pracownia2/rozw2.cpp | 71 ++ semestr-4/aisd/pracownia2/rozw3.cpp | 71 ++ semestr-4/aisd/pracownia2/rozw4.cpp | 51 + semestr-4/aisd/pracownia2/show_problem.pdf | Bin 0 -> 53598 bytes semestr-4/aisd/pracownia3/check.cpp | 87 ++ semestr-4/aisd/pracownia3/gen.py | 14 + semestr-4/aisd/pracownia3/ocen.sh | 18 + semestr-4/aisd/pracownia3/rozw.cpp | 102 ++ semestr-4/aisd/pracownia3/show_problem.pdf | Bin 0 -> 73936 bytes semestr-4/aisd/pracownia3/wa.outr | 1025 ++++++++++++++++++++ semestr-4/aisd/pracownia4/brut.cpp | 69 ++ semestr-4/aisd/pracownia4/gen.py | 24 + semestr-4/aisd/pracownia4/rozw.cpp | 157 +++ semestr-4/aisd/pracownia4/rozw2.cpp | 135 +++ semestr-4/aisd/pracownia4/rozw3.cpp | 149 +++ semestr-4/aisd/pracownia4/show_problem.pdf | Bin 0 -> 61345 bytes semestr-4/aisd/pracownia4/test.sh | 21 + semestr-4/aisd/pracownia5/gen.py | 40 + semestr-4/aisd/pracownia5/t.tin | 0 semestr-4/aisd/pracownia5/wzo.cpp | 288 ++++++ semestr-4/aisd/pracownia5/wzo2.cpp | 184 ++++ semestr-4/aisd/pracownia6/wzo.cpp | 51 + semestr-4/aisd/themis/AISDDEBIUT21.cpp | 24 + semestr-4/aisd/themis/AISDPOTEGOWANIE.cpp | 29 + semestr-4/aisd/themis/BELLMAN.cpp | 55 ++ semestr-4/aisd/themis/FIB.cpp | 58 ++ .../aisd/wyklady/Notatka 1 - Preliminaria.pdf | Bin 0 -> 211162 bytes semestr-4/aisd/wyklady/Notatka 2 - Kopiec.pdf | Bin 0 -> 150213 bytes .../aisd/wyklady/Notatka 3 - Zach\305\202any.pdf" | Bin 0 -> 243598 bytes .../wyklady/Notatka 4 - divide and conquer.pdf | Bin 0 -> 326839 bytes .../wyklady/Notatka 5 - divide and conquer cd.pdf | Bin 0 -> 146884 bytes .../Notatka 6 - Programowanie Dynamiczne.pdf | Bin 0 -> 213697 bytes .../Notatka 7 - Programowanie Dynamiczne cd.pdf | Bin 0 -> 214965 bytes 49 files changed, 2973 insertions(+) create mode 100644 semestr-4/aisd/lista0/L0Z8.md create mode 100644 semestr-4/aisd/lista0/Rozw L0.pdf create mode 100644 semestr-4/aisd/lista0/lista0.pdf create mode 100644 semestr-4/aisd/lista1/Lista 1.pdf create mode 100644 semestr-4/aisd/lista1/lista1.pdf create mode 100644 semestr-4/aisd/lista2/Lista 2.pdf create mode 100644 semestr-4/aisd/lista2/lista2.pdf create mode 100644 semestr-4/aisd/lista3/huff.pdf create mode 100644 semestr-4/aisd/lista3/huffman.pdf create mode 100644 semestr-4/aisd/lista3/lista3.pdf create mode 100644 semestr-4/aisd/pracownia1/pracownia1.pdf create mode 100644 semestr-4/aisd/pracownia1/rozw.cpp create mode 100644 semestr-4/aisd/pracownia1/rozw2.cpp create mode 100644 semestr-4/aisd/pracownia2/gen.py create mode 100755 semestr-4/aisd/pracownia2/gen_test.sh create mode 100644 semestr-4/aisd/pracownia2/rozw.cpp create mode 100644 semestr-4/aisd/pracownia2/rozw2.cpp create mode 100644 semestr-4/aisd/pracownia2/rozw3.cpp create mode 100644 semestr-4/aisd/pracownia2/rozw4.cpp create mode 100644 semestr-4/aisd/pracownia2/show_problem.pdf create mode 100644 semestr-4/aisd/pracownia3/check.cpp create mode 100644 semestr-4/aisd/pracownia3/gen.py create mode 100755 semestr-4/aisd/pracownia3/ocen.sh create mode 100644 semestr-4/aisd/pracownia3/rozw.cpp create mode 100644 semestr-4/aisd/pracownia3/show_problem.pdf create mode 100644 semestr-4/aisd/pracownia3/wa.outr create mode 100644 semestr-4/aisd/pracownia4/brut.cpp create mode 100644 semestr-4/aisd/pracownia4/gen.py create mode 100644 semestr-4/aisd/pracownia4/rozw.cpp create mode 100644 semestr-4/aisd/pracownia4/rozw2.cpp create mode 100644 semestr-4/aisd/pracownia4/rozw3.cpp create mode 100644 semestr-4/aisd/pracownia4/show_problem.pdf create mode 100755 semestr-4/aisd/pracownia4/test.sh create mode 100644 semestr-4/aisd/pracownia5/gen.py create mode 100644 semestr-4/aisd/pracownia5/t.tin create mode 100644 semestr-4/aisd/pracownia5/wzo.cpp create mode 100644 semestr-4/aisd/pracownia5/wzo2.cpp create mode 100644 semestr-4/aisd/pracownia6/wzo.cpp create mode 100644 semestr-4/aisd/themis/AISDDEBIUT21.cpp create mode 100644 semestr-4/aisd/themis/AISDPOTEGOWANIE.cpp create mode 100644 semestr-4/aisd/themis/BELLMAN.cpp create mode 100644 semestr-4/aisd/themis/FIB.cpp create mode 100644 semestr-4/aisd/wyklady/Notatka 1 - Preliminaria.pdf create mode 100644 semestr-4/aisd/wyklady/Notatka 2 - Kopiec.pdf create mode 100644 "semestr-4/aisd/wyklady/Notatka 3 - Zach\305\202any.pdf" create mode 100644 semestr-4/aisd/wyklady/Notatka 4 - divide and conquer.pdf create mode 100644 semestr-4/aisd/wyklady/Notatka 5 - divide and conquer cd.pdf create mode 100644 semestr-4/aisd/wyklady/Notatka 6 - Programowanie Dynamiczne.pdf create mode 100644 semestr-4/aisd/wyklady/Notatka 7 - Programowanie Dynamiczne cd.pdf (limited to 'semestr-4/aisd') diff --git a/semestr-4/aisd/lista0/L0Z8.md b/semestr-4/aisd/lista0/L0Z8.md new file mode 100644 index 0000000..d9c8604 --- /dev/null +++ b/semestr-4/aisd/lista0/L0Z8.md @@ -0,0 +1,51 @@ +# AiSD, L0Z8 + +Dane: $n$, $m$. +Wynik: (Współczynnik przy $x^2$) $\mod m$ wielomianu $\underbrace{(\ldots((x-2)^2 -2)^2\ldots - 2)^2}_{n\text{ razy}}$. + +**Obserwacja 1:** Wszystkie obliczenia możemy wykonywać $\mod m$. Nie zwiększa to złożoności obliczeniowej, a ogranicza wartości które musimy utrzymywać. + +**Obserwacja 2:** Obliczając współczynniki wielomianu nie musimy obliczać współczynników przy większej potędze $x$ niż $2$. + +Niech $w_k(x)$ = $\underbrace{(\ldots((x-2)^2 -2)^2\ldots - 2)^2}_{k\text{ razy}}$, ale bez wyrazów gdzie $x$ występuje w potędze większej niż $2$. Dla jasności przyjmujemy $w_0(x) = x$. + +Mamy w takim razie $w_k(x) = a_k + b_kx + c_kx^2$. Ponadto: +\begin{align} + w_{k+1}(x) &= (a_k + b_kx + c_kx^2 - 2)^2 \\ + &= \underbrace{(a_k^2 - 4a_k + 4)}_{a_{k+1}} + \underbrace{(2a_kb_k - 4b_k)}_{b_{k+1}}x + \underbrace{(2a_kc_k + b_k^2 - 4c_k)}_{c_{k+1}}x^2 +\end{align} + +Dostajemy zatem układ rekurencyjny: +\begin{cases} +a_0=c_0=0 \\ +b_0=1 \\ +a_{k+1} = a_k^2 - 4a_k + 4 = (a_k - 2)^2 \\ +b_{k+1} = 2a_kb_k - 4b_k \\ +c_{k+1} = 2a_kc_k + b_k^2 - 4c_k \\ +\end{cases} + +**Obserwacja 3:** $a_k = 4$ dla $k \ge 1$. Faktycznie, policzmy $a_1 = (a_0 - 2)^2 = 4$. Ale $a_2 = (4 - 2)^2 = 4$. Zatem ciąg ten jest stale równy $4$ od $k = 1$. + +**Obserwacja 4:** $b_k = -(4^k)$ dla $k \ge 1$. Korzystając z zależności rekurencyjnej dla $k \ge 1$ mamy $b_{k+1} = 2b_k(a_k - 2) = 4b_k$, ale $b_1 = -4$, zatem $b_k = -(4^k)$. + +Korzystając z obserwacji 3. i 4. upraszczamy zależność rekurencyjną na $c_{k+1}$ dla $k\ge 1$: +\begin{align} +c_{k+1} = 8c_k + 4^{2k} - 4c_k = 4c_k + 4^{2k} +\end{align} + +Stąd już dostajemy łatwą zależność (dla $k\ge 1$): + +$$ +\left[\begin{array}{cc} +4 & 1\\ +0 & 16 +\end{array}\right] +\left[\begin{array}{cc} +c_k\\ +4^{2k} +\end{array}\right] = +\left[\begin{array}{cc} +c_{k+1}\\ +4^{2(k+1)} +\end{array}\right] +$$ \ No newline at end of file diff --git a/semestr-4/aisd/lista0/Rozw L0.pdf b/semestr-4/aisd/lista0/Rozw L0.pdf new file mode 100644 index 0000000..d39c13b Binary files /dev/null and b/semestr-4/aisd/lista0/Rozw L0.pdf differ diff --git a/semestr-4/aisd/lista0/lista0.pdf b/semestr-4/aisd/lista0/lista0.pdf new file mode 100644 index 0000000..31b9daa Binary files /dev/null and b/semestr-4/aisd/lista0/lista0.pdf differ diff --git a/semestr-4/aisd/lista1/Lista 1.pdf b/semestr-4/aisd/lista1/Lista 1.pdf new file mode 100644 index 0000000..7e2f5ae Binary files /dev/null and b/semestr-4/aisd/lista1/Lista 1.pdf differ diff --git a/semestr-4/aisd/lista1/lista1.pdf b/semestr-4/aisd/lista1/lista1.pdf new file mode 100644 index 0000000..a7dc065 Binary files /dev/null and b/semestr-4/aisd/lista1/lista1.pdf differ diff --git a/semestr-4/aisd/lista2/Lista 2.pdf b/semestr-4/aisd/lista2/Lista 2.pdf new file mode 100644 index 0000000..ccf83b7 Binary files /dev/null and b/semestr-4/aisd/lista2/Lista 2.pdf differ diff --git a/semestr-4/aisd/lista2/lista2.pdf b/semestr-4/aisd/lista2/lista2.pdf new file mode 100644 index 0000000..2d8937f Binary files /dev/null and b/semestr-4/aisd/lista2/lista2.pdf differ diff --git a/semestr-4/aisd/lista3/huff.pdf b/semestr-4/aisd/lista3/huff.pdf new file mode 100644 index 0000000..bf2cfec Binary files /dev/null and b/semestr-4/aisd/lista3/huff.pdf differ diff --git a/semestr-4/aisd/lista3/huffman.pdf b/semestr-4/aisd/lista3/huffman.pdf new file mode 100644 index 0000000..1881a27 Binary files /dev/null and b/semestr-4/aisd/lista3/huffman.pdf differ diff --git a/semestr-4/aisd/lista3/lista3.pdf b/semestr-4/aisd/lista3/lista3.pdf new file mode 100644 index 0000000..74514b8 Binary files /dev/null and b/semestr-4/aisd/lista3/lista3.pdf differ diff --git a/semestr-4/aisd/pracownia1/pracownia1.pdf b/semestr-4/aisd/pracownia1/pracownia1.pdf new file mode 100644 index 0000000..2b99ba4 Binary files /dev/null and b/semestr-4/aisd/pracownia1/pracownia1.pdf differ diff --git a/semestr-4/aisd/pracownia1/rozw.cpp b/semestr-4/aisd/pracownia1/rozw.cpp new file mode 100644 index 0000000..acbd711 --- /dev/null +++ b/semestr-4/aisd/pracownia1/rozw.cpp @@ -0,0 +1,59 @@ +#include +using namespace std; +typedef long long ll; + +vector>> v; +const int MAX_LEN = 85; +int bits[100]; + +int main() { + ios_base::sync_with_stdio(false); + cin.tie(); + int n; + cin >> n; + for (int i = 0; i < n; i++) { + int d, nd; + cin >> d >> nd; + int k = 0; + while (d % 2 == 0) { + d /= 2; + k++; + } + v.push_back({d, {k, nd}}); + } + sort(v.begin(), v.end()); + int result = 0; + + for (int i = 0; i < n; ) { + int h = i; + int d = v[i].first; + while (h < n && v[h].first == d) { + h++; + } + for (int k = 0; k < MAX_LEN; k++) + bits[k] = 0; + for (int j = i; j < h; ++j) { + ll x = (ll)(1LL << v[j].second.first) * (ll)v[j].second.second; + int k = 0; + while (x > 0) { + if (x % 2 == 1) { + bits[k]++; + } + x /= 2; + k++; + } + } + + for (int k = 0; k < MAX_LEN; k++) { + if (bits[k] > 1) { + bits[k + 1] += bits[k]/2; + } + if (bits[k] % 2 == 1) { + result++; + } + } + i = h; + } + + cout << result << "\n"; +} \ No newline at end of file diff --git a/semestr-4/aisd/pracownia1/rozw2.cpp b/semestr-4/aisd/pracownia1/rozw2.cpp new file mode 100644 index 0000000..35fd37e --- /dev/null +++ b/semestr-4/aisd/pracownia1/rozw2.cpp @@ -0,0 +1,33 @@ +#include +using namespace std; +typedef unsigned long long ll; + +vector> v; + +int main() { + int n; + scanf("%d", &n); + for (int i = 0; i < n; i++) { + int d, nd, k = 0; + scanf("%d %d", &d, &nd); + while (d % 2 == 0) { + k++; + d /= 2; + } + v.push_back({d, (ll)(1LL< sum: + print("N musi być mniejsze równe od sum.") + exit() + +t = [1 for i in range(n)] + +for i in range(sum - n): + idx = randint(0, n - 1) + t[idx] += 1 + +print(n) +for i in t: + print(i, end=' ') +print() diff --git a/semestr-4/aisd/pracownia2/gen_test.sh b/semestr-4/aisd/pracownia2/gen_test.sh new file mode 100755 index 0000000..d5bff05 --- /dev/null +++ b/semestr-4/aisd/pracownia2/gen_test.sh @@ -0,0 +1,24 @@ +#!/bin/bash + +mkdir -p tests +cp gen.py tests/ +cd tests + +python3 gen.py 1 5 20 > t1.in +python3 gen.py 2 10 100 > t2.in +python3 gen.py 3 20 200 > t3.in +python3 gen.py 4 40 600 > t4.in +python3 gen.py 5 80 5000 > t5.in +python3 gen.py 6 160 10000 > t6.in +python3 gen.py 7 320 10000 > t7.in +python3 gen.py 8 640 20000 > t8.in +python3 gen.py 9 1280 20000 > t9.in +python3 gen.py 10 2000 2000 > t10.in +python3 gen.py 11 2000 20000 > t11.in +python3 gen.py 12 2000 200000 > t12.in +python3 gen.py 13 2000 1000000 > t13.in +python3 gen.py 14 2000 1000000 > t14.in +python3 gen.py 15 2000 1000000 > t15.in + + +rm gen.py diff --git a/semestr-4/aisd/pracownia2/rozw.cpp b/semestr-4/aisd/pracownia2/rozw.cpp new file mode 100644 index 0000000..dd0d700 --- /dev/null +++ b/semestr-4/aisd/pracownia2/rozw.cpp @@ -0,0 +1,59 @@ +#include +using namespace std; + +const int MAX_SUM = 1e6; +const int N = 2e3 + 10; + +unordered_map sums; +vector> v; + +int main() { + int n; + scanf("%d", &n); + sums[0] = 0; + for (int i = 0; i < n; i++) { + int h; + scanf("%d", &h); + v.clear(); + for (auto kv: sums) { + v.push_back(kv); + } + + for (auto kv: v) { + int dif = kv.first, best = kv.second; + cout << dif << " " << best << "\n"; + int aux = 0; + if (dif >= 0) { + aux = h; + } else if (dif + h > 0) { + aux = dif + h; + } + + cout << ">aux: " << aux << " "; + sums[dif + h] = max(sums[dif + h], best + aux); + aux = 0; + if (dif <= 0) { + aux = h; + } else if (dif - h < 0) { + aux = h - dif; + } + cout << aux << "\n"; + sums[dif - h] = max(sums[dif - h], best + aux); + } + cout << "---\n"; + } + for (auto kv: sums) { + printf("%d %d\n", kv.first, kv.second); + } + + if (sums[0] != 0) { + printf("TAK\n%d\n", sums[0]); + } else { + int mini = 1e9; + sums.erase(0); + for (auto kv: sums) { + mini = min(mini, abs(kv.first)); + } + printf("NIE\n%d\n", mini); + } +} \ No newline at end of file diff --git a/semestr-4/aisd/pracownia2/rozw2.cpp b/semestr-4/aisd/pracownia2/rozw2.cpp new file mode 100644 index 0000000..fa0b2d6 --- /dev/null +++ b/semestr-4/aisd/pracownia2/rozw2.cpp @@ -0,0 +1,71 @@ +#include +using namespace std; + +const int MAX_SUM = 5e5; + +int t[2][MAX_SUM * 2 + 10]; +int H[2003]; +uint8_t eligible[2][MAX_SUM * 2 + 10]; // 0 - not used, 1 - only st, 2 - only nd, 3 - both + +int main() { + int n, sum = 0, which = 0; + scanf("%d", &n); + for (int i = 0; i < n; i++) + scanf("%d", &H[i]); + sort(H, H + n); + + for (int i = 0; i < n; i++) { + // cout << i << "\n"; + int h = H[i], *prev = t[which], *cur = t[which ^ 1]; + uint8_t *pe = eligible[which], *ce = eligible[which ^ 1]; + + for (int dif = -sum; dif <= sum; ++dif) { + int aux = 0; + // cout << (int)pe[dif + MAX_SUM] << "\n"; + + if (abs(dif) > MAX_SUM || (pe[dif + MAX_SUM] == 0 && dif != 0)) continue; + + if (dif + h <= MAX_SUM) { + if (dif >= 0) { + aux = h; + } else if (dif + h > 0) { + aux = dif + h; + } + int idx = dif + h + MAX_SUM; + + cur[idx] = max({cur[idx], prev[idx], prev[idx - h] + aux}); + ce[idx] |= pe[dif + MAX_SUM] | 1; + // cout << "> " << idx - MAX_SUM << " " << cur[idx] << " " << (int)eligible[idx] << "\n"; + } + + if (dif - h >= -MAX_SUM) { + aux = 0; + if (dif <= 0) { + aux = h; + } else if (dif - h < 0) { + aux = h - dif; + } + int idx = dif - h + MAX_SUM; + cur[idx] = max({cur[idx], prev[idx], prev[idx + h] + aux}); + ce[idx] |= pe[dif + MAX_SUM] | 2; + // cout << ">> " << idx - MAX_SUM << " " << cur[idx] << " " << (int)eligible[idx] << "\n"; + } + } + sum += h; + which ^= 1; + // for (int dif = -sum; dif <= sum; ++dif) { + // cout << dif << " " << " " << (int)ce[dif + MAX_SUM] << " " << cur[dif + MAX_SUM] << "\n"; + // } + // printf("-----\n"); + } + if (eligible[which][MAX_SUM] == 3) { + printf("TAK\n%d\n", t[which][MAX_SUM]); + } else { + int mini = 1e9; + for (int i = -MAX_SUM; i <= MAX_SUM; i++) { + if (eligible[which][i + MAX_SUM] == 3) + mini = min(mini, abs(i)); + } + printf("NIE\n%d\n", mini); + } +} \ No newline at end of file diff --git a/semestr-4/aisd/pracownia2/rozw3.cpp b/semestr-4/aisd/pracownia2/rozw3.cpp new file mode 100644 index 0000000..8e3dd2a --- /dev/null +++ b/semestr-4/aisd/pracownia2/rozw3.cpp @@ -0,0 +1,71 @@ +#include +using namespace std; + +#define RIGHT 0 +#define LEFT 1 + +const int MAXN = 2e3 + 10; +const int M = 5e5 + 10; + +int n, H[MAXN], dp[2][M*2]; +bool vis[2][M*2], both[2][M*2]; + +int get_val() + +int main() { + ios_base::sync_with_stdio(false); + cin.tie(); + cin >> n; + for (int i = 0; i < n; i++) { + cin >> H[i]; + } + + int sum = 0, K = 0; + vis[K^1][0] = true; + for (int i = 0; i < n; i++) { + int h = H[i]; + for (int cur = -sum; cur <= sum; ++cur) { + vis[K][cur + M] |= vis[K^1][cur + M]; + both[K][cur + M] |= both[K^1][cur + M]; + dp[K][cur + M] = max({dp[K][cur + M], dp[K^1][cur + M]}); + if (vis[K][cur + M]) { + int val = dp[K][cur + M]; + int left = cur + M - h; + int right = cur + M + h; + + if (cur - h >= 0) { + both[K][right] = true; + } + vis[K][right] = true; + dp[K][right] = max({dp[K][right], dp[K^1][right], dp[K^1][right] + h}); + + if (cur + h <= 0) { + both[K][left]= true; + } + vis[K][left] = true; + dp[K][left] = max({dp[K][left], dp[K^1][left], dp[K^1][left] + h}); + } + } + K^=1; + for (int cur = -sum; cur <= sum; ++cur) { + dp[K][cur + M] = 0; + vis[K][cur + M] = 0; + both[K][cur + M] = 0; + } + sum += h; + } + K^=1; + if (both[K][M]) { + cout << "TAK\n"; + cout << dp[K][M] << "\n"; + } else { + cout << "NIE\n"; + int best = -sum; + for (int cur = -sum ; cur <= sum; ++cur) { + if (both[cur + M] && abs(cur) < abs(best)) { + best = cur; + } + } + cout << abs(best) << "\n"; + } +} \ No newline at end of file diff --git a/semestr-4/aisd/pracownia2/rozw4.cpp b/semestr-4/aisd/pracownia2/rozw4.cpp new file mode 100644 index 0000000..73ff79a --- /dev/null +++ b/semestr-4/aisd/pracownia2/rozw4.cpp @@ -0,0 +1,51 @@ +#include +using namespace std; + +const int MAX_SUM = 1e6, MAXN = 2004; +int n; +int dp[2][MAX_SUM + 10], H[MAXN]; + +int main() { + scanf("%d", &n); + for (int i = 0; i < n; ++i) { + scanf("%d", &H[i]); + } + + sort(H, H + n); + + int sum = 0, K = 0; + for (int i = 0; i < n; ++i) { + int h = H[i]; + for (int i = 0; i <= min(sum, MAX_SUM); i++) + dp[K^1][i] = dp[K][i]; + + for (int i = 0; i <= min(sum, MAX_SUM); i++) { + if (i != 0 && dp[K][i] == 0) continue; + + int left = abs(i - h), aux = i-h >= 0 ? 0 : h-i; + if (left <= MAX_SUM) { + dp[K^1][left] = max(dp[K^1][left], dp[K][i] + aux); + } + int right = i + h; + if (right <= MAX_SUM) { + dp[K^1][right] = max(dp[K^1][right], dp[K][i] + h); + } + } + + K ^= 1; + sum += h; + } + if (dp[K][0] != 0) { + printf("TAK\n%d\n", dp[K][0]); + } + else { + int res = 0; + for (int i = 1; i <= MAX_SUM; i++) { + if (dp[K][i] != i && dp[K][i]) { + res = i; + break; + } + } + printf("NIE\n%d\n", res); + } +} \ No newline at end of file diff --git a/semestr-4/aisd/pracownia2/show_problem.pdf b/semestr-4/aisd/pracownia2/show_problem.pdf new file mode 100644 index 0000000..4ab0312 Binary files /dev/null and b/semestr-4/aisd/pracownia2/show_problem.pdf differ diff --git a/semestr-4/aisd/pracownia3/check.cpp b/semestr-4/aisd/pracownia3/check.cpp new file mode 100644 index 0000000..c9c74d7 --- /dev/null +++ b/semestr-4/aisd/pracownia3/check.cpp @@ -0,0 +1,87 @@ +#include +using namespace std; + +int n, p, m; +int banned[103][3][3]; +int plane[5][10]; + +bool check(int k, int i, int pp) { + for (int kk = k; kk < k + 3; kk++) { + for (int ii = i; ii < i + 3; ii++) { + if (plane[kk][ii] != banned[pp][kk-k][ii-i]) + return false; + } + } + return true; +} + +void debug(int pp) { + for (int i = 0; i < 3; ++i) { + for (int j = 0; j < 3; ++j) { + cout << ((banned[pp][i][j] == 0) ? '.' : 'x'); + } + cout << "\n"; + } +} + +void debug() { + for (int k = 0; k < 5; ++k) { + for (int i = 0; i < n; ++i) { + cout << (plane[k][i] ? 'x' : '.'); + } + cout << "\n"; + } + cout << "\n"; +} + +int ile[1030]; + +int main() { + cin >> n >> p >> m; + for (int i = 0; i < p; i++) { + for (int k = 0; k < 3; k++) { + string s; + cin >> s; + for (int j = 0; j < 3; ++j) { + banned[i][k][j] = (s[j] == 'x'); + } + } + } + int res = 0; + for (int mask = 0; mask < (1<<(5 * n)); mask++) { + for (int k = 0; k < 5; ++k) { + for (int i = 0; i < n; i++) { + plane[k][i] = ((mask & (1 << (k * n + i))) > 0); + } + } + bool dziala = true; + for (int k = 0; k < 3; ++k) { + for (int i = 0; i < n-2; ++i) { + for (int j = 0; j < p; ++j) { + if (check(k, i, j)) { + dziala = false; + break; + } + } + if (!dziala) break; + } + if (!dziala) break; + } + if (dziala) { + res++; + if (res == m) { + res = 0; + } + int mm = 0; + for (int i = 0; i < 5; ++i) { + mm += plane[i][n-2] * (1<<(i*2)); + mm += plane[i][n-1] * (1<<(i*2 + 1)); + } + ile[mm]++; + } + } + for (int i = 0; i < 1024; ++i) { + cout << i << ": " << ile[i] << "\n"; + } + cout << res % m << "\n"; +} \ No newline at end of file diff --git a/semestr-4/aisd/pracownia3/gen.py b/semestr-4/aisd/pracownia3/gen.py new file mode 100644 index 0000000..b572647 --- /dev/null +++ b/semestr-4/aisd/pracownia3/gen.py @@ -0,0 +1,14 @@ +import sys + +mask = int(sys.argv[1]) +print(3, 1, 1000000) + +def f(m): + t = [[0]*3]*3 + for i in range(3): + for j in range(3): + t[i][j] = (m >> (i*3 + j)) & 1 + print('x' if t[i][j] else '.', end='') + print() + +f(mask) \ No newline at end of file diff --git a/semestr-4/aisd/pracownia3/ocen.sh b/semestr-4/aisd/pracownia3/ocen.sh new file mode 100755 index 0000000..593aa67 --- /dev/null +++ b/semestr-4/aisd/pracownia3/ocen.sh @@ -0,0 +1,18 @@ +#!/bin/bash + +make rozw +make check +for i in {0..1023} +do + python3 gen.py $i > t.in + ./rozw < t.in > wa.out + ./check < t.in > t.out + if diff -w wa.out t.out + then + echo $i + echo ok + else + echo nieok + break + fi +done \ No newline at end of file diff --git a/semestr-4/aisd/pracownia3/rozw.cpp b/semestr-4/aisd/pracownia3/rozw.cpp new file mode 100644 index 0000000..7f1a307 --- /dev/null +++ b/semestr-4/aisd/pracownia3/rozw.cpp @@ -0,0 +1,102 @@ +#include +using namespace std; + +const int MAXP = 105; +const int MAXN = 5005; + +int n, p, m; +unordered_set banned; +vector> propagate; +int dp[2][1024 + 10]; + +inline int char_to_bit(char c) { + return c == '.' ? 0 : 1; +} + +void input() { + scanf("%d%d%d", &n, &p, &m); + for (int i = 0; i < p; i++) { + char s[5]; + int value = 0, d = 1; + for (int k = 0; k < 3; k++) { + scanf("%s", s); + value += (char_to_bit(s[0]) + char_to_bit(s[1]) * 2 + char_to_bit(s[2]) * 4) * d; + d *= 8; + } + banned.insert(value); + } +} + +pair> get_pieces_values(int db, int sb) { + int tab[5][3]; + for (int i = 0; i < 5; i++) { + tab[i][0] = (db >> (i*2)) & 1; + tab[i][1] = (db >> (i*2 + 1)) & 1; + tab[i][2] = (sb >> i) & 1; + } + int res[3]; + for (int k = 0; k < 3; ++k) { + int value = 0, d = 1; + for (int i = k; i < k + 3; ++i) { + value += (tab[i][0] + tab[i][1] * 2 + tab[i][2] * 4) * d; + d *= 8; + } + res[k] = value; + } + return {res[0], {res[1], res[2]}}; +} + +int combine(int db, int sb) { + int res = (db >> 1) & 0x155; + for (int i = 0; i < 5; i++) { + res |= ((sb >> i) & 1) << (2*i + 1); + } + return res; +} + +void preproces() { + const int db = (1<<10); // double bar + const int sb = (1<<5); // single bar + + for (int db_mask = 0; db_mask < db; ++db_mask) { + for (int sb_mask = 0; sb_mask < sb; ++sb_mask) { + auto pieces = get_pieces_values(db_mask, sb_mask); + if (banned.count(pieces.first) || banned.count(pieces.second.first) || banned.count(pieces.second.second)) + continue; + int db2_mask = combine(db_mask, sb_mask); + propagate.push_back({db_mask, db2_mask}); + } + } +} + +int compute_dp() { + int K = 1; + for (int i = 0; i < 1024; i++) { + dp[0][i] = 1; + } + for (int i = 2; i < n; i++) { + for (auto pp: propagate) { + int p1 = pp.first, p2 = pp.second; + dp[K][p2] += dp[K^1][p1]; + dp[K][p2] %= m; + } + K ^= 1; + for (int j = 0; j < 1024; ++j) { + dp[K][j] = 0; + } + } + + K ^= 1; + int result = 0; + for (int i = 0; i < 1024; i++) { + result += dp[K][i]; + result %= m; + } + return result; +} + +int main() { + input(); + preproces(); + printf("%d\n", compute_dp()); +} \ No newline at end of file diff --git a/semestr-4/aisd/pracownia3/show_problem.pdf b/semestr-4/aisd/pracownia3/show_problem.pdf new file mode 100644 index 0000000..f426311 Binary files /dev/null and b/semestr-4/aisd/pracownia3/show_problem.pdf differ diff --git a/semestr-4/aisd/pracownia3/wa.outr b/semestr-4/aisd/pracownia3/wa.outr new file mode 100644 index 0000000..81a8bb1 --- /dev/null +++ b/semestr-4/aisd/pracownia3/wa.outr @@ -0,0 +1,1025 @@ +0: 613 +1: 745 +2: 729 +3: 745 +4: 881 +5: 881 +6: 881 +7: 881 +8: 849 +9: 865 +10: 849 +11: 865 +12: 881 +13: 881 +14: 881 +15: 881 +16: 1025 +17: 1025 +18: 1025 +19: 1025 +20: 1025 +21: 1025 +22: 1025 +23: 1025 +24: 1025 +25: 1025 +26: 1025 +27: 1025 +28: 1025 +29: 1025 +30: 1025 +31: 1025 +32: 977 +33: 993 +34: 977 +35: 993 +36: 1009 +37: 1009 +38: 1009 +39: 1009 +40: 977 +41: 993 +42: 977 +43: 993 +44: 1009 +45: 1009 +46: 1009 +47: 1009 +48: 1025 +49: 1025 +50: 1025 +51: 1025 +52: 1025 +53: 1025 +54: 1025 +55: 1025 +56: 1025 +57: 1025 +58: 1025 +59: 1025 +60: 1025 +61: 1025 +62: 1025 +63: 1025 +64: 881 +65: 1025 +66: 1009 +67: 1025 +68: 1025 +69: 1025 +70: 1025 +71: 1025 +72: 1009 +73: 1025 +74: 1009 +75: 1025 +76: 1025 +77: 1025 +78: 1025 +79: 1025 +80: 1025 +81: 1025 +82: 1025 +83: 1025 +84: 1025 +85: 1025 +86: 1025 +87: 1025 +88: 1025 +89: 1025 +90: 1025 +91: 1025 +92: 1025 +93: 1025 +94: 1025 +95: 1025 +96: 1009 +97: 1025 +98: 1009 +99: 1025 +100: 1025 +101: 1025 +102: 1025 +103: 1025 +104: 1009 +105: 1025 +106: 1009 +107: 1025 +108: 1025 +109: 1025 +110: 1025 +111: 1025 +112: 1025 +113: 1025 +114: 1025 +115: 1025 +116: 1025 +117: 1025 +118: 1025 +119: 1025 +120: 1025 +121: 1025 +122: 1025 +123: 1025 +124: 1025 +125: 1025 +126: 1025 +127: 1025 +128: 861 +129: 993 +130: 977 +131: 993 +132: 1009 +133: 1009 +134: 1009 +135: 1009 +136: 977 +137: 993 +138: 977 +139: 993 +140: 1009 +141: 1009 +142: 1009 +143: 1009 +144: 1025 +145: 1025 +146: 1025 +147: 1025 +148: 1025 +149: 1025 +150: 1025 +151: 1025 +152: 1025 +153: 1025 +154: 1025 +155: 1025 +156: 1025 +157: 1025 +158: 1025 +159: 1025 +160: 977 +161: 993 +162: 977 +163: 993 +164: 1009 +165: 1009 +166: 1009 +167: 1009 +168: 977 +169: 993 +170: 977 +171: 993 +172: 1009 +173: 1009 +174: 1009 +175: 1009 +176: 1025 +177: 1025 +178: 1025 +179: 1025 +180: 1025 +181: 1025 +182: 1025 +183: 1025 +184: 1025 +185: 1025 +186: 1025 +187: 1025 +188: 1025 +189: 1025 +190: 1025 +191: 1025 +192: 881 +193: 1025 +194: 1009 +195: 1025 +196: 1025 +197: 1025 +198: 1025 +199: 1025 +200: 1009 +201: 1025 +202: 1009 +203: 1025 +204: 1025 +205: 1025 +206: 1025 +207: 1025 +208: 1025 +209: 1025 +210: 1025 +211: 1025 +212: 1025 +213: 1025 +214: 1025 +215: 1025 +216: 1025 +217: 1025 +218: 1025 +219: 1025 +220: 1025 +221: 1025 +222: 1025 +223: 1025 +224: 1009 +225: 1025 +226: 1009 +227: 1025 +228: 1025 +229: 1025 +230: 1025 +231: 1025 +232: 1009 +233: 1025 +234: 1009 +235: 1025 +236: 1025 +237: 1025 +238: 1025 +239: 1025 +240: 1025 +241: 1025 +242: 1025 +243: 1025 +244: 1025 +245: 1025 +246: 1025 +247: 1025 +248: 1025 +249: 1025 +250: 1025 +251: 1025 +252: 1025 +253: 1025 +254: 1025 +255: 1025 +256: 745 +257: 881 +258: 865 +259: 881 +260: 1025 +261: 1025 +262: 1025 +263: 1025 +264: 993 +265: 1009 +266: 993 +267: 1009 +268: 1025 +269: 1025 +270: 1025 +271: 1025 +272: 1025 +273: 1025 +274: 1025 +275: 1025 +276: 1025 +277: 1025 +278: 1025 +279: 1025 +280: 1025 +281: 1025 +282: 1025 +283: 1025 +284: 1025 +285: 1025 +286: 1025 +287: 1025 +288: 993 +289: 1009 +290: 993 +291: 1009 +292: 1025 +293: 1025 +294: 1025 +295: 1025 +296: 993 +297: 1009 +298: 993 +299: 1009 +300: 1025 +301: 1025 +302: 1025 +303: 1025 +304: 1025 +305: 1025 +306: 1025 +307: 1025 +308: 1025 +309: 1025 +310: 1025 +311: 1025 +312: 1025 +313: 1025 +314: 1025 +315: 1025 +316: 1025 +317: 1025 +318: 1025 +319: 1025 +320: 881 +321: 1025 +322: 1009 +323: 1025 +324: 1025 +325: 1025 +326: 1025 +327: 1025 +328: 1009 +329: 1025 +330: 1009 +331: 1025 +332: 1025 +333: 1025 +334: 1025 +335: 1025 +336: 1025 +337: 1025 +338: 1025 +339: 1025 +340: 1025 +341: 1025 +342: 1025 +343: 1025 +344: 1025 +345: 1025 +346: 1025 +347: 1025 +348: 1025 +349: 1025 +350: 1025 +351: 1025 +352: 1009 +353: 1025 +354: 1009 +355: 1025 +356: 1025 +357: 1025 +358: 1025 +359: 1025 +360: 1009 +361: 1025 +362: 1009 +363: 1025 +364: 1025 +365: 1025 +366: 1025 +367: 1025 +368: 1025 +369: 1025 +370: 1025 +371: 1025 +372: 1025 +373: 1025 +374: 1025 +375: 1025 +376: 1025 +377: 1025 +378: 1025 +379: 1025 +380: 1025 +381: 1025 +382: 1025 +383: 1025 +384: 873 +385: 1009 +386: 993 +387: 1009 +388: 1025 +389: 1025 +390: 1025 +391: 1025 +392: 993 +393: 1009 +394: 993 +395: 1009 +396: 1025 +397: 1025 +398: 1025 +399: 1025 +400: 1025 +401: 1025 +402: 1025 +403: 1025 +404: 1025 +405: 1025 +406: 1025 +407: 1025 +408: 1025 +409: 1025 +410: 1025 +411: 1025 +412: 1025 +413: 1025 +414: 1025 +415: 1025 +416: 993 +417: 1009 +418: 993 +419: 1009 +420: 1025 +421: 1025 +422: 1025 +423: 1025 +424: 993 +425: 1009 +426: 993 +427: 1009 +428: 1025 +429: 1025 +430: 1025 +431: 1025 +432: 1025 +433: 1025 +434: 1025 +435: 1025 +436: 1025 +437: 1025 +438: 1025 +439: 1025 +440: 1025 +441: 1025 +442: 1025 +443: 1025 +444: 1025 +445: 1025 +446: 1025 +447: 1025 +448: 881 +449: 1025 +450: 1009 +451: 1025 +452: 1025 +453: 1025 +454: 1025 +455: 1025 +456: 1009 +457: 1025 +458: 1009 +459: 1025 +460: 1025 +461: 1025 +462: 1025 +463: 1025 +464: 1025 +465: 1025 +466: 1025 +467: 1025 +468: 1025 +469: 1025 +470: 1025 +471: 1025 +472: 1025 +473: 1025 +474: 1025 +475: 1025 +476: 1025 +477: 1025 +478: 1025 +479: 1025 +480: 1009 +481: 1025 +482: 1009 +483: 1025 +484: 1025 +485: 1025 +486: 1025 +487: 1025 +488: 1009 +489: 1025 +490: 1009 +491: 1025 +492: 1025 +493: 1025 +494: 1025 +495: 1025 +496: 1025 +497: 1025 +498: 1025 +499: 1025 +500: 1025 +501: 1025 +502: 1025 +503: 1025 +504: 1025 +505: 1025 +506: 1025 +507: 1025 +508: 1025 +509: 1025 +510: 1025 +511: 1025 +512: 741 +513: 873 +514: 857 +515: 873 +516: 1009 +517: 1009 +518: 1009 +519: 1009 +520: 977 +521: 993 +522: 977 +523: 993 +524: 1009 +525: 1009 +526: 1009 +527: 1009 +528: 1025 +529: 1025 +530: 1025 +531: 1025 +532: 1025 +533: 1025 +534: 1025 +535: 1025 +536: 1025 +537: 1025 +538: 1025 +539: 1025 +540: 1025 +541: 1025 +542: 1025 +543: 1025 +544: 977 +545: 993 +546: 977 +547: 993 +548: 1009 +549: 1009 +550: 1009 +551: 1009 +552: 977 +553: 993 +554: 977 +555: 993 +556: 1009 +557: 1009 +558: 1009 +559: 1009 +560: 1025 +561: 1025 +562: 1025 +563: 1025 +564: 1025 +565: 1025 +566: 1025 +567: 1025 +568: 1025 +569: 1025 +570: 1025 +571: 1025 +572: 1025 +573: 1025 +574: 1025 +575: 1025 +576: 881 +577: 1025 +578: 1009 +579: 1025 +580: 1025 +581: 1025 +582: 1025 +583: 1025 +584: 1009 +585: 1025 +586: 1009 +587: 1025 +588: 1025 +589: 1025 +590: 1025 +591: 1025 +592: 1025 +593: 1025 +594: 1025 +595: 1025 +596: 1025 +597: 1025 +598: 1025 +599: 1025 +600: 1025 +601: 1025 +602: 1025 +603: 1025 +604: 1025 +605: 1025 +606: 1025 +607: 1025 +608: 1009 +609: 1025 +610: 1009 +611: 1025 +612: 1025 +613: 1025 +614: 1025 +615: 1025 +616: 1009 +617: 1025 +618: 1009 +619: 1025 +620: 1025 +621: 1025 +622: 1025 +623: 1025 +624: 1025 +625: 1025 +626: 1025 +627: 1025 +628: 1025 +629: 1025 +630: 1025 +631: 1025 +632: 1025 +633: 1025 +634: 1025 +635: 1025 +636: 1025 +637: 1025 +638: 1025 +639: 1025 +640: 861 +641: 993 +642: 977 +643: 993 +644: 1009 +645: 1009 +646: 1009 +647: 1009 +648: 977 +649: 993 +650: 977 +651: 993 +652: 1009 +653: 1009 +654: 1009 +655: 1009 +656: 1025 +657: 1025 +658: 1025 +659: 1025 +660: 1025 +661: 1025 +662: 1025 +663: 1025 +664: 1025 +665: 1025 +666: 1025 +667: 1025 +668: 1025 +669: 1025 +670: 1025 +671: 1025 +672: 977 +673: 993 +674: 977 +675: 993 +676: 1009 +677: 1009 +678: 1009 +679: 1009 +680: 977 +681: 993 +682: 977 +683: 993 +684: 1009 +685: 1009 +686: 1009 +687: 1009 +688: 1025 +689: 1025 +690: 1025 +691: 1025 +692: 1025 +693: 1025 +694: 1025 +695: 1025 +696: 1025 +697: 1025 +698: 1025 +699: 1025 +700: 1025 +701: 1025 +702: 1025 +703: 1025 +704: 881 +705: 1025 +706: 1009 +707: 1025 +708: 1025 +709: 1025 +710: 1025 +711: 1025 +712: 1009 +713: 1025 +714: 1009 +715: 1025 +716: 1025 +717: 1025 +718: 1025 +719: 1025 +720: 1025 +721: 1025 +722: 1025 +723: 1025 +724: 1025 +725: 1025 +726: 1025 +727: 1025 +728: 1025 +729: 1025 +730: 1025 +731: 1025 +732: 1025 +733: 1025 +734: 1025 +735: 1025 +736: 1009 +737: 1025 +738: 1009 +739: 1025 +740: 1025 +741: 1025 +742: 1025 +743: 1025 +744: 1009 +745: 1025 +746: 1009 +747: 1025 +748: 1025 +749: 1025 +750: 1025 +751: 1025 +752: 1025 +753: 1025 +754: 1025 +755: 1025 +756: 1025 +757: 1025 +758: 1025 +759: 1025 +760: 1025 +761: 1025 +762: 1025 +763: 1025 +764: 1025 +765: 1025 +766: 1025 +767: 1025 +768: 745 +769: 881 +770: 865 +771: 881 +772: 1025 +773: 1025 +774: 1025 +775: 1025 +776: 993 +777: 1009 +778: 993 +779: 1009 +780: 1025 +781: 1025 +782: 1025 +783: 1025 +784: 1025 +785: 1025 +786: 1025 +787: 1025 +788: 1025 +789: 1025 +790: 1025 +791: 1025 +792: 1025 +793: 1025 +794: 1025 +795: 1025 +796: 1025 +797: 1025 +798: 1025 +799: 1025 +800: 993 +801: 1009 +802: 993 +803: 1009 +804: 1025 +805: 1025 +806: 1025 +807: 1025 +808: 993 +809: 1009 +810: 993 +811: 1009 +812: 1025 +813: 1025 +814: 1025 +815: 1025 +816: 1025 +817: 1025 +818: 1025 +819: 1025 +820: 1025 +821: 1025 +822: 1025 +823: 1025 +824: 1025 +825: 1025 +826: 1025 +827: 1025 +828: 1025 +829: 1025 +830: 1025 +831: 1025 +832: 881 +833: 1025 +834: 1009 +835: 1025 +836: 1025 +837: 1025 +838: 1025 +839: 1025 +840: 1009 +841: 1025 +842: 1009 +843: 1025 +844: 1025 +845: 1025 +846: 1025 +847: 1025 +848: 1025 +849: 1025 +850: 1025 +851: 1025 +852: 1025 +853: 1025 +854: 1025 +855: 1025 +856: 1025 +857: 1025 +858: 1025 +859: 1025 +860: 1025 +861: 1025 +862: 1025 +863: 1025 +864: 1009 +865: 1025 +866: 1009 +867: 1025 +868: 1025 +869: 1025 +870: 1025 +871: 1025 +872: 1009 +873: 1025 +874: 1009 +875: 1025 +876: 1025 +877: 1025 +878: 1025 +879: 1025 +880: 1025 +881: 1025 +882: 1025 +883: 1025 +884: 1025 +885: 1025 +886: 1025 +887: 1025 +888: 1025 +889: 1025 +890: 1025 +891: 1025 +892: 1025 +893: 1025 +894: 1025 +895: 1025 +896: 873 +897: 1009 +898: 993 +899: 1009 +900: 1025 +901: 1025 +902: 1025 +903: 1025 +904: 993 +905: 1009 +906: 993 +907: 1009 +908: 1025 +909: 1025 +910: 1025 +911: 1025 +912: 1025 +913: 1025 +914: 1025 +915: 1025 +916: 1025 +917: 1025 +918: 1025 +919: 1025 +920: 1025 +921: 1025 +922: 1025 +923: 1025 +924: 1025 +925: 1025 +926: 1025 +927: 1025 +928: 993 +929: 1009 +930: 993 +931: 1009 +932: 1025 +933: 1025 +934: 1025 +935: 1025 +936: 993 +937: 1009 +938: 993 +939: 1009 +940: 1025 +941: 1025 +942: 1025 +943: 1025 +944: 1025 +945: 1025 +946: 1025 +947: 1025 +948: 1025 +949: 1025 +950: 1025 +951: 1025 +952: 1025 +953: 1025 +954: 1025 +955: 1025 +956: 1025 +957: 1025 +958: 1025 +959: 1025 +960: 881 +961: 1025 +962: 1009 +963: 1025 +964: 1025 +965: 1025 +966: 1025 +967: 1025 +968: 1009 +969: 1025 +970: 1009 +971: 1025 +972: 1025 +973: 1025 +974: 1025 +975: 1025 +976: 1025 +977: 1025 +978: 1025 +979: 1025 +980: 1025 +981: 1025 +982: 1025 +983: 1025 +984: 1025 +985: 1025 +986: 1025 +987: 1025 +988: 1025 +989: 1025 +990: 1025 +991: 1025 +992: 1009 +993: 1025 +994: 1009 +995: 1025 +996: 1025 +997: 1025 +998: 1025 +999: 1025 +1000: 1009 +1001: 1025 +1002: 1009 +1003: 1025 +1004: 1025 +1005: 1025 +1006: 1025 +1007: 1025 +1008: 1025 +1009: 1025 +1010: 1025 +1011: 1025 +1012: 1025 +1013: 1025 +1014: 1025 +1015: 1025 +1016: 1025 +1017: 1025 +1018: 1025 +1019: 1025 +1020: 1025 +1021: 1025 +1022: 1025 +1023: 1025 +37456 diff --git a/semestr-4/aisd/pracownia4/brut.cpp b/semestr-4/aisd/pracownia4/brut.cpp new file mode 100644 index 0000000..32f4ebb --- /dev/null +++ b/semestr-4/aisd/pracownia4/brut.cpp @@ -0,0 +1,69 @@ +#include +using namespace std; +typedef long long ll; + +struct insert_list { + vector v; + + insert_list() { + } + + void insert(int p, int val) { + assert(p <= v.size()); + assert(p >= 0); + vector temp; + for (int i = 0; i < p; i++) { + temp.push_back(v[i]); + } + temp.push_back(val); + for (int i = p; i < v.size(); i++) { + temp.push_back(v[i]); + } + v = temp; + } + + void erase(int p) { + assert(p <= v.size()); + assert(p >= 1); + vector temp; + for (int i = 0; i < p-1; i++) { + temp.push_back(v[i]); + } + for (int i = p; i < v.size(); i++) { + temp.push_back(v[i]); + } + v = temp; + } + + ll sum(int l, int r) { + ll ans = 0; + for (int i = l-1; i < r; i++) { + ans += v[i]; + } + return ans; + } +}; + +insert_list v; + +int main() { + ios_base::sync_with_stdio(false); + cin.tie(); + int n; + cin >> n; + for (int i = 0; i < n; i++) { + char c; + cin >> c; + if (c == 'D') { + int a; + cin >> a; + v.erase(a); + } + else { + int a, b; + cin >> a >> b; + if (c == 'I') v.insert(a, b); + else cout << v.sum(a,b) << "\n"; + } + } +} \ No newline at end of file diff --git a/semestr-4/aisd/pracownia4/gen.py b/semestr-4/aisd/pracownia4/gen.py new file mode 100644 index 0000000..733a60e --- /dev/null +++ b/semestr-4/aisd/pracownia4/gen.py @@ -0,0 +1,24 @@ +from random import randint, seed, choice +import sys + + +seed(sys.argv[1]) +n = int(sys.argv[2]) +l = 0 +print(n) + + +for i in range(n): + c = choice('ISD') + if l == 0: + c = 'I' + + if c == 'D': + print(c, randint(1, l)) + l -= 1 + elif c == 'I': + print(c, randint(0, l), randint(-10, 10)) + l += 1 + else: + a = randint(1, l) + print(c, a, randint(a, l)) \ No newline at end of file diff --git a/semestr-4/aisd/pracownia4/rozw.cpp b/semestr-4/aisd/pracownia4/rozw.cpp new file mode 100644 index 0000000..9c314e2 --- /dev/null +++ b/semestr-4/aisd/pracownia4/rozw.cpp @@ -0,0 +1,157 @@ +#include +using namespace std; +typedef long long ll; + +const int K = 20; +const int M = (1<= 0; d--) { + int maks = (1< queries; +map q_to_pos; +kox_set secik; +kox_set pstree; + + +int main() { + int n, inserts = 0; + scanf("%d", &n); + for (int i = 0; i < n; ++i) { + char c; + scanf(" %c", &c); + query q; + q.type = c; + if (c == 'D') { + int a; + scanf("%d", &a); + pstree.add(a); + q.info.del = a; + } + else { + int a, b; + scanf("%d%d", &a, &b); + q.type = c; + if (c == 'I') { + q.info.insert = {a, b}; + inserts++; + } else { + q.info.sum = {a, b}; + } + } + queries.push_back(q); + } + + secik.fill(1); + for (int i = n-1; i >= 0; i--) { + query q = queries[i]; + if (q.type == 'D') { + pstree.del(q.info.del); + } + if (q.type == 'I') { + int offset = pstree.sum(0, q.info.insert.p); + int kth = secik.kth_elem(q.info.insert.p + offset + 1); + secik.del(kth); + q_to_pos[i] = kth; + cout << q.info.insert.p << " " << offset << "\n"; + cout << i << ": " << q_to_pos[i] << "\n"; + } + } + secik.fill(0); + pstree.fill(0); + + for (int i = 0; i < n; i++) { + query q = queries[i]; + if (q.type == 'I') { + secik.add(q_to_pos[i]); + pstree.update(q_to_pos[i], q.info.insert.x); + // cout << "Inserting " << q.info.insert.x << " to " << q_to_pos[i] << "\n"; + } + if (q.type == 'D') { + int pos = secik.kth_elem(q.info.del); + // cout << "kth: " << q.info.del << " " << pos << "\n"; + secik.del(pos); + pstree.update(pos, -pstree.tree[pos + M]); + } + if (q.type == 'S') { + int from = secik.kth_elem(q.info.sum.from); + int to = secik.kth_elem(q.info.sum.to); + printf("%lld\n", pstree.sum(from, to)); + } + } +} \ No newline at end of file diff --git a/semestr-4/aisd/pracownia4/rozw2.cpp b/semestr-4/aisd/pracownia4/rozw2.cpp new file mode 100644 index 0000000..17562a9 --- /dev/null +++ b/semestr-4/aisd/pracownia4/rozw2.cpp @@ -0,0 +1,135 @@ +#include +using namespace std; + +struct treap { + typedef long long T; + treap *left = nullptr; + treap *right = nullptr; + int rank, items = 1; + T value; + T sum; + bool rev = false; + + treap(T val = T()) : rank(rand()), value(val), sum(val) {} + + inline void update() { + if (rev) { + swap(left, right); + if (left) left->rev = !left->rev; + if (right) right->rev = !right->rev; + rev = false; + } + } +}; + +inline int items(treap *t) { return t ? t->items : 0; } +inline int sum(treap *t) { return t ? t->sum : 0; } +inline void recalc(treap *t) { + t->items = items(t->left) + items(t->right) + 1; + t->sum = sum(t->left) + sum(t->right) + t->value; +} + +pair split(treap *t, int k) { + if (!t) return {nullptr, nullptr}; + t->update(); + if (items(t->left) < k) { + auto p = split(t->right, k - items(t->left) - 1); + t->right = p.first; + recalc(t); + return {t, p.second}; + } + else { + auto p = split(t->left, k); + t->right = p.first; + recalc(t); + return {p.first, t}; + } +} + +treap* merge(treap *a, treap *b) { + if (!a) return b; + if (!b) return a; + a->update(); + b->update(); + if (a->rank > b->rank) { + a->right = merge(a->right, b); + recalc(a); + return a; + } + else { + b->left = merge(a, b->left); + recalc(b); + return b; + } +} + +treap::T select(treap *t, int k) { + if (!t) return treap::T(); + t->update(); + int i = items(t->left); + if (i == k) return t->value; + else if (i > k) return select(t->left, k); + else return select(t->right, k - i - 1); +} + +treap *insert (treap *t, treap::T val, int k) { + auto p = split(t, k); + return merge(merge(p.first, new treap(val)), p.second); +} + +treap *erase(treap *t, int k) { + auto p1 = split(t, k); + auto p2 = split(p1.second, 1); + return merge(p1.first, p2.second); +} + +treap::T sum(treap *t, int l, int r) { + auto p1 = split(t, r); + auto p2 = split(p1.first, l); + return sum(p2.second); +} + +void write(treap *t) { + if (!t) return; + t->update(); + write(t->left); + cout << t->value << " "; + write(t->right); +} +void destroy(treap *t) { + if (!t) return; + destroy(t->left); + destroy(t->right); + delete t; +} + +treap *t = 0; + +int main() { + int n; + scanf("%d", &n); + for (int i = 0; i < n; i++) { + char c; + scanf(" %c", &c); + if (c == 'I') { + int p, x; + scanf("%d%d", &p, &x); + t = insert(t, x, p); + } + if (c == 'D') { + int p; + scanf("%d", &p); + t = erase(t, p - 1); + } + if (c == 'S') { + int l, r; + scanf("%d%d", &l, &r); + printf("ans: %lld\n", sum(t, l, r)); + } + cout << "Treap:\n"; + write(t); + cout << "\n"; + } + + destroy(t); +} \ No newline at end of file diff --git a/semestr-4/aisd/pracownia4/rozw3.cpp b/semestr-4/aisd/pracownia4/rozw3.cpp new file mode 100644 index 0000000..ec107ef --- /dev/null +++ b/semestr-4/aisd/pracownia4/rozw3.cpp @@ -0,0 +1,149 @@ + +#include +using namespace std; + +struct treap +{ + typedef long long T; + treap *left = nullptr, *right = nullptr; + + int rank, items = 1; + bool rev = false; + T value, sum; + + treap(T val = T()) : value(val), sum(val), rank(rand()) { } + + inline void update() + { + if(rev) + { + swap(left, right); + if(left) left->rev = !left->rev; + if(right) right->rev = !right->rev; + rev = false; + } + } +}; + +inline int items(treap *t) { return t ? t->items : 0; } +inline treap::T sum(treap *t) { return t ? t->sum : 0; } +inline void recalc(treap *t) { + t->items = items(t->left) + items(t->right) + 1; + t->sum = sum(t->left) + sum(t->right) + t->value; +} + +pair split(treap *t, int k) //dzieli na prefiks dlugosci k i reszte +{ + if(!t) return make_pair(nullptr, nullptr); + //t = new treap(*t); //odkomentowac zeby zrobic strukture trwala + t->update(); + if(items(t->left) < k) + { + auto p = split(t->right, k - items(t->left) - 1); + t->right = p.first; + recalc(t); + return make_pair(t, p.second); + } + else + { + auto p = split(t->left, k); + t->left = p.second; + recalc(t); + return make_pair(p.first, t); + } +} + +treap* merge(treap *a, treap *b) +{ + if(!a) return b; + if(!b) return a; + a->update(); + b->update(); + if(a->rank > b->rank) { + a->right = merge(a->right, b); + recalc(a); + return a; + } + else { + b->left = merge(a, b->left); + recalc(b); + return b; + } +} + +treap::T select(treap *t, int k) //zwraca k-ty element +{ + if(!t) return treap::T(); + t->update(); + int i = items(t->left); + if(i == k) return t->value; + if(i > k) return select(t->left, k); + return select(t->right, k - i - 1); +} + +treap* insert(treap *t, treap::T val, int k) //wstaw val na pozycje k (liczac od 0) +{ + auto p = split(t, k); + return merge(merge(p.first, new treap(val)), p.second); +} +void write(treap *t) +{ + if(!t) return; + t->update(); + write(t->left); + cout << "(" << t->value << ", " << t->sum << ") "; + write(t->right); +} + +treap* erase(treap *t, int k) +{ + auto p1 = split(t, k); + auto p2 = split(p1.second, 1); + return merge(p1.first, p2.second); +} + +treap* reverse(treap *t, int a, int b) //odwroc przedzial rev = !p2.second->rev; + return merge(merge(p2.first, p2.second), p1.second); +} + +treap::T sum(treap* t, int l, int r) { + auto p1 = split(t, r); + auto p2 = split(p1.first, l); + treap::T ret = sum(p2.second); + merge(merge(p2.first, p2.second), p1.second); + return ret; +} + +treap *root = 0; + +int main() { + int n; + scanf("%d", &n); + for (int i = 0; i < n; i++) { + char c; + scanf(" %c", &c); + if (c == 'I') { + int p, x; + scanf("%d%d", &p, &x); + root = insert(root, x, p); + } + if (c == 'D') { + int p; + scanf("%d", &p); + root = erase(root, p - 1); + } + if (c == 'S') { + int l, r; + scanf("%d%d", &l, &r); + printf("%lld\n", sum(root, l - 1, r)); + } + // cout << "Treap:\n"; + // write(root); + // cout << "\n"; + } + +} \ No newline at end of file diff --git a/semestr-4/aisd/pracownia4/show_problem.pdf b/semestr-4/aisd/pracownia4/show_problem.pdf new file mode 100644 index 0000000..8a1c155 Binary files /dev/null and b/semestr-4/aisd/pracownia4/show_problem.pdf differ diff --git a/semestr-4/aisd/pracownia4/test.sh b/semestr-4/aisd/pracownia4/test.sh new file mode 100755 index 0000000..dc725ad --- /dev/null +++ b/semestr-4/aisd/pracownia4/test.sh @@ -0,0 +1,21 @@ +#!/bin/bash + +make brut +make rozw3 + + +for i in {1..10000} +do + echo $i + python3 gen.py $i $1 > test.in + ./rozw3 < test.in > wa.out + ./brut < test.in > test.out + + if diff -w test.out wa.out + then + echo ok + else + echo nieok + break + fi +done diff --git a/semestr-4/aisd/pracownia5/gen.py b/semestr-4/aisd/pracownia5/gen.py new file mode 100644 index 0000000..85d332c --- /dev/null +++ b/semestr-4/aisd/pracownia5/gen.py @@ -0,0 +1,40 @@ +import random +import sys + +random.seed(sys.argv[1]) + +n = int(sys.argv[2]) +maxcoord = 200 + + +print(n) +for i in range(n): + ty = random.randint(0, 3) + a, b = 0, 0 + y1, y2 = 0, 0 + if ty == 0: + a = random.randint(0, maxcoord) + b = random.randint(a+1, maxcoord + 1) + y1 = random.randint(0, maxcoord) + y2 = y1 + if ty == 1: + y1 = random.randint(0, maxcoord) + y2 = random.randint(a+1, maxcoord + 1) + a = random.randint(0, maxcoord) + b = a + if ty == 2: + a = random.randint(0, maxcoord) + b = random.randint(0, maxcoord) + x = random.randint(1, maxcoord) + y1 = b + b = a + x + y2 = y1 + x + if ty == 3: + a = random.randint(0, maxcoord) + b = random.randint(0, maxcoord) + x = random.randint(1, maxcoord) + y1 = b + b = a + x + y2 = y1 - x + + print(a, y1, b, y2) diff --git a/semestr-4/aisd/pracownia5/t.tin b/semestr-4/aisd/pracownia5/t.tin new file mode 100644 index 0000000..e69de29 diff --git a/semestr-4/aisd/pracownia5/wzo.cpp b/semestr-4/aisd/pracownia5/wzo.cpp new file mode 100644 index 0000000..d4aa4fa --- /dev/null +++ b/semestr-4/aisd/pracownia5/wzo.cpp @@ -0,0 +1,288 @@ +#include +using namespace std; + +#define VER_T 1 +#define HOR_T 0 + +#define BEG 0 +#define END 1 + +struct event { + int x, y, z; + bool t; + event(int _x=0, bool _t=false, int _y=0, int _z=0) : x(_x), y(_y), z(_z), t(_t) {} + + bool operator < (const event &e) const { + if (x == e.x) { + if (t == e.t) return make_pair(y, z) < make_pair(e.y, e.z); + if (t == HOR_T) return z == BEG; + if (e.t == HOR_T) return e.z == END; + return t < e.t; + // if (t == HOR_T && z == BEG) return true; + // else if (t == HOR_T) return false; + // else if (e.t == HOR_T && e.z == BEG) return false; + // else if (e.t == HOR_T) return true; + // return (make_pair(y,z) < make_pair(e.y, e.z)); + } + return x < e.x; + // return make_pair(x, make_pair(t, make_pair(y, z))) < make_pair(e.x, make_pair(e.t, make_pair(e.y, e.z))); + } + +}; + +struct pnt { + int x, y; + + pnt(int _x=0, int _y=0) : x(_x), y(_y) {} + + void transpoze(int a11, int a12, int a21, int a22) { + int temp = x*a11 + y*a12; + y = x*a21 + y*a22; + x = temp; + } + bool operator == (const pnt &p) { + return (x==p.x && y == p.y); + } + +}; + +struct seg { + pnt st, nd; + + seg(pnt p1=pnt(), pnt p2=pnt()) : st(p1), nd(p2) {} + + void transpoze(int a11, int a12, int a21, int a22) { + st.transpoze(a11, a12, a21, a22); + nd.transpoze(a11, a12, a21, a22); + } +}; + +inline int sig(int x) { + if (x < 0) return -1; + if (x == 0) return 0; + if (x > 0) return 1; +} + +void swap(pnt &x, pnt &y) { + swap(x.x, y.x); + swap(x.y, y.y); +} + +vector events; +map points; + +void get_cross_pnts(vector &result, vector &hor, vector &ver) { + events.resize(0); + points.clear(); + // cout << "h:\n"; + for (auto &s: hor) { + if (s.st.x > s.nd.x) swap(s.st, s.nd); + // cout << s.st.x << " " << s.st.y << ", " << s.nd.x << " " << s.nd.y << "\n"; + events.push_back(event(s.st.x, HOR_T, s.st.y, BEG)); + events.push_back(event(s.nd.x, HOR_T, s.st.y, END)); + } + // cout << "v:\n"; + for (auto &s: ver) { + if (s.st.y > s.nd.y) swap(s.st, s.nd); + // cout << s.st.x << " " << s.st.y << ", " << s.nd.x << " " << s.nd.y << "\n"; + + events.push_back(event(s.st.x, VER_T, s.st.y, s.nd.y)); + } + + sort(events.begin(), events.end()); + for (auto e: events) { + // cout << e.x << " " << (e.t == HOR_T ? "hor " : "ver ") << e.y << " " << (e.t == HOR_T ? (e.z == BEG ? "beg" : "end") : to_string(e.z)) << "\n"; + if (e.t == HOR_T) { + if (e.z == BEG) points[e.y]++; + else { + if (--points[e.y] == 0) points.erase(e.y); + } + } + else { + auto it = points.lower_bound(e.y); + while (it != points.end() && it->first <= e.z) { + result.push_back(pnt(e.x, it->first)); + it++; + } + } + } + // cout << "done\n"; +} + +vector temp; +vector hor, ver, cross_left, cross_right; + +void read() { + int n; + // cin >> n; + scanf("%d", &n); + for (int i = 0; i < n; i++) { + int x1, y1, x2, y2; + // cin >> x1 >> y1 >> x2 >> y2; + scanf("%d%d%d%d", &x1, &y1, &x2, &y2); + seg s = seg(pnt(x1, y1), pnt(x2, y2)); + if (y1 == y2) + hor.push_back(s); + else if (x1 == x2) + ver.push_back(s); + else if (sig(x1 - x2) == sig(y1 - y2)) + cross_right.push_back(s); + else + cross_left.push_back(s); + } +} + +void hor_ver(vector &result) { + // cout << "hor_ver\n"; + + temp.clear(); + get_cross_pnts(temp, hor, ver); + for (auto p: temp) result.push_back(p); +} + +void hor_c_r(vector &result) { + // cout << "hor_cr\n"; + temp.clear(); + for (auto &p: hor) p.transpoze(1, -1, 0, 1); + for (auto &p: cross_right) p.transpoze(1, -1, 0, 1); + get_cross_pnts(temp, hor, cross_right); + for (auto &p: hor) p.transpoze(1, 1, 0, 1); + for (auto &p: cross_right) p.transpoze(1, 1, 0, 1); + + for (auto &p: temp) { + p.transpoze(1, 1, 0, 1); + result.push_back(p); + } +} + +void hor_c_l(vector &result) { + // cout << "hor_cl\n"; + temp.clear(); + for (auto &p: hor) p.transpoze(1, 1, 0, 1); + for (auto &p: cross_left) p.transpoze(1, 1, 0, 1); + + get_cross_pnts(temp, hor, cross_left); + + for (auto &p: hor) p.transpoze(1, -1, 0, 1); + for (auto &p: cross_left) p.transpoze(1, -1, 0, 1); + + for (auto &p: temp) { + p.transpoze(1, -1, 0, 1); + result.push_back(p); + } +} + +void ver_c_r(vector &result) { + // cout << "ver_cr\n"; + + temp.clear(); + for (auto &p: ver) { + p.transpoze(1, 0, -1, 1); + } + for (auto &p: cross_right) { + p.transpoze(1, 0, -1, 1); + } + + get_cross_pnts(temp, cross_right, ver); + + for (auto &p: ver) { + p.transpoze(1, 0, 1, 1); + } + for (auto &p: cross_right) { + p.transpoze(1, 0, 1, 1); + } + + for (auto &p: temp) { + p.transpoze(1, 0, 1, 1); + result.push_back(p); + } +} + +void ver_c_l(vector &result) { + // cout << "ver_cl\n"; + + temp.clear(); + for (auto &p: ver) { + p.transpoze(-1, 0, 1, 1); + } + for (auto &p: cross_left) { + p.transpoze(-1, 0, 1, 1); + } + + get_cross_pnts(temp, cross_left, ver); + for (auto &p: ver) { + p.transpoze(-1, 0, 1, 1); + } + for (auto &p: cross_left) { + p.transpoze(-1, 0, 1, 1); + } + + for (auto &p: temp) { + p.transpoze(-1, 0, 1, 1); + result.push_back(p); + } +} + +void c_l_c_r(vector &result) { + temp.clear(); + // cout << "cl_cr\n"; + for (auto &p: cross_right) { + // cout << p.st.x << " " << p.st.y << ", " << p.nd.x << " " << p.nd.y << "\n"; + p.transpoze(1, 1, -1, 1); + } + // cout << "---\n"; + for (auto &p: cross_left) { + // cout << p.st.x << " " << p.st.y << ", " << p.nd.x << " " << p.nd.y << "\n"; + p.transpoze(1, 1, -1, 1); + } + + get_cross_pnts(temp, cross_right, cross_left); + + for (auto &p: ver) { + p.transpoze(1, -1, 1, 1); + } + for (auto &p: cross_left) { + p.transpoze(1, -1, 1, 1); + } + + for (auto &p: temp) { + p.transpoze(1, -1, 1, 1); + result.push_back(p); + } +} + +void solve() { + // cout << hor.size() << " " << ver.size() << " " << cross_left.size() << " " << cross_right.size() << "\n"; + vector result; + hor_ver(result); + hor_c_r(result); + hor_c_l(result); + ver_c_r(result); + ver_c_l(result); + for (auto &p: result) { + p.x *= 2; + p.y *= 2; + } + c_l_c_r(result); + + sort(result.begin(), result.end(), [&](const pnt &p1, const pnt &p2) { + if (p1.x == p2.x) return p1.y < p2.y; + return p1.x < p2.x; + }); + result.erase(unique(result.begin(), result.end()), result.end()); + + printf("%d\n", result.size()); + for (auto p : result) { + printf("%d.%s ", p.x/2, (p.x % 2 == 1 ? "5" : "0")); + printf("%d.%s\n", p.y/2, (p.y % 2 == 1 ? "5" : "0")); + // cout << p.x/2 << "." << (p.x % 2 == 1 ? "5" : "0") << " "; + // cout << p.y/2 << "." << (p.y % 2 == 1 ? "5" : "0") << "\n"; + } +} + +int main() { + // ios_base::sync_with_stdio(false); + // cin.tie(); + read(); + solve(); +} diff --git a/semestr-4/aisd/pracownia5/wzo2.cpp b/semestr-4/aisd/pracownia5/wzo2.cpp new file mode 100644 index 0000000..b4e9ac3 --- /dev/null +++ b/semestr-4/aisd/pracownia5/wzo2.cpp @@ -0,0 +1,184 @@ +#include +using namespace std; + +/* +[0 -1] +[1 0] +*/ + +struct pnt { + int x, y; + pnt (int _x=0, int _y=0) : x(_x), y(_y) {} + void transpose(int a11, int a12, int a21, int a22) { + int temp = x*a11 + y*a12; + y = x*a21 + y*a22; + x = temp; + } + bool operator<(const pnt &p) const { + if (p.x == x) return y < p.y; + return x < p.x; + } + bool operator==(const pnt &p) const { + return (x == p.x && y == p.y); + } +}; + +struct seg { + pnt st, nd; + seg(pnt p1=pnt(), pnt p2=pnt()) : st(p1), nd(p2) {} + void transpose(int a11, int a12, int a21, int a22) { + st.transpose(a11, a12, a21, a22); + nd.transpose(a11, a12, a21, a22); + } +}; + +#define HOR_T 0 +#define VER_T 1 +#define CL_T 2 +#define CR_T 3 +#define BEG 0 +#define END 1 + +struct event { + int x; + int t; + int i1, i2; + + event(int _x, int _t, int _i1, int _i2) : x(_x), t(_t), i1(_i1), i2(_i2) {} + + bool operator < (const event &e) const { + if (x == e.x) { + if (t == e.t) return make_pair(i1, i2) < make_pair(e.i1, e.i2); + if (t == HOR_T) return (e.i2 == END); + if (e.t == HOR_T) return (i2 == BEG); + return t < e.t; + } + return x < e.x; + } +}; + +inline void swap(pnt &p1, pnt &p2) { + swap(p1.x, p2.x); + swap(p1.y, p2.y); +} + +vector segments; +vector result; +vector temp_res; +vector events; +map hor; +map cl; +map cr; + +void read() { + int n; + scanf("%d", &n); + segments.resize(n); + for (int i = 0; i < n; i++) { + cin >> segments[i].st.x >> segments[i].st.y >> segments[i].nd.x >> segments[i].nd.y; + } +} + +void rotate(int a11, int a12, int a21, int a22) { + for (auto s: segments) { + s.transpose(a11, a12, a21, a22); + } +} + +void solve_prob() { + temp_res.clear(); + events.clear(); + hor.clear(); cl.clear(); cr.clear(); + + for (auto s: segments) { + if (s.st.x > s.nd.x) swap(s.st, s.nd); + if (s.st.x == s.nd.x) { + if (s.st.y > s.nd.y) swap(s.st, s.nd); + events.push_back(event(s.st.x, VER_T, s.st.y, s.nd.y)); + } + else if (s.st.y == s.nd.y) { + events.push_back(event(s.st.x, HOR_T, s.st.y, BEG)); + events.push_back(event(s.nd.x, HOR_T, s.st.y, END)); + } + else if (s.st.y - s.nd.y < 0) { + events.push_back(event(s.st.x, CR_T, s.st.y, BEG)); + events.push_back(event(s.nd.x, CR_T, s.nd.y, END)); + } + else { + events.push_back(event(s.st.x, CL_T, s.st.y, BEG)); + events.push_back(event(s.nd.x, CL_T, s.nd.y, END)); + } + } + + sort(events.begin(), events.end()); + for (auto e: events) { + if (e.t == VER_T) { + auto it = hor.lower_bound(e.i1); + while (it != hor.end() && it->first <= e.i2) { + temp_res.push_back({e.x, it->first}); + it++; + } + it = cr.lower_bound(e.i1 - e.x); + while (it != cr.end() && it->first <= e.i2 - e.x) { + temp_res.push_back({e.x, it->first + e.x}); + it++; + } + it = cl.lower_bound(e.i1 + e.x); + while (it != cl.end() && it->first <= e.i2 + e.x) { + temp_res.push_back({e.x, it->first - e.x}); + it++; + } + } + if (e.t == CR_T) { + if (e.i2 == BEG) cr[e.i1 - e.x]++; + else if (--cr[e.i1 - e.x] <= 0) cr.erase(e.i1 - e.x); + } + if (e.t == CL_T) { + if (e.i2 == BEG) cl[e.i1 + e.x]++; + else if (--cl[e.i1 + e.x] <= 0) cl.erase(e.i1); + } + if (e.t == HOR_T) { + if (e.i2 == BEG) hor[e.i1]++; + else if (--hor[e.i1] <= 0) hor.erase(e.i1); + } + } +} + +void add_to_res(int a11, int a12, int a21, int a22) { + for (auto p: temp_res) { + p.transpose(a11, a12, a21, a22); + result.push_back(p); + } +} + +void solve() { + solve_prob(); + for (auto &p: temp_res) { + p.x *= 2; p.y *= 2; + } + add_to_res(1, 0, 0, 1); + for (auto &p: temp_res) { + p.x /= 2; p.y /= 2; + } + rotate(1, -1, 1, 1); + solve_prob(); + add_to_res(1, 1, -1, 1); + rotate(1, 1, -1, 1); + for (auto &p: temp_res) { + p.x /= 2; p.y /= 2; + } + + + + sort(result.begin(), result.end()); + result.erase(unique(result.begin(), result.end()), result.end()); + for (auto p : result) { + cout << p.x/2 << "." << (p.x % 2 == 1 ? "5" : "0") << " "; + cout << p.y/2 << "." << (p.y % 2 == 1 ? "5" : "0") << "\n"; + } +} + +int main() { + read(); + solve(); +} \ No newline at end of file diff --git a/semestr-4/aisd/pracownia6/wzo.cpp b/semestr-4/aisd/pracownia6/wzo.cpp new file mode 100644 index 0000000..f13f0ec --- /dev/null +++ b/semestr-4/aisd/pracownia6/wzo.cpp @@ -0,0 +1,51 @@ +#include +using namespace std; + +const int N = 1e6 + 10; +bool vis[N]; +int n, m, ranga[N], par[N]; +pair> G[N]; + +int Find(int v) { + if (par[v] == v) return v; + return par[v] = Find(par[v]); +} + +void Union(int v, int u) { + if (ranga[v] > ranga[u]) { + par[u] = v; + } + else { + if (ranga[v] == ranga[u]) ranga[u]++; + par[v] = u; + } +} + +bool traj(int maks) { + +} + +int main() { + scanf("%d%d", &n, &m); + for (int i = 0; i < m; i++) { + int a, b, w; + scanf("%d%d%d", &a, &b, &w); + G[i] = {-w, {a,b}}; + } + sort(G, G+m); + for (int i = 1; i <= n; i++) { + par[i] = i; + ranga[i] = 0; + } + int mini = 1e9; + for (int i = 0; i < m; i++) { + int a = G[i].second.first; + int b = G[i].second.second; + a = Find(a); b = Find(b); + if (a != b) { + Union(a, b); + mini = min(mini, -G[i].first); + } + } + printf("%d\n", mini); +} \ No newline at end of file diff --git a/semestr-4/aisd/themis/AISDDEBIUT21.cpp b/semestr-4/aisd/themis/AISDDEBIUT21.cpp new file mode 100644 index 0000000..3666d69 --- /dev/null +++ b/semestr-4/aisd/themis/AISDDEBIUT21.cpp @@ -0,0 +1,24 @@ +/* + * Autor: Franciszek Malinka + * Numer indeksu: 316093 + * Prowadzący: WJA + */ + +#include +using namespace std; + +int main() +{ + ios_base::sync_with_stdio(false); + cin.tie(); + int a, b; + cin >> a >> b; + for (int i = a; i <= b; i++) + { + if (i % 2021 == 0) + { + cout << i << " "; + } + } + cout << "\n"; +} \ No newline at end of file diff --git a/semestr-4/aisd/themis/AISDPOTEGOWANIE.cpp b/semestr-4/aisd/themis/AISDPOTEGOWANIE.cpp new file mode 100644 index 0000000..c1b76fe --- /dev/null +++ b/semestr-4/aisd/themis/AISDPOTEGOWANIE.cpp @@ -0,0 +1,29 @@ +#include +using namespace std; + +int fast_pow(int a, int b, int m) +{ + if (b == 0) + { + return 1; + } + long long p = fast_pow(a, b / 2, m); + p = (p * p) % m; + if (b % 2 == 0) + return (int)p; + return (p * (long long)a) % m; +} + +int main() +{ + ios_base::sync_with_stdio(false); + cin.tie(); + int t; + cin >> t; + while (t--) + { + int a, b, m; + cin >> a >> b >> m; + cout << fast_pow(a, b, m) << "\n"; + } +} \ No newline at end of file diff --git a/semestr-4/aisd/themis/BELLMAN.cpp b/semestr-4/aisd/themis/BELLMAN.cpp new file mode 100644 index 0000000..5a65096 --- /dev/null +++ b/semestr-4/aisd/themis/BELLMAN.cpp @@ -0,0 +1,55 @@ +#include +using namespace std; + +const int N = 503; +int dist[N]; +vector>> edges; +int main() +{ + ios_base::sync_with_stdio(false); + cin.tie(); + int n, m, s; + cin >> n >> m >> s; + for (int i = 0; i <= n; i++) + { + dist[i] = 2e9; + } + dist[s] = 0; + for (int i = 0; i < m; i++) + { + int u, v, w; + cin >> u >> v >> w; + edges.push_back({w, {u, v}}); + // edges.push_back({w, {v, u}}); + } + + for (int i = 0; i < n + 1; i++) + { + for (auto e : edges) + { + int w = e.first; + int u = e.second.first; + int v = e.second.second; + if (dist[v] > dist[u] + w) + { + dist[v] = dist[u] + w; + } + } + } + for (auto e : edges) + { + int w = e.first; + int u = e.second.first; + int v = e.second.second; + if (dist[v] > dist[u] + w) + { + cout << "NIE\n"; + return 0; + } + } + for (int i = 0; i < n; i++) + { + if (i != s && dist[i] < 1e9) + cout << i << " " << dist[i] << "\n"; + } +} \ No newline at end of file diff --git a/semestr-4/aisd/themis/FIB.cpp b/semestr-4/aisd/themis/FIB.cpp new file mode 100644 index 0000000..dd38c5c --- /dev/null +++ b/semestr-4/aisd/themis/FIB.cpp @@ -0,0 +1,58 @@ +#include +using namespace std; +typedef long long ll; + +class matrix +{ +public: + ll a, b, c, d; + static ll m; + + matrix(ll _a = 0, ll _b = 0, ll _c = 0, ll _d = 0) : a(_a), b(_b), c(_c), d(_d) {} + + matrix operator*(const matrix &M) const + { + matrix res; + res.a = (a * M.a + b * M.c) % m; + res.b = (a * M.b + b * M.d) % m; + res.c = (c * M.a + d * M.c) % m; + res.d = (c * M.b + d * M.d) % m; + return res; + } +}; + +ll matrix::m = 1; + +matrix fast_pow(matrix M, int w) +{ + matrix res(1, 0, 0, 1); + while (w) + { + if (w % 2 == 1) + res = res * M; + M = M * M; + w >>= 1; + } + return res; +} + +void solve() +{ + int n, m; + cin >> n >> m; + matrix M(0, 1, 1, 1); + matrix::m = m; + cout << fast_pow(M, n + 1).a << "\n"; +} + +int main() +{ + ios_base::sync_with_stdio(false); + cin.tie(); + int t; + cin >> t; + while (t--) + { + solve(); + } +} \ No newline at end of file diff --git a/semestr-4/aisd/wyklady/Notatka 1 - Preliminaria.pdf b/semestr-4/aisd/wyklady/Notatka 1 - Preliminaria.pdf new file mode 100644 index 0000000..dc4ee1c Binary files /dev/null and b/semestr-4/aisd/wyklady/Notatka 1 - Preliminaria.pdf differ diff --git a/semestr-4/aisd/wyklady/Notatka 2 - Kopiec.pdf b/semestr-4/aisd/wyklady/Notatka 2 - Kopiec.pdf new file mode 100644 index 0000000..c8e76a7 Binary files /dev/null and b/semestr-4/aisd/wyklady/Notatka 2 - Kopiec.pdf differ diff --git "a/semestr-4/aisd/wyklady/Notatka 3 - Zach\305\202any.pdf" "b/semestr-4/aisd/wyklady/Notatka 3 - Zach\305\202any.pdf" new file mode 100644 index 0000000..5403789 Binary files /dev/null and "b/semestr-4/aisd/wyklady/Notatka 3 - Zach\305\202any.pdf" differ diff --git a/semestr-4/aisd/wyklady/Notatka 4 - divide and conquer.pdf b/semestr-4/aisd/wyklady/Notatka 4 - divide and conquer.pdf new file mode 100644 index 0000000..205b505 Binary files /dev/null and b/semestr-4/aisd/wyklady/Notatka 4 - divide and conquer.pdf differ diff --git a/semestr-4/aisd/wyklady/Notatka 5 - divide and conquer cd.pdf b/semestr-4/aisd/wyklady/Notatka 5 - divide and conquer cd.pdf new file mode 100644 index 0000000..48fc8e4 Binary files /dev/null and b/semestr-4/aisd/wyklady/Notatka 5 - divide and conquer cd.pdf differ diff --git a/semestr-4/aisd/wyklady/Notatka 6 - Programowanie Dynamiczne.pdf b/semestr-4/aisd/wyklady/Notatka 6 - Programowanie Dynamiczne.pdf new file mode 100644 index 0000000..d8b61ce Binary files /dev/null and b/semestr-4/aisd/wyklady/Notatka 6 - Programowanie Dynamiczne.pdf differ diff --git a/semestr-4/aisd/wyklady/Notatka 7 - Programowanie Dynamiczne cd.pdf b/semestr-4/aisd/wyklady/Notatka 7 - Programowanie Dynamiczne cd.pdf new file mode 100644 index 0000000..7040119 Binary files /dev/null and b/semestr-4/aisd/wyklady/Notatka 7 - Programowanie Dynamiczne cd.pdf differ -- cgit v1.2.3