aboutsummaryrefslogtreecommitdiff
path: root/Semestr 4/aisd/Pracownia 2
diff options
context:
space:
mode:
Diffstat (limited to 'Semestr 4/aisd/Pracownia 2')
-rw-r--r--Semestr 4/aisd/Pracownia 2/rozw.cpp59
-rw-r--r--Semestr 4/aisd/Pracownia 2/rozw2.cpp71
-rw-r--r--Semestr 4/aisd/Pracownia 2/rozw3.cpp71
-rw-r--r--Semestr 4/aisd/Pracownia 2/show_problem.pdfbin53598 -> 0 bytes
4 files changed, 0 insertions, 201 deletions
diff --git a/Semestr 4/aisd/Pracownia 2/rozw.cpp b/Semestr 4/aisd/Pracownia 2/rozw.cpp
deleted file mode 100644
index dd0d700..0000000
--- a/Semestr 4/aisd/Pracownia 2/rozw.cpp
+++ /dev/null
@@ -1,59 +0,0 @@
-#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/Pracownia 2/rozw2.cpp b/Semestr 4/aisd/Pracownia 2/rozw2.cpp
deleted file mode 100644
index fa0b2d6..0000000
--- a/Semestr 4/aisd/Pracownia 2/rozw2.cpp
+++ /dev/null
@@ -1,71 +0,0 @@
-#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/Pracownia 2/rozw3.cpp b/Semestr 4/aisd/Pracownia 2/rozw3.cpp
deleted file mode 100644
index 8e3dd2a..0000000
--- a/Semestr 4/aisd/Pracownia 2/rozw3.cpp
+++ /dev/null
@@ -1,71 +0,0 @@
-#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/show_problem.pdf b/Semestr 4/aisd/Pracownia 2/show_problem.pdf
deleted file mode 100644
index 4ab0312..0000000
--- a/Semestr 4/aisd/Pracownia 2/show_problem.pdf
+++ /dev/null
Binary files differ
generated by cgit v1.2.3 (git 2.25.1) at 2024-11-23 07:54:17 +0000