From d6e7fae474dc97e46990a45b48ac4f69a35072eb Mon Sep 17 00:00:00 2001 From: Franciszek Malinka Date: Fri, 26 Mar 2021 18:04:17 +0100 Subject: aktualizacja --- Semestr 4/Pstwo/Lista 4/RP1R_04.pdf | Bin 0 -> 125285 bytes Semestr 4/aisd/Pracownia 2/rozw3.cpp | 71 ++++++++++++++++++++ Semestr 4/aisd/Pracownia 2/rozw4.cpp | 51 +++++++++++++++ Semestr 4/aisd/pracownia3/check.cpp | 87 ++++++++++++++++++++++++ Semestr 4/aisd/pracownia3/gen.py | 14 ++++ Semestr 4/aisd/pracownia3/ocen.sh | 18 +++++ Semestr 4/aisd/pracownia3/rozw.cpp | 102 +++++++++++++++++++++++++++++ Semestr 4/aisd/pracownia3/show_problem.pdf | Bin 0 -> 73936 bytes Semestr 4/sieci/cwiczenia1/c1.pdf | Bin 0 -> 164919 bytes Semestr 4/sieci/cwiczenia1/cw1.pdf | Bin 0 -> 1647345 bytes Semestr 4/sieci/pracownia2/p2.pdf | Bin 0 -> 98190 bytes 11 files changed, 343 insertions(+) create mode 100644 Semestr 4/Pstwo/Lista 4/RP1R_04.pdf create mode 100644 Semestr 4/aisd/Pracownia 2/rozw3.cpp create mode 100644 Semestr 4/aisd/Pracownia 2/rozw4.cpp create mode 100644 Semestr 4/aisd/pracownia3/check.cpp create mode 100644 Semestr 4/aisd/pracownia3/gen.py create mode 100755 Semestr 4/aisd/pracownia3/ocen.sh create mode 100644 Semestr 4/aisd/pracownia3/rozw.cpp create mode 100644 Semestr 4/aisd/pracownia3/show_problem.pdf create mode 100644 Semestr 4/sieci/cwiczenia1/c1.pdf create mode 100644 Semestr 4/sieci/cwiczenia1/cw1.pdf create mode 100644 Semestr 4/sieci/pracownia2/p2.pdf 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 Binary files /dev/null and b/Semestr 4/Pstwo/Lista 4/RP1R_04.pdf differ 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 +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 +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 +using namespace std; + +int n, p, m; +int banned[103][3][3]; +int plane[5][10]; + +bool check(int k, int i, int pp) { + for (int kk = k; kk < k + 3; kk++) { + for (int ii = i; ii < i + 3; ii++) { + if (plane[kk][ii] != banned[pp][kk-k][ii-i]) + return false; + } + } + return true; +} + +void debug(int pp) { + for (int i = 0; i < 3; ++i) { + for (int j = 0; j < 3; ++j) { + cout << ((banned[pp][i][j] == 0) ? '.' : 'x'); + } + cout << "\n"; + } +} + +void debug() { + for (int k = 0; k < 5; ++k) { + for (int i = 0; i < n; ++i) { + cout << (plane[k][i] ? 'x' : '.'); + } + cout << "\n"; + } + cout << "\n"; +} + +int ile[1030]; + +int main() { + cin >> n >> p >> m; + for (int i = 0; i < p; i++) { + for (int k = 0; k < 3; k++) { + string s; + cin >> s; + for (int j = 0; j < 3; ++j) { + banned[i][k][j] = (s[j] == 'x'); + } + } + } + int res = 0; + for (int mask = 0; mask < (1<<(5 * n)); mask++) { + for (int k = 0; k < 5; ++k) { + for (int i = 0; i < n; i++) { + plane[k][i] = ((mask & (1 << (k * n + i))) > 0); + } + } + bool dziala = true; + for (int k = 0; k < 3; ++k) { + for (int i = 0; i < n-2; ++i) { + for (int j = 0; j < p; ++j) { + if (check(k, i, j)) { + dziala = false; + break; + } + } + if (!dziala) break; + } + if (!dziala) break; + } + if (dziala) { + res++; + if (res == m) { + res = 0; + } + int mm = 0; + for (int i = 0; i < 5; ++i) { + mm += plane[i][n-2] * (1<<(i*2)); + mm += plane[i][n-1] * (1<<(i*2 + 1)); + } + ile[mm]++; + } + } + for (int i = 0; i < 1024; ++i) { + cout << i << ": " << ile[i] << "\n"; + } + cout << res % m << "\n"; +} \ No newline at end of file diff --git a/Semestr 4/aisd/pracownia3/gen.py b/Semestr 4/aisd/pracownia3/gen.py new file mode 100644 index 0000000..b572647 --- /dev/null +++ b/Semestr 4/aisd/pracownia3/gen.py @@ -0,0 +1,14 @@ +import sys + +mask = int(sys.argv[1]) +print(3, 1, 1000000) + +def f(m): + t = [[0]*3]*3 + for i in range(3): + for j in range(3): + t[i][j] = (m >> (i*3 + j)) & 1 + print('x' if t[i][j] else '.', end='') + print() + +f(mask) \ No newline at end of file diff --git a/Semestr 4/aisd/pracownia3/ocen.sh b/Semestr 4/aisd/pracownia3/ocen.sh new file mode 100755 index 0000000..593aa67 --- /dev/null +++ b/Semestr 4/aisd/pracownia3/ocen.sh @@ -0,0 +1,18 @@ +#!/bin/bash + +make rozw +make check +for i in {0..1023} +do + python3 gen.py $i > t.in + ./rozw < t.in > wa.out + ./check < t.in > t.out + if diff -w wa.out t.out + then + echo $i + echo ok + else + echo nieok + break + fi +done \ No newline at end of file diff --git a/Semestr 4/aisd/pracownia3/rozw.cpp b/Semestr 4/aisd/pracownia3/rozw.cpp new file mode 100644 index 0000000..7f1a307 --- /dev/null +++ b/Semestr 4/aisd/pracownia3/rozw.cpp @@ -0,0 +1,102 @@ +#include +using namespace std; + +const int MAXP = 105; +const int MAXN = 5005; + +int n, p, m; +unordered_set banned; +vector> propagate; +int dp[2][1024 + 10]; + +inline int char_to_bit(char c) { + return c == '.' ? 0 : 1; +} + +void input() { + scanf("%d%d%d", &n, &p, &m); + for (int i = 0; i < p; i++) { + char s[5]; + int value = 0, d = 1; + for (int k = 0; k < 3; k++) { + scanf("%s", s); + value += (char_to_bit(s[0]) + char_to_bit(s[1]) * 2 + char_to_bit(s[2]) * 4) * d; + d *= 8; + } + banned.insert(value); + } +} + +pair> get_pieces_values(int db, int sb) { + int tab[5][3]; + for (int i = 0; i < 5; i++) { + tab[i][0] = (db >> (i*2)) & 1; + tab[i][1] = (db >> (i*2 + 1)) & 1; + tab[i][2] = (sb >> i) & 1; + } + int res[3]; + for (int k = 0; k < 3; ++k) { + int value = 0, d = 1; + for (int i = k; i < k + 3; ++i) { + value += (tab[i][0] + tab[i][1] * 2 + tab[i][2] * 4) * d; + d *= 8; + } + res[k] = value; + } + return {res[0], {res[1], res[2]}}; +} + +int combine(int db, int sb) { + int res = (db >> 1) & 0x155; + for (int i = 0; i < 5; i++) { + res |= ((sb >> i) & 1) << (2*i + 1); + } + return res; +} + +void preproces() { + const int db = (1<<10); // double bar + const int sb = (1<<5); // single bar + + for (int db_mask = 0; db_mask < db; ++db_mask) { + for (int sb_mask = 0; sb_mask < sb; ++sb_mask) { + auto pieces = get_pieces_values(db_mask, sb_mask); + if (banned.count(pieces.first) || banned.count(pieces.second.first) || banned.count(pieces.second.second)) + continue; + int db2_mask = combine(db_mask, sb_mask); + propagate.push_back({db_mask, db2_mask}); + } + } +} + +int compute_dp() { + int K = 1; + for (int i = 0; i < 1024; i++) { + dp[0][i] = 1; + } + for (int i = 2; i < n; i++) { + for (auto pp: propagate) { + int p1 = pp.first, p2 = pp.second; + dp[K][p2] += dp[K^1][p1]; + dp[K][p2] %= m; + } + K ^= 1; + for (int j = 0; j < 1024; ++j) { + dp[K][j] = 0; + } + } + + K ^= 1; + int result = 0; + for (int i = 0; i < 1024; i++) { + result += dp[K][i]; + result %= m; + } + return result; +} + +int main() { + input(); + preproces(); + printf("%d\n", compute_dp()); +} \ No newline at end of file diff --git a/Semestr 4/aisd/pracownia3/show_problem.pdf b/Semestr 4/aisd/pracownia3/show_problem.pdf new file mode 100644 index 0000000..f426311 Binary files /dev/null and b/Semestr 4/aisd/pracownia3/show_problem.pdf differ diff --git a/Semestr 4/sieci/cwiczenia1/c1.pdf b/Semestr 4/sieci/cwiczenia1/c1.pdf new file mode 100644 index 0000000..ace2fa7 Binary files /dev/null and b/Semestr 4/sieci/cwiczenia1/c1.pdf differ diff --git a/Semestr 4/sieci/cwiczenia1/cw1.pdf b/Semestr 4/sieci/cwiczenia1/cw1.pdf new file mode 100644 index 0000000..d217892 Binary files /dev/null and b/Semestr 4/sieci/cwiczenia1/cw1.pdf differ diff --git a/Semestr 4/sieci/pracownia2/p2.pdf b/Semestr 4/sieci/pracownia2/p2.pdf new file mode 100644 index 0000000..f0cc942 Binary files /dev/null and b/Semestr 4/sieci/pracownia2/p2.pdf differ -- cgit v1.2.3