From 647fafedf582a892db8b7f2c2858ad1bad3307db Mon Sep 17 00:00:00 2001 From: Franciszek Malinka Date: Sun, 7 Mar 2021 17:58:54 +0100 Subject: Aktualizacja --- Semestr 4/aisd/Pracownia 1/rozw2.cpp | 33 +++++++++++++ Semestr 4/aisd/Pracownia 2/gen.py | 24 ++++++++++ Semestr 4/aisd/Pracownia 2/gen_test.sh | 24 ++++++++++ Semestr 4/aisd/Pracownia 2/rozw.cpp | 59 +++++++++++++++++++++++ Semestr 4/aisd/Pracownia 2/rozw2.cpp | 71 ++++++++++++++++++++++++++++ Semestr 4/aisd/Pracownia 2/show_problem.pdf | Bin 0 -> 53598 bytes 6 files changed, 211 insertions(+) create mode 100644 Semestr 4/aisd/Pracownia 1/rozw2.cpp create mode 100644 Semestr 4/aisd/Pracownia 2/gen.py create mode 100755 Semestr 4/aisd/Pracownia 2/gen_test.sh create mode 100644 Semestr 4/aisd/Pracownia 2/rozw.cpp create mode 100644 Semestr 4/aisd/Pracownia 2/rozw2.cpp create mode 100644 Semestr 4/aisd/Pracownia 2/show_problem.pdf (limited to 'Semestr 4/aisd') diff --git a/Semestr 4/aisd/Pracownia 1/rozw2.cpp b/Semestr 4/aisd/Pracownia 1/rozw2.cpp new file mode 100644 index 0000000..35fd37e --- /dev/null +++ b/Semestr 4/aisd/Pracownia 1/rozw2.cpp @@ -0,0 +1,33 @@ +#include +using namespace std; +typedef unsigned long long ll; + +vector> v; + +int main() { + int n; + scanf("%d", &n); + for (int i = 0; i < n; i++) { + int d, nd, k = 0; + scanf("%d %d", &d, &nd); + while (d % 2 == 0) { + k++; + d /= 2; + } + v.push_back({d, (ll)(1LL< 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/Pracownia 2/gen_test.sh b/Semestr 4/aisd/Pracownia 2/gen_test.sh new file mode 100755 index 0000000..d5bff05 --- /dev/null +++ b/Semestr 4/aisd/Pracownia 2/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/Pracownia 2/rozw.cpp b/Semestr 4/aisd/Pracownia 2/rozw.cpp new file mode 100644 index 0000000..dd0d700 --- /dev/null +++ b/Semestr 4/aisd/Pracownia 2/rozw.cpp @@ -0,0 +1,59 @@ +#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/Pracownia 2/rozw2.cpp b/Semestr 4/aisd/Pracownia 2/rozw2.cpp new file mode 100644 index 0000000..fa0b2d6 --- /dev/null +++ b/Semestr 4/aisd/Pracownia 2/rozw2.cpp @@ -0,0 +1,71 @@ +#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/Pracownia 2/show_problem.pdf b/Semestr 4/aisd/Pracownia 2/show_problem.pdf new file mode 100644 index 0000000..4ab0312 Binary files /dev/null and b/Semestr 4/aisd/Pracownia 2/show_problem.pdf differ -- cgit v1.2.3