aboutsummaryrefslogtreecommitdiff
path: root/Semestr 4/aisd/pracownia3
diff options
context:
space:
mode:
authorFranciszek Malinka <franciszek.malinka@gmail.com>2021-03-26 18:04:17 +0100
committerFranciszek Malinka <franciszek.malinka@gmail.com>2021-03-26 18:04:17 +0100
commitd6e7fae474dc97e46990a45b48ac4f69a35072eb (patch)
tree15e3ce59b6c26875162f221e3a5dd9e1daba05a1 /Semestr 4/aisd/pracownia3
parentaf5ee4836792f6c235414c7a4b73b73f4dd191ea (diff)
aktualizacja
Diffstat (limited to 'Semestr 4/aisd/pracownia3')
-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.pdfbin0 -> 73936 bytes
5 files changed, 221 insertions, 0 deletions
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
Binary files differ