From c5fcf7179a83ef65c86c6a4a390029149e518649 Mon Sep 17 00:00:00 2001 From: Franciszek Malinka Date: Tue, 5 Oct 2021 21:49:54 +0200 Subject: Duzy commit ze smieciami --- Semestr 4/aisd/pracownia2/gen.py | 24 ---------- Semestr 4/aisd/pracownia2/gen_test.sh | 24 ---------- Semestr 4/aisd/pracownia2/rozw.cpp | 59 ------------------------ Semestr 4/aisd/pracownia2/rozw2.cpp | 71 ----------------------------- Semestr 4/aisd/pracownia2/rozw3.cpp | 71 ----------------------------- Semestr 4/aisd/pracownia2/rozw4.cpp | 51 --------------------- Semestr 4/aisd/pracownia2/show_problem.pdf | Bin 53598 -> 0 bytes 7 files changed, 300 deletions(-) delete mode 100644 Semestr 4/aisd/pracownia2/gen.py delete mode 100755 Semestr 4/aisd/pracownia2/gen_test.sh delete mode 100644 Semestr 4/aisd/pracownia2/rozw.cpp delete mode 100644 Semestr 4/aisd/pracownia2/rozw2.cpp delete mode 100644 Semestr 4/aisd/pracownia2/rozw3.cpp delete mode 100644 Semestr 4/aisd/pracownia2/rozw4.cpp delete mode 100644 Semestr 4/aisd/pracownia2/show_problem.pdf (limited to 'Semestr 4/aisd/pracownia2') diff --git a/Semestr 4/aisd/pracownia2/gen.py b/Semestr 4/aisd/pracownia2/gen.py deleted file mode 100644 index 13aed55..0000000 --- a/Semestr 4/aisd/pracownia2/gen.py +++ /dev/null @@ -1,24 +0,0 @@ -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 deleted file mode 100755 index d5bff05..0000000 --- a/Semestr 4/aisd/pracownia2/gen_test.sh +++ /dev/null @@ -1,24 +0,0 @@ -#!/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 deleted file mode 100644 index dd0d700..0000000 --- a/Semestr 4/aisd/pracownia2/rozw.cpp +++ /dev/null @@ -1,59 +0,0 @@ -#include -using namespace std; - -const int MAX_SUM = 1e6; -const int N = 2e3 + 10; - -unordered_map sums; -vector> 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 deleted file mode 100644 index fa0b2d6..0000000 --- a/Semestr 4/aisd/pracownia2/rozw2.cpp +++ /dev/null @@ -1,71 +0,0 @@ -#include -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 deleted file mode 100644 index 8e3dd2a..0000000 --- a/Semestr 4/aisd/pracownia2/rozw3.cpp +++ /dev/null @@ -1,71 +0,0 @@ -#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/pracownia2/rozw4.cpp b/Semestr 4/aisd/pracownia2/rozw4.cpp deleted file mode 100644 index 73ff79a..0000000 --- a/Semestr 4/aisd/pracownia2/rozw4.cpp +++ /dev/null @@ -1,51 +0,0 @@ -#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/pracownia2/show_problem.pdf b/Semestr 4/aisd/pracownia2/show_problem.pdf deleted file mode 100644 index 4ab0312..0000000 Binary files a/Semestr 4/aisd/pracownia2/show_problem.pdf and /dev/null differ -- cgit v1.2.3