aktualizacja

11 files changed, 343 insertions, 0 deletions

diff --git a/Semestr 4/Pstwo/Lista 4/RP1R_04.pdf b/Semestr 4/Pstwo/Lista 4/RP1R_04.pdf
new file mode 100644
index 0000000..a093a1b
--- /dev/null
+++ b/Semestr 4/Pstwo/Lista 4/RP1R_04.pdf
diff --git a/Semestr 4/aisd/Pracownia 2/rozw3.cpp b/Semestr 4/aisd/Pracownia 2/rozw3.cpp
new file mode 100644
index 0000000..8e3dd2a
--- /dev/null
+++ b/Semestr 4/aisd/Pracownia 2/rozw3.cpp
@@ -0,0 +1,71 @@
+#include<bits/stdc++.h>
+using namespace std;
+
+#define RIGHT 0
+#define LEFT 1
+
+const int MAXN = 2e3 + 10;
+const int M = 5e5 + 10;
+
+int n, H[MAXN], dp[2][M*2];
+bool vis[2][M*2], both[2][M*2];
+
+int get_val()
+
+int main() {
+    ios_base::sync_with_stdio(false);
+    cin.tie();
+    cin >> n;
+    for (int i = 0; i < n; i++) {
+        cin >> H[i];
+    }
+
+    int sum = 0, K = 0;
+    vis[K^1][0] = true;
+    for (int i = 0; i < n; i++) {
+        int h = H[i];
+        for (int cur = -sum; cur <= sum; ++cur) {
+            vis[K][cur + M] |= vis[K^1][cur + M];
+            both[K][cur + M] |= both[K^1][cur + M];
+            dp[K][cur + M] = max({dp[K][cur + M], dp[K^1][cur + M]});
+            if (vis[K][cur + M]) {
+                int val = dp[K][cur + M];
+                int left = cur + M - h;
+                int right = cur + M + h;
+
+                if (cur - h >= 0) {
+                    both[K][right] = true;
+                }
+                vis[K][right] = true;
+                dp[K][right] = max({dp[K][right], dp[K^1][right], dp[K^1][right] + h});
+
+                if (cur + h <= 0) {
+                    both[K][left]= true;
+                }
+                vis[K][left] = true;
+                dp[K][left] = max({dp[K][left], dp[K^1][left], dp[K^1][left] + h});
+            }
+        }
+        K^=1;
+        for (int cur = -sum; cur <= sum; ++cur) {
+            dp[K][cur + M] = 0;
+            vis[K][cur + M] = 0;
+            both[K][cur + M] = 0;
+        }
+        sum += h;
+    }
+    K^=1;
+    if (both[K][M]) {
+        cout << "TAK\n";
+        cout << dp[K][M] << "\n";
+    } else {
+        cout << "NIE\n";
+        int best = -sum;
+        for (int cur = -sum ; cur <= sum; ++cur) {
+            if (both[cur + M] && abs(cur) < abs(best)) {
+                best = cur;
+            }
+        }
+        cout << abs(best) << "\n";
+    }
+}
\ No newline at end of file
diff --git a/Semestr 4/aisd/Pracownia 2/rozw4.cpp b/Semestr 4/aisd/Pracownia 2/rozw4.cpp
new file mode 100644
index 0000000..73ff79a
--- /dev/null
+++ b/Semestr 4/aisd/Pracownia 2/rozw4.cpp
@@ -0,0 +1,51 @@
+#include<bits/stdc++.h>
+using namespace std;
+
+const int MAX_SUM = 1e6, MAXN = 2004;
+int n;
+int dp[2][MAX_SUM + 10], H[MAXN];
+
+int main() {
+    scanf("%d", &n);
+    for (int i = 0; i < n; ++i) {
+        scanf("%d", &H[i]);
+    }
+    
+    sort(H, H + n);
+
+    int sum = 0, K = 0;
+    for (int i = 0; i < n; ++i) {
+        int h = H[i];
+        for (int i = 0; i <= min(sum, MAX_SUM); i++) 
+            dp[K^1][i] = dp[K][i];
+            
+        for (int i = 0; i <= min(sum, MAX_SUM); i++) {
+            if (i != 0 && dp[K][i] == 0) continue;
+
+            int left = abs(i - h), aux = i-h >= 0 ? 0 : h-i;
+            if (left <= MAX_SUM) {
+                dp[K^1][left] = max(dp[K^1][left], dp[K][i] + aux);
+            }
+            int right = i + h;
+            if (right <= MAX_SUM) {
+                dp[K^1][right] = max(dp[K^1][right], dp[K][i] + h);
+            }
+        }
+        
+        K ^= 1;            
+        sum += h;
+    }
+    if (dp[K][0] != 0) {
+        printf("TAK\n%d\n", dp[K][0]);
+    }
+    else {
+        int res = 0;
+        for (int i = 1; i <= MAX_SUM; i++) {
+            if (dp[K][i] != i && dp[K][i]) {
+                res = i;
+                break;
+            }
+        }
+        printf("NIE\n%d\n", res);
+    }
+}
\ No newline at end of file
diff --git a/Semestr 4/aisd/pracownia3/check.cpp b/Semestr 4/aisd/pracownia3/check.cpp
new file mode 100644
index 0000000..c9c74d7
--- /dev/null
+++ b/Semestr 4/aisd/pracownia3/check.cpp
@@ -0,0 +1,87 @@
+#include <bits/stdc++.h>
+using namespace std;
+
+int n, p, m;
+int banned[103][3][3];
+int plane[5][10];
+
+bool check(int k, int i, int pp) {
+    for (int kk = k; kk < k + 3; kk++) {
+        for (int ii = i; ii < i + 3; ii++) {
+            if (plane[kk][ii] != banned[pp][kk-k][ii-i])
+                return false;
+        }
+    }
+    return true;
+}
+
+void debug(int pp) {
+    for (int i = 0; i < 3; ++i) {
+        for (int j = 0; j < 3; ++j) {
+            cout << ((banned[pp][i][j] == 0) ? '.' : 'x');
+        }
+        cout << "\n";
+    }
+}
+
+void debug() {
+    for (int k = 0; k < 5; ++k) {
+        for (int i = 0; i < n; ++i) {
+            cout << (plane[k][i] ? 'x' : '.');
+        }
+        cout << "\n"; 
+    }
+    cout << "\n";
+}
+
+int ile[1030];
+
+int main() {
+    cin >> n >> p >> m;
+    for (int i = 0; i < p; i++) {
+        for (int k = 0; k < 3; k++) {
+            string s;
+            cin >> s;
+            for (int j = 0; j < 3; ++j) {
+                banned[i][k][j] = (s[j] == 'x');
+            }
+        }
+    }
+    int res = 0;
+    for (int mask = 0; mask < (1<<(5 * n)); mask++) {
+        for (int k = 0; k < 5; ++k) {
+            for (int i = 0; i < n; i++) {
+                plane[k][i] = ((mask & (1 << (k * n + i))) > 0);
+            }
+        }
+        bool dziala = true;
+        for (int k = 0; k < 3; ++k) {
+            for (int i = 0; i < n-2; ++i) {
+                for (int j = 0; j < p; ++j) {
+                    if (check(k, i, j)) {
+                        dziala = false;
+                        break;
+                    }
+                }
+                if (!dziala) break;
+            }
+            if (!dziala) break;
+        }
+        if (dziala) {
+            res++;
+            if (res == m) {
+                res = 0;
+            }
+            int mm = 0;
+            for (int i = 0; i < 5; ++i) {
+                mm += plane[i][n-2] * (1<<(i*2));
+                mm += plane[i][n-1] * (1<<(i*2 + 1));
+            }
+            ile[mm]++;
+        }
+    }  
+    for (int i = 0; i < 1024; ++i) {
+        cout << i << ": " << ile[i] << "\n";
+    }
+    cout << res % m << "\n";
+}
\ No newline at end of file
diff --git a/Semestr 4/aisd/pracownia3/gen.py b/Semestr 4/aisd/pracownia3/gen.py
new file mode 100644
index 0000000..b572647
--- /dev/null
+++ b/Semestr 4/aisd/pracownia3/gen.py
@@ -0,0 +1,14 @@
+import sys
+
+mask = int(sys.argv[1])
+print(3, 1, 1000000)
+
+def f(m):
+    t = [[0]*3]*3
+    for i in range(3):
+        for j in range(3):
+            t[i][j] = (m >> (i*3 + j)) & 1
+            print('x' if t[i][j] else '.', end='')
+        print()
+
+f(mask)
\ No newline at end of file
diff --git a/Semestr 4/aisd/pracownia3/ocen.sh b/Semestr 4/aisd/pracownia3/ocen.sh
new file mode 100755
index 0000000..593aa67
--- /dev/null
+++ b/Semestr 4/aisd/pracownia3/ocen.sh
@@ -0,0 +1,18 @@
+#!/bin/bash
+
+make rozw
+make check
+for i in {0..1023}
+do
+    python3 gen.py $i > t.in
+    ./rozw < t.in > wa.out
+    ./check < t.in > t.out
+    if diff -w wa.out t.out
+    then
+        echo $i
+        echo ok
+    else
+        echo nieok
+        break
+    fi
+done
\ No newline at end of file
diff --git a/Semestr 4/aisd/pracownia3/rozw.cpp b/Semestr 4/aisd/pracownia3/rozw.cpp
new file mode 100644
index 0000000..7f1a307
--- /dev/null
+++ b/Semestr 4/aisd/pracownia3/rozw.cpp
@@ -0,0 +1,102 @@
+#include <bits/stdc++.h>
+using namespace std;
+
+const int MAXP = 105;
+const int MAXN = 5005;
+
+int n, p, m;
+unordered_set<int> banned;
+vector<pair<int, int>> propagate;
+int dp[2][1024 + 10];
+
+inline int char_to_bit(char c) {
+    return c == '.' ? 0 : 1;
+}
+
+void input() {
+    scanf("%d%d%d", &n, &p, &m);
+    for (int i = 0; i < p; i++) {
+        char s[5];
+        int value = 0, d = 1;
+        for (int k = 0; k < 3; k++) {
+            scanf("%s", s);
+            value += (char_to_bit(s[0]) + char_to_bit(s[1]) * 2 + char_to_bit(s[2]) * 4) * d;
+            d *= 8;
+        }
+        banned.insert(value);
+    }
+}
+
+pair<int, pair<int, int>> get_pieces_values(int db, int sb) {
+    int tab[5][3];
+    for (int i = 0; i < 5; i++) {
+        tab[i][0] = (db >> (i*2)) & 1;
+        tab[i][1] = (db >> (i*2 + 1)) & 1;
+        tab[i][2] = (sb >> i) & 1;
+    }
+    int res[3];
+    for (int k = 0; k < 3; ++k) {
+        int value = 0, d = 1;
+        for (int i = k; i < k + 3; ++i) {
+            value += (tab[i][0] + tab[i][1] * 2 + tab[i][2] * 4) * d;
+            d *= 8;
+        }
+        res[k] = value;
+    }
+    return {res[0], {res[1], res[2]}};
+}
+
+int combine(int db, int sb) {
+    int res = (db >> 1) & 0x155;
+    for (int i = 0; i < 5; i++) {
+        res |= ((sb >> i) & 1) << (2*i + 1);
+    }
+    return res;
+}
+
+void preproces() {
+    const int db = (1<<10);     // double bar
+    const int sb = (1<<5);      // single bar
+
+    for (int db_mask = 0; db_mask < db; ++db_mask) {
+        for (int sb_mask = 0; sb_mask < sb; ++sb_mask) {
+            auto pieces = get_pieces_values(db_mask, sb_mask);
+            if (banned.count(pieces.first) || banned.count(pieces.second.first) || banned.count(pieces.second.second)) 
+                continue;
+            int db2_mask = combine(db_mask, sb_mask);
+            propagate.push_back({db_mask, db2_mask});
+        }
+    }
+}
+
+int compute_dp() {
+    int K = 1;
+    for (int i = 0; i < 1024; i++) {
+        dp[0][i] = 1;
+    }
+    for (int i = 2; i < n; i++) {
+        for (auto pp: propagate) {
+            int p1 = pp.first, p2 = pp.second;
+            dp[K][p2] += dp[K^1][p1];
+            dp[K][p2] %= m;
+        }
+        K ^= 1;
+        for (int j = 0; j < 1024; ++j) {
+            dp[K][j] = 0;
+        }
+    }
+
+    K ^= 1;
+    int result = 0;
+    for (int i = 0; i < 1024; i++) {
+        result += dp[K][i];
+        result %= m;
+    }
+    return result;
+}
+
+int main() {
+    input();
+    preproces();
+    printf("%d\n", compute_dp());
+}
\ No newline at end of file
diff --git a/Semestr 4/aisd/pracownia3/show_problem.pdf b/Semestr 4/aisd/pracownia3/show_problem.pdf
new file mode 100644
index 0000000..f426311
--- /dev/null
+++ b/Semestr 4/aisd/pracownia3/show_problem.pdf
diff --git a/Semestr 4/sieci/cwiczenia1/c1.pdf b/Semestr 4/sieci/cwiczenia1/c1.pdf
new file mode 100644
index 0000000..ace2fa7
--- /dev/null
+++ b/Semestr 4/sieci/cwiczenia1/c1.pdf
diff --git a/Semestr 4/sieci/cwiczenia1/cw1.pdf b/Semestr 4/sieci/cwiczenia1/cw1.pdf
new file mode 100644
index 0000000..d217892
--- /dev/null
+++ b/Semestr 4/sieci/cwiczenia1/cw1.pdf
diff --git a/Semestr 4/sieci/pracownia2/p2.pdf b/Semestr 4/sieci/pracownia2/p2.pdf
new file mode 100644
index 0000000..f0cc942
--- /dev/null
+++ b/Semestr 4/sieci/pracownia2/p2.pdf