aboutsummaryrefslogtreecommitdiff
path: root/Semestr 4/aisd
diff options
context:
space:
mode:
authorFranciszek Malinka <franciszek.malinka@gmail.com>2021-10-05 21:49:54 +0200
committerFranciszek Malinka <franciszek.malinka@gmail.com>2021-10-05 21:49:54 +0200
commitc5fcf7179a83ef65c86c6a4a390029149e518649 (patch)
treed29ffc5b86a0d257453cedcf87d91a13d8bf3b0d /Semestr 4/aisd
parentf8a88b6a4aba1f66d04711a9330eaba49a50c463 (diff)
Duzy commit ze smieciami
Diffstat (limited to 'Semestr 4/aisd')
-rw-r--r--Semestr 4/aisd/lista0/L0Z8.md51
-rw-r--r--Semestr 4/aisd/lista0/Rozw L0.pdfbin1983735 -> 0 bytes
-rw-r--r--Semestr 4/aisd/lista0/lista0.pdfbin83161 -> 0 bytes
-rw-r--r--Semestr 4/aisd/lista1/Lista 1.pdfbin810791 -> 0 bytes
-rw-r--r--Semestr 4/aisd/lista1/lista1.pdfbin103432 -> 0 bytes
-rw-r--r--Semestr 4/aisd/lista2/Lista 2.pdfbin2301798 -> 0 bytes
-rw-r--r--Semestr 4/aisd/lista2/lista2.pdfbin128638 -> 0 bytes
-rw-r--r--Semestr 4/aisd/lista3/huff.pdfbin62844 -> 0 bytes
-rw-r--r--Semestr 4/aisd/lista3/huffman.pdfbin73477 -> 0 bytes
-rw-r--r--Semestr 4/aisd/lista3/lista3.pdfbin179499 -> 0 bytes
-rw-r--r--Semestr 4/aisd/pracownia1/pracownia1.pdfbin55846 -> 0 bytes
-rw-r--r--Semestr 4/aisd/pracownia1/rozw.cpp59
-rw-r--r--Semestr 4/aisd/pracownia1/rozw2.cpp33
-rw-r--r--Semestr 4/aisd/pracownia2/gen.py24
-rwxr-xr-xSemestr 4/aisd/pracownia2/gen_test.sh24
-rw-r--r--Semestr 4/aisd/pracownia2/rozw.cpp59
-rw-r--r--Semestr 4/aisd/pracownia2/rozw2.cpp71
-rw-r--r--Semestr 4/aisd/pracownia2/rozw3.cpp71
-rw-r--r--Semestr 4/aisd/pracownia2/rozw4.cpp51
-rw-r--r--Semestr 4/aisd/pracownia2/show_problem.pdfbin53598 -> 0 bytes
-rw-r--r--Semestr 4/aisd/pracownia3/check.cpp87
-rw-r--r--Semestr 4/aisd/pracownia3/gen.py14
-rwxr-xr-xSemestr 4/aisd/pracownia3/ocen.sh18
-rw-r--r--Semestr 4/aisd/pracownia3/rozw.cpp102
-rw-r--r--Semestr 4/aisd/pracownia3/show_problem.pdfbin73936 -> 0 bytes
-rw-r--r--Semestr 4/aisd/pracownia3/wa.outr1025
-rw-r--r--Semestr 4/aisd/pracownia4/brut.cpp69
-rw-r--r--Semestr 4/aisd/pracownia4/gen.py24
-rw-r--r--Semestr 4/aisd/pracownia4/rozw.cpp157
-rw-r--r--Semestr 4/aisd/pracownia4/rozw2.cpp135
-rw-r--r--Semestr 4/aisd/pracownia4/rozw3.cpp149
-rw-r--r--Semestr 4/aisd/pracownia4/show_problem.pdfbin61345 -> 0 bytes
-rwxr-xr-xSemestr 4/aisd/pracownia4/test.sh21
-rw-r--r--Semestr 4/aisd/pracownia5/gen.py40
-rw-r--r--Semestr 4/aisd/pracownia5/wzo.cpp286
-rw-r--r--Semestr 4/aisd/pracownia5/wzo2.cpp184
-rw-r--r--Semestr 4/aisd/pracownia6/wzo.cpp51
-rw-r--r--Semestr 4/aisd/themis/AISDDEBIUT21.cpp24
-rw-r--r--Semestr 4/aisd/themis/AISDPOTEGOWANIE.cpp29
-rw-r--r--Semestr 4/aisd/themis/BELLMAN.cpp55
-rw-r--r--Semestr 4/aisd/themis/FIB.cpp58
-rw-r--r--Semestr 4/aisd/wyklady/Notatka 1 - Preliminaria.pdfbin211162 -> 0 bytes
-rw-r--r--Semestr 4/aisd/wyklady/Notatka 2 - Kopiec.pdfbin150213 -> 0 bytes
-rw-r--r--Semestr 4/aisd/wyklady/Notatka 3 - Zachłany.pdfbin243598 -> 0 bytes
-rw-r--r--Semestr 4/aisd/wyklady/Notatka 4 - divide and conquer.pdfbin326839 -> 0 bytes
-rw-r--r--Semestr 4/aisd/wyklady/Notatka 5 - divide and conquer cd.pdfbin146884 -> 0 bytes
-rw-r--r--Semestr 4/aisd/wyklady/Notatka 6 - Programowanie Dynamiczne.pdfbin213697 -> 0 bytes
-rw-r--r--Semestr 4/aisd/wyklady/Notatka 7 - Programowanie Dynamiczne cd.pdfbin214965 -> 0 bytes
48 files changed, 0 insertions, 2971 deletions
diff --git a/Semestr 4/aisd/lista0/L0Z8.md b/Semestr 4/aisd/lista0/L0Z8.md
deleted file mode 100644
index d9c8604..0000000
--- a/Semestr 4/aisd/lista0/L0Z8.md
+++ /dev/null
@@ -1,51 +0,0 @@
-# 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
deleted file mode 100644
index d39c13b..0000000
--- a/Semestr 4/aisd/lista0/Rozw L0.pdf
+++ /dev/null
Binary files differ
diff --git a/Semestr 4/aisd/lista0/lista0.pdf b/Semestr 4/aisd/lista0/lista0.pdf
deleted file mode 100644
index 31b9daa..0000000
--- a/Semestr 4/aisd/lista0/lista0.pdf
+++ /dev/null
Binary files differ
diff --git a/Semestr 4/aisd/lista1/Lista 1.pdf b/Semestr 4/aisd/lista1/Lista 1.pdf
deleted file mode 100644
index 7e2f5ae..0000000
--- a/Semestr 4/aisd/lista1/Lista 1.pdf
+++ /dev/null
Binary files differ
diff --git a/Semestr 4/aisd/lista1/lista1.pdf b/Semestr 4/aisd/lista1/lista1.pdf
deleted file mode 100644
index a7dc065..0000000
--- a/Semestr 4/aisd/lista1/lista1.pdf
+++ /dev/null
Binary files differ
diff --git a/Semestr 4/aisd/lista2/Lista 2.pdf b/Semestr 4/aisd/lista2/Lista 2.pdf
deleted file mode 100644
index ccf83b7..0000000
--- a/Semestr 4/aisd/lista2/Lista 2.pdf
+++ /dev/null
Binary files differ
diff --git a/Semestr 4/aisd/lista2/lista2.pdf b/Semestr 4/aisd/lista2/lista2.pdf
deleted file mode 100644
index 2d8937f..0000000
--- a/Semestr 4/aisd/lista2/lista2.pdf
+++ /dev/null
Binary files differ
diff --git a/Semestr 4/aisd/lista3/huff.pdf b/Semestr 4/aisd/lista3/huff.pdf
deleted file mode 100644
index bf2cfec..0000000
--- a/Semestr 4/aisd/lista3/huff.pdf
+++ /dev/null
Binary files differ
diff --git a/Semestr 4/aisd/lista3/huffman.pdf b/Semestr 4/aisd/lista3/huffman.pdf
deleted file mode 100644
index 1881a27..0000000
--- a/Semestr 4/aisd/lista3/huffman.pdf
+++ /dev/null
Binary files differ
diff --git a/Semestr 4/aisd/lista3/lista3.pdf b/Semestr 4/aisd/lista3/lista3.pdf
deleted file mode 100644
index 74514b8..0000000
--- a/Semestr 4/aisd/lista3/lista3.pdf
+++ /dev/null
Binary files differ
diff --git a/Semestr 4/aisd/pracownia1/pracownia1.pdf b/Semestr 4/aisd/pracownia1/pracownia1.pdf
deleted file mode 100644
index 2b99ba4..0000000
--- a/Semestr 4/aisd/pracownia1/pracownia1.pdf
+++ /dev/null
Binary files differ
diff --git a/Semestr 4/aisd/pracownia1/rozw.cpp b/Semestr 4/aisd/pracownia1/rozw.cpp
deleted file mode 100644
index acbd711..0000000
--- a/Semestr 4/aisd/pracownia1/rozw.cpp
+++ /dev/null
@@ -1,59 +0,0 @@
-#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
deleted file mode 100644
index 35fd37e..0000000
--- a/Semestr 4/aisd/pracownia1/rozw2.cpp
+++ /dev/null
@@ -1,33 +0,0 @@
-#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
deleted file mode 100644
index 13aed55..0000000
--- a/Semestr 4/aisd/pracownia2/gen.py
+++ /dev/null
@@ -1,24 +0,0 @@
-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
deleted file mode 100755
index d5bff05..0000000
--- a/Semestr 4/aisd/pracownia2/gen_test.sh
+++ /dev/null
@@ -1,24 +0,0 @@
-#!/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
deleted file mode 100644
index dd0d700..0000000
--- a/Semestr 4/aisd/pracownia2/rozw.cpp
+++ /dev/null
@@ -1,59 +0,0 @@
-#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
deleted file mode 100644
index fa0b2d6..0000000
--- a/Semestr 4/aisd/pracownia2/rozw2.cpp
+++ /dev/null
@@ -1,71 +0,0 @@
-#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
deleted file mode 100644
index 8e3dd2a..0000000
--- a/Semestr 4/aisd/pracownia2/rozw3.cpp
+++ /dev/null
@@ -1,71 +0,0 @@
-#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
deleted file mode 100644
index 73ff79a..0000000
--- a/Semestr 4/aisd/pracownia2/rozw4.cpp
+++ /dev/null
@@ -1,51 +0,0 @@
-#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
deleted file mode 100644
index 4ab0312..0000000
--- a/Semestr 4/aisd/pracownia2/show_problem.pdf
+++ /dev/null
Binary files differ
diff --git a/Semestr 4/aisd/pracownia3/check.cpp b/Semestr 4/aisd/pracownia3/check.cpp
deleted file mode 100644
index c9c74d7..0000000
--- a/Semestr 4/aisd/pracownia3/check.cpp
+++ /dev/null
@@ -1,87 +0,0 @@
-#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
deleted file mode 100644
index b572647..0000000
--- a/Semestr 4/aisd/pracownia3/gen.py
+++ /dev/null
@@ -1,14 +0,0 @@
-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
deleted file mode 100755
index 593aa67..0000000
--- a/Semestr 4/aisd/pracownia3/ocen.sh
+++ /dev/null
@@ -1,18 +0,0 @@
-#!/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
deleted file mode 100644
index 7f1a307..0000000
--- a/Semestr 4/aisd/pracownia3/rozw.cpp
+++ /dev/null
@@ -1,102 +0,0 @@
-#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
deleted file mode 100644
index f426311..0000000
--- a/Semestr 4/aisd/pracownia3/show_problem.pdf
+++ /dev/null
Binary files differ
diff --git a/Semestr 4/aisd/pracownia3/wa.outr b/Semestr 4/aisd/pracownia3/wa.outr
deleted file mode 100644
index 81a8bb1..0000000
--- a/Semestr 4/aisd/pracownia3/wa.outr
+++ /dev/null
@@ -1,1025 +0,0 @@
-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
deleted file mode 100644
index 32f4ebb..0000000
--- a/Semestr 4/aisd/pracownia4/brut.cpp
+++ /dev/null
@@ -1,69 +0,0 @@
-#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
deleted file mode 100644
index 733a60e..0000000
--- a/Semestr 4/aisd/pracownia4/gen.py
+++ /dev/null
@@ -1,24 +0,0 @@
-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
deleted file mode 100644
index 9c314e2..0000000
--- a/Semestr 4/aisd/pracownia4/rozw.cpp
+++ /dev/null
@@ -1,157 +0,0 @@
-#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
deleted file mode 100644
index 17562a9..0000000
--- a/Semestr 4/aisd/pracownia4/rozw2.cpp
+++ /dev/null
@@ -1,135 +0,0 @@
-#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
deleted file mode 100644
index ec107ef..0000000
--- a/Semestr 4/aisd/pracownia4/rozw3.cpp
+++ /dev/null
@@ -1,149 +0,0 @@
-
-#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
deleted file mode 100644
index 8a1c155..0000000
--- a/Semestr 4/aisd/pracownia4/show_problem.pdf
+++ /dev/null
Binary files differ
diff --git a/Semestr 4/aisd/pracownia4/test.sh b/Semestr 4/aisd/pracownia4/test.sh
deleted file mode 100755
index dc725ad..0000000
--- a/Semestr 4/aisd/pracownia4/test.sh
+++ /dev/null
@@ -1,21 +0,0 @@
-#!/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
deleted file mode 100644
index 283cd04..0000000
--- a/Semestr 4/aisd/pracownia5/gen.py
+++ /dev/null
@@ -1,40 +0,0 @@
-import random
-import sys
-
-random.seed(sys.argv[1])
-
-n = int(sys.argv[2])
-maxcoord = 1000
-
-
-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/wzo.cpp b/Semestr 4/aisd/pracownia5/wzo.cpp
deleted file mode 100644
index 14056c8..0000000
--- a/Semestr 4/aisd/pracownia5/wzo.cpp
+++ /dev/null
@@ -1,286 +0,0 @@
-#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());
- 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();
-} \ No newline at end of file
diff --git a/Semestr 4/aisd/pracownia5/wzo2.cpp b/Semestr 4/aisd/pracownia5/wzo2.cpp
deleted file mode 100644
index b4e9ac3..0000000
--- a/Semestr 4/aisd/pracownia5/wzo2.cpp
+++ /dev/null
@@ -1,184 +0,0 @@
-#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
deleted file mode 100644
index f13f0ec..0000000
--- a/Semestr 4/aisd/pracownia6/wzo.cpp
+++ /dev/null
@@ -1,51 +0,0 @@
-#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
deleted file mode 100644
index 3666d69..0000000
--- a/Semestr 4/aisd/themis/AISDDEBIUT21.cpp
+++ /dev/null
@@ -1,24 +0,0 @@
-/*
- * 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
deleted file mode 100644
index c1b76fe..0000000
--- a/Semestr 4/aisd/themis/AISDPOTEGOWANIE.cpp
+++ /dev/null
@@ -1,29 +0,0 @@
-#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
deleted file mode 100644
index 5a65096..0000000
--- a/Semestr 4/aisd/themis/BELLMAN.cpp
+++ /dev/null
@@ -1,55 +0,0 @@
-#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
deleted file mode 100644
index dd38c5c..0000000
--- a/Semestr 4/aisd/themis/FIB.cpp
+++ /dev/null
@@ -1,58 +0,0 @@
-#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
deleted file mode 100644
index dc4ee1c..0000000
--- a/Semestr 4/aisd/wyklady/Notatka 1 - Preliminaria.pdf
+++ /dev/null
Binary files differ
diff --git a/Semestr 4/aisd/wyklady/Notatka 2 - Kopiec.pdf b/Semestr 4/aisd/wyklady/Notatka 2 - Kopiec.pdf
deleted file mode 100644
index c8e76a7..0000000
--- a/Semestr 4/aisd/wyklady/Notatka 2 - Kopiec.pdf
+++ /dev/null
Binary files differ
diff --git a/Semestr 4/aisd/wyklady/Notatka 3 - Zachłany.pdf b/Semestr 4/aisd/wyklady/Notatka 3 - Zachłany.pdf
deleted file mode 100644
index 5403789..0000000
--- a/Semestr 4/aisd/wyklady/Notatka 3 - Zachłany.pdf
+++ /dev/null
Binary files 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
deleted file mode 100644
index 205b505..0000000
--- a/Semestr 4/aisd/wyklady/Notatka 4 - divide and conquer.pdf
+++ /dev/null
Binary files 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
deleted file mode 100644
index 48fc8e4..0000000
--- a/Semestr 4/aisd/wyklady/Notatka 5 - divide and conquer cd.pdf
+++ /dev/null
Binary files differ
diff --git a/Semestr 4/aisd/wyklady/Notatka 6 - Programowanie Dynamiczne.pdf b/Semestr 4/aisd/wyklady/Notatka 6 - Programowanie Dynamiczne.pdf
deleted file mode 100644
index d8b61ce..0000000
--- a/Semestr 4/aisd/wyklady/Notatka 6 - Programowanie Dynamiczne.pdf
+++ /dev/null
Binary files 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
deleted file mode 100644
index 7040119..0000000
--- a/Semestr 4/aisd/wyklady/Notatka 7 - Programowanie Dynamiczne cd.pdf
+++ /dev/null
Binary files differ