aktualizacja

2 files changed, 122 insertions, 0 deletions

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