diff options
author | Franciszek Malinka <franciszek.malinka@gmail.com> | 2021-10-05 21:49:54 +0200 |
---|---|---|
committer | Franciszek Malinka <franciszek.malinka@gmail.com> | 2021-10-05 21:49:54 +0200 |
commit | c5fcf7179a83ef65c86c6a4a390029149e518649 (patch) | |
tree | d29ffc5b86a0d257453cedcf87d91a13d8bf3b0d /Semestr 4/aisd | |
parent | f8a88b6a4aba1f66d04711a9330eaba49a50c463 (diff) |
Duzy commit ze smieciami
Diffstat (limited to 'Semestr 4/aisd')
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 Binary files differdeleted file mode 100644 index d39c13b..0000000 --- a/Semestr 4/aisd/lista0/Rozw L0.pdf +++ /dev/null diff --git a/Semestr 4/aisd/lista0/lista0.pdf b/Semestr 4/aisd/lista0/lista0.pdf Binary files differdeleted file mode 100644 index 31b9daa..0000000 --- a/Semestr 4/aisd/lista0/lista0.pdf +++ /dev/null diff --git a/Semestr 4/aisd/lista1/Lista 1.pdf b/Semestr 4/aisd/lista1/Lista 1.pdf Binary files differdeleted file mode 100644 index 7e2f5ae..0000000 --- a/Semestr 4/aisd/lista1/Lista 1.pdf +++ /dev/null diff --git a/Semestr 4/aisd/lista1/lista1.pdf b/Semestr 4/aisd/lista1/lista1.pdf Binary files differdeleted file mode 100644 index a7dc065..0000000 --- a/Semestr 4/aisd/lista1/lista1.pdf +++ /dev/null diff --git a/Semestr 4/aisd/lista2/Lista 2.pdf b/Semestr 4/aisd/lista2/Lista 2.pdf Binary files differdeleted file mode 100644 index ccf83b7..0000000 --- a/Semestr 4/aisd/lista2/Lista 2.pdf +++ /dev/null diff --git a/Semestr 4/aisd/lista2/lista2.pdf b/Semestr 4/aisd/lista2/lista2.pdf Binary files differdeleted file mode 100644 index 2d8937f..0000000 --- a/Semestr 4/aisd/lista2/lista2.pdf +++ /dev/null diff --git a/Semestr 4/aisd/lista3/huff.pdf b/Semestr 4/aisd/lista3/huff.pdf Binary files differdeleted file mode 100644 index bf2cfec..0000000 --- a/Semestr 4/aisd/lista3/huff.pdf +++ /dev/null diff --git a/Semestr 4/aisd/lista3/huffman.pdf b/Semestr 4/aisd/lista3/huffman.pdf Binary files differdeleted file mode 100644 index 1881a27..0000000 --- a/Semestr 4/aisd/lista3/huffman.pdf +++ /dev/null diff --git a/Semestr 4/aisd/lista3/lista3.pdf b/Semestr 4/aisd/lista3/lista3.pdf Binary files differdeleted file mode 100644 index 74514b8..0000000 --- a/Semestr 4/aisd/lista3/lista3.pdf +++ /dev/null diff --git a/Semestr 4/aisd/pracownia1/pracownia1.pdf b/Semestr 4/aisd/pracownia1/pracownia1.pdf Binary files differdeleted file mode 100644 index 2b99ba4..0000000 --- a/Semestr 4/aisd/pracownia1/pracownia1.pdf +++ /dev/null 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 Binary files differdeleted file mode 100644 index 4ab0312..0000000 --- a/Semestr 4/aisd/pracownia2/show_problem.pdf +++ /dev/null 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 Binary files differdeleted file mode 100644 index f426311..0000000 --- a/Semestr 4/aisd/pracownia3/show_problem.pdf +++ /dev/null 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 Binary files differdeleted file mode 100644 index 8a1c155..0000000 --- a/Semestr 4/aisd/pracownia4/show_problem.pdf +++ /dev/null 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 Binary files differdeleted file mode 100644 index dc4ee1c..0000000 --- a/Semestr 4/aisd/wyklady/Notatka 1 - Preliminaria.pdf +++ /dev/null diff --git a/Semestr 4/aisd/wyklady/Notatka 2 - Kopiec.pdf b/Semestr 4/aisd/wyklady/Notatka 2 - Kopiec.pdf Binary files differdeleted file mode 100644 index c8e76a7..0000000 --- a/Semestr 4/aisd/wyklady/Notatka 2 - Kopiec.pdf +++ /dev/null diff --git a/Semestr 4/aisd/wyklady/Notatka 3 - Zachłany.pdf b/Semestr 4/aisd/wyklady/Notatka 3 - Zachłany.pdf Binary files differdeleted file mode 100644 index 5403789..0000000 --- a/Semestr 4/aisd/wyklady/Notatka 3 - Zachłany.pdf +++ /dev/null diff --git a/Semestr 4/aisd/wyklady/Notatka 4 - divide and conquer.pdf b/Semestr 4/aisd/wyklady/Notatka 4 - divide and conquer.pdf Binary files differdeleted file mode 100644 index 205b505..0000000 --- a/Semestr 4/aisd/wyklady/Notatka 4 - divide and conquer.pdf +++ /dev/null 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 Binary files differdeleted file mode 100644 index 48fc8e4..0000000 --- a/Semestr 4/aisd/wyklady/Notatka 5 - divide and conquer cd.pdf +++ /dev/null diff --git a/Semestr 4/aisd/wyklady/Notatka 6 - Programowanie Dynamiczne.pdf b/Semestr 4/aisd/wyklady/Notatka 6 - Programowanie Dynamiczne.pdf Binary files differdeleted file mode 100644 index d8b61ce..0000000 --- a/Semestr 4/aisd/wyklady/Notatka 6 - Programowanie Dynamiczne.pdf +++ /dev/null diff --git a/Semestr 4/aisd/wyklady/Notatka 7 - Programowanie Dynamiczne cd.pdf b/Semestr 4/aisd/wyklady/Notatka 7 - Programowanie Dynamiczne cd.pdf Binary files differdeleted file mode 100644 index 7040119..0000000 --- a/Semestr 4/aisd/wyklady/Notatka 7 - Programowanie Dynamiczne cd.pdf +++ /dev/null |