aboutsummaryrefslogtreecommitdiff
path: root/semestr-4/aisd/pracownia2
diff options
context:
space:
mode:
Diffstat (limited to 'semestr-4/aisd/pracownia2')
-rw-r--r--semestr-4/aisd/pracownia2/gen.py24
-rwxr-xr-xsemestr-4/aisd/pracownia2/gen_test.sh24
-rw-r--r--semestr-4/aisd/pracownia2/rozw.cpp59
-rw-r--r--semestr-4/aisd/pracownia2/rozw2.cpp71
-rw-r--r--semestr-4/aisd/pracownia2/rozw3.cpp71
-rw-r--r--semestr-4/aisd/pracownia2/rozw4.cpp51
-rw-r--r--semestr-4/aisd/pracownia2/show_problem.pdfbin0 -> 53598 bytes
7 files changed, 300 insertions, 0 deletions
diff --git a/semestr-4/aisd/pracownia2/gen.py b/semestr-4/aisd/pracownia2/gen.py
new file mode 100644
index 0000000..13aed55
--- /dev/null
+++ b/semestr-4/aisd/pracownia2/gen.py
@@ -0,0 +1,24 @@
+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
new file mode 100755
index 0000000..d5bff05
--- /dev/null
+++ b/semestr-4/aisd/pracownia2/gen_test.sh
@@ -0,0 +1,24 @@
+#!/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
new file mode 100644
index 0000000..dd0d700
--- /dev/null
+++ b/semestr-4/aisd/pracownia2/rozw.cpp
@@ -0,0 +1,59 @@
+#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
new file mode 100644
index 0000000..fa0b2d6
--- /dev/null
+++ b/semestr-4/aisd/pracownia2/rozw2.cpp
@@ -0,0 +1,71 @@
+#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
new file mode 100644
index 0000000..8e3dd2a
--- /dev/null
+++ b/semestr-4/aisd/pracownia2/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/pracownia2/rozw4.cpp b/semestr-4/aisd/pracownia2/rozw4.cpp
new file mode 100644
index 0000000..73ff79a
--- /dev/null
+++ b/semestr-4/aisd/pracownia2/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/pracownia2/show_problem.pdf b/semestr-4/aisd/pracownia2/show_problem.pdf
new file mode 100644
index 0000000..4ab0312
--- /dev/null
+++ b/semestr-4/aisd/pracownia2/show_problem.pdf
Binary files differ
generated by cgit v1.2.3 (git 2.25.1) at 2024-11-22 21:27:32 +0000