Duzy commit ze smieciami

49 files changed, 2973 insertions, 0 deletions

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
--- /dev/null
+++ b/semestr-4/aisd/lista0/Rozw L0.pdf
diff --git a/semestr-4/aisd/lista0/lista0.pdf b/semestr-4/aisd/lista0/lista0.pdf
new file mode 100644
index 0000000..31b9daa
--- /dev/null
+++ b/semestr-4/aisd/lista0/lista0.pdf
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
--- /dev/null
+++ b/semestr-4/aisd/lista1/Lista 1.pdf
diff --git a/semestr-4/aisd/lista1/lista1.pdf b/semestr-4/aisd/lista1/lista1.pdf
new file mode 100644
index 0000000..a7dc065
--- /dev/null
+++ b/semestr-4/aisd/lista1/lista1.pdf
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
--- /dev/null
+++ b/semestr-4/aisd/lista2/Lista 2.pdf
diff --git a/semestr-4/aisd/lista2/lista2.pdf b/semestr-4/aisd/lista2/lista2.pdf
new file mode 100644
index 0000000..2d8937f
--- /dev/null
+++ b/semestr-4/aisd/lista2/lista2.pdf
diff --git a/semestr-4/aisd/lista3/huff.pdf b/semestr-4/aisd/lista3/huff.pdf
new file mode 100644
index 0000000..bf2cfec
--- /dev/null
+++ b/semestr-4/aisd/lista3/huff.pdf
diff --git a/semestr-4/aisd/lista3/huffman.pdf b/semestr-4/aisd/lista3/huffman.pdf
new file mode 100644
index 0000000..1881a27
--- /dev/null
+++ b/semestr-4/aisd/lista3/huffman.pdf
diff --git a/semestr-4/aisd/lista3/lista3.pdf b/semestr-4/aisd/lista3/lista3.pdf
new file mode 100644
index 0000000..74514b8
--- /dev/null
+++ b/semestr-4/aisd/lista3/lista3.pdf
diff --git a/semestr-4/aisd/pracownia1/pracownia1.pdf b/semestr-4/aisd/pracownia1/pracownia1.pdf
new file mode 100644
index 0000000..2b99ba4
--- /dev/null
+++ b/semestr-4/aisd/pracownia1/pracownia1.pdf
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<bits/stdc++.h>

+using namespace std;

+typedef long long ll;

+

+vector<pair<int, pair<int, int>>> 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<bits/stdc++.h>
+using namespace std;
+typedef unsigned long long ll;
+
+vector<pair<int, ll>> 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<<k) * (ll)nd});
+    }
+    sort(v.begin(), v.end());
+    int result = 0;
+    for (int i = 0; i < n; ) {
+        int j = i;
+        int cur = v[i].first;
+        ll count = 0;
+        while (j < n && v[j].first == cur) {
+            count += v[j].second;
+            ++j;
+        }
+        result += __builtin_popcountll(count);
+        i = j;
+    }
+    cout << result << "\n";
+}
\ No newline at end of file
diff --git a/semestr-4/aisd/pracownia2/gen.py b/semestr-4/aisd/pracownia2/gen.py
new file mode 100644
index 0000000..13aed55
--- /dev/null
+++ b/semestr-4/aisd/pracownia2/gen.py
@@ -0,0 +1,24 @@
+from random import randint, seed
+import sys
+
+if (len(sys.argv) < 4):
+    print("usage: python3 gen.py seed n sum")
+    exit()
+
+seed(sys.argv[1])
+
+n, sum = map(int, sys.argv[2:4])
+if n > 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 <bits/stdc++.h>
+using namespace std;
+
+const int MAX_SUM = 1e6;
+const int N = 2e3 + 10;
+
+unordered_map<int, int> sums;
+vector<pair<int, int>> 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 <bits/stdc++.h>
+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<bits/stdc++.h>
+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<bits/stdc++.h>
+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
--- /dev/null
+++ b/semestr-4/aisd/pracownia2/show_problem.pdf
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 <bits/stdc++.h>
+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 <bits/stdc++.h>
+using namespace std;
+
+const int MAXP = 105;
+const int MAXN = 5005;
+
+int n, p, m;
+unordered_set<int> banned;
+vector<pair<int, int>> 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<int, pair<int, int>> 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
--- /dev/null
+++ b/semestr-4/aisd/pracownia3/show_problem.pdf
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 <bits/stdc++.h>
+using namespace std;
+typedef long long ll;
+
+struct insert_list {
+    vector<int> v;
+    
+    insert_list() {
+    }
+
+    void insert(int p, int val) {
+        assert(p <= v.size());
+        assert(p >= 0);
+        vector<int> 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<int> 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 <bits/stdc++.h>
+using namespace std;
+typedef long long ll;
+
+const int K = 20;
+const int M = (1<<K);
+const size_t tree_size = M*2 + 10;
+
+struct query {
+    char type;
+    union {
+        struct insert {
+            int p;
+            int x;
+        } insert;
+        struct sum {
+            int from;
+            int to;
+        } sum;
+        int del;
+    } info;
+};
+
+struct kox_set {
+    ll tree[tree_size];
+
+    kox_set() {
+        for (int i = 0; i < tree_size; i++) tree[i] = 0;
+    }
+
+    void add(int val) {
+        update(val, 1);
+    }
+
+    void del(int val) {
+        update(val, -1);
+    }
+
+    void update(int where, int val) {
+        where += M;
+        while (where) {
+            tree[where] += val;
+            where /= 2;
+        }
+    }
+
+    ll sum(int from, int to) {
+        from += M;
+        to += M;
+        ll ans = tree[from];
+        if (from != to) ans += tree[to];
+        while (from/2 != to/2) {
+            if (from % 2 == 0)  ans += tree[from + 1];
+            if (to % 2 == 1)    ans += tree[to - 1];
+            to /= 2; from /= 2;
+        }
+        return ans;
+    }
+
+    int kth_elem(int k) {
+        int where = 1;
+        while (where < M) {
+            where *= 2;
+            if (tree[where] < k) {
+                k -= tree[where];
+                where += 1;
+            } 
+        }
+        return where - M;
+    }
+
+    void fill(int value) {
+        for (int i = 0; i < M; i++) {
+            tree[i + M] = value;
+        }
+        for (int d = K-1; d >= 0; d--) {
+            int maks = (1<<d);
+            for (int i = 0; i < maks; i++) {
+                int ind = i + maks;
+                tree[ind] = tree[ind*2] + tree[ind*2 + 1];
+            }
+        }
+    }
+};
+
+vector<query> queries;
+map<int, int> 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 <bits/stdc++.h>
+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<treap*, treap*> 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 <bits/stdc++.h>
+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<treap*, treap*> 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 <a, b)
+{
+    auto p1 = split(t, b);
+    auto p2 = split(p1.first, a);
+    if(p2.second) p2.second->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
--- /dev/null
+++ b/semestr-4/aisd/pracownia4/show_problem.pdf
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
--- /dev/null
+++ b/semestr-4/aisd/pracownia5/t.tin
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 <bits/stdc++.h>
+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<event> events;
+map<int, int> points;
+
+void get_cross_pnts(vector<pnt> &result, vector<seg> &hor, vector<seg> &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<pnt> temp;
+vector<seg> 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<pnt> &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<pnt> &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<pnt> &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<pnt> &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<pnt> &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<pnt> &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<pnt> 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 <bits/stdc++.h>
+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<seg> segments;
+vector<pnt> result; 
+vector<pnt> temp_res;
+vector<event> events;
+map<int, int> hor;
+map<int, int> cl;
+map<int, int> 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 <bits/stdc++.h>
+using namespace std;
+
+const int N = 1e6 + 10;
+bool vis[N];
+int n, m, ranga[N], par[N];
+pair<int, pair<int, int>> 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 <bits/stdc++.h>

+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 <bits/stdc++.h>

+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 <bits/stdc++.h>

+using namespace std;

+

+const int N = 503;

+int dist[N];

+vector<pair<int, pair<int, int>>> 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 <bits/stdc++.h>

+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
--- /dev/null
+++ b/semestr-4/aisd/wyklady/Notatka 1 - Preliminaria.pdf
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
--- /dev/null
+++ b/semestr-4/aisd/wyklady/Notatka 2 - Kopiec.pdf
diff --git a/semestr-4/aisd/wyklady/Notatka 3 - Zachłany.pdf b/semestr-4/aisd/wyklady/Notatka 3 - Zachłany.pdf
new file mode 100644
index 0000000..5403789
--- /dev/null
+++ b/semestr-4/aisd/wyklady/Notatka 3 - Zachłany.pdf
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
--- /dev/null
+++ b/semestr-4/aisd/wyklady/Notatka 4 - divide and conquer.pdf
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
--- /dev/null
+++ b/semestr-4/aisd/wyklady/Notatka 5 - divide and conquer cd.pdf
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
--- /dev/null
+++ b/semestr-4/aisd/wyklady/Notatka 6 - Programowanie Dynamiczne.pdf
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
--- /dev/null
+++ b/semestr-4/aisd/wyklady/Notatka 7 - Programowanie Dynamiczne cd.pdf